рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Область применения

Область применения - раздел Математика, Линейное программирование: постановка задач и графическое решение Область Применения. Графический Метод Основан На Геометрической Интерп...

Область применения.

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного простран6тва, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств.

Задачу пространства размерности больше трех изобразить графически вообще невозможно.

Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные. Найти минимальное значение функции (2.1) Z = С 1 х 1 +С 2 х 2 при a 11 x 1 + a 22 x 2 b 1 (2.2) a 21 x 1 + a 22 x 2 b 2 a M1 x 1 + a M2 x 2 b M (2.3) х 1 0, х 2 0 Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен.

Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: a i1 x 1 + a i2 x 2 + a i3 x 3 = b i ,(i = 1, 2, n), х 1 =0, х 2 =0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С 1 х 1 + С 2 х 2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию.

Найти точку многоугольника решений, в которой прямая С 1 х 1 + С 2 х 2 = const опорная и функция Z при этом достигает минимума. Значения Z = С 1 х 1 + С 2 х 2 возрастают в направлении вектора N =(С 1 , С 2 ), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х 1 , х 2 ) находим, решая систему уравнений прямых АВ и АЕ. Если многоугольник решений представляет собой неограниченную многоуголь-ную область, то возможны два случая.

Случай 1. Прямая С 1 х 1 + С 2 х 2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2). Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а – 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в). 2.1. Примеры задач, решаемых графическим методом. Решим графическим методом задачи использования сырья и составления рациона.

Задача использования сырья. Для изготовления двух видов продукции Р 1 и Р 2 используют три вида сырья: S 1 , S 2 , S 3 . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукци, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1. Таблица 2.1. Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции Р 1 Р 2 S 1 20 2 5 S 2 40 8 5 S 3 30 5 6 Прибыль от единицы продукции, руб. 50 40 Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Решение.

Обозначим через х 1 количество единиц продукции Р 1 , а через х 2 – количество единиц продукции Р 2 . Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений: 2х 1 + 5х 2 20 8х 1 + 5х 2 40 5х 1 + 6х 2 30 которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превысит имеющихся запасов. Если продукция Р 1 не выпускается, то х 1 =0; в противном случае x 1 0. То же самое получаем и для продукции Р 2 . Таким образом, на неизвестные х 1 и х 2 должно быть наложено ограничение неотрицательности: х 1 0, х 2 0. Конечную цель решаемой задачи – получение максимальной прибылипри реализации продукции – выразим как функцию двух переменных х 1 и х 2 . Реализация х 1 единиц продукции Р 1 и х 2 единиц продукции Р 2 дает соответственно 50х 1 и 40х 2 руб. прибыли, суммарная прибыль Z = 50х 1 + 40х 2 (руб.) Условиями не оговорена неделимость единица продукции, поэтому х 1 и х 2 (план выпуска продукции) могут быть и дробными числами.

Требуется найти такие х 1 и х 2 , при которых функция Z достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х 1 + 40х 2 при ограничениях 2х 1 + 5х 2 20 8х 1 + 5х 2 40 5х 1 + 6х 2 30 х 1 0, х 2 0. Построим многоугольник решений (рис. 2.3). Для этого в системе координат х 1 Ох 2 на плоскости на плоскости изобразим граничные прямые 2х 1 + 5х 2 = 20 (L 1 ) 8х 1 + 5х 2 = 40 (L 2 ) 5х 1 + 6х 2 = 30 (L 3 ) х 1 = 0, х 2 = 0. Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскости на рис. 2.3 показаны стрелками). Многоугольником решений данной задачи является ограниченный пятиугольник ОАВСD. Для построения прямой 50х 1 + 40х 2 = 0 строим радиус-вектор N = (50;40) = 10(5;4) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.3 следует, что опорной по отношению к многоугольнику решений эта прямая становится в точке С, где функция Z принимает максимальное значение.

Точка С лежит на пересечении прямых L 1 и L 2 . Для определения ее координат решим систему уравнений 8x 1 + 5х 2 = 40 5х 1 + 6х 2 = 30 Оптимальный план задачи: х 1 = 90/23 = 3,9; х 2 = 40/23 = 1,7. Подставляя значения х 1 и х 2 в линейную функцию, получаем Z max = 50 3,9 + 40 1,7 = 260,3 Таким образом, для того чтобы получить максимальную прибыль в размере 260,3 руб необходимо запланировать производство 3,9 ед. продукции Р 1 и 1,7 ед. продукции Р 2 . Задача составления рациона.

При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S 1 , не менее 8 ед. вещества S 2 и не менее 12 ед. вещества S 3 . Для составления рациона используют два вида корма.

Содержание количества елиниц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 2.2. Таблица 2.2. Питательные вещества Количество единиц питательных веществ в 1 кг корма.

Корм 1 Корм 2 S 1 3 1 S 2 1 2 S 3 1 6 Стоимость 1 кг корма, коп. 4 6 Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.

Решение. Для составления математической модели обозначим через х 1 и х 2 соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимая во внимание значения, приведенные в таблице 2.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений 3х 1 + х 2 9 х 1 + 2х 2 8 х 1 + 6х 2 12 х 1 0, х 2 0. Если корм 1 не используется в рационе, то х 1 =0; в противном случае x 1 0. Аналогично имеем х 2 0. То есть должно выполняться условие неотрицательности переменных: х 1 0, х 2 0. Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х 1 + 6х 2 (коп.) Требуется найти такие х 1 и х 2 , при которых функция Z принимает минимальное.

Таким образом, необходимо найти минимальное значение линейной функции Z = 4х 1 + 6х 2 при ограничениях.

– Конец работы –

Эта тема принадлежит разделу:

Линейное программирование: постановка задач и графическое решение

Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.Казалось бы, что для исследования линейной… Действительно, путь необходимо исследовать на экстремум линейную функцию Z = С… Для решения задач линейного программирования потребовалось создание специальных методов.Особенно широкое…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Область применения

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Формулировка задачи
Формулировка задачи. Даны линейная функция (1.1) Z = С 1 х 1 +С 2 х 2 + +С N x N и система линейных ограничений a 11 x 1 + a 22 x 2 + + a 1N Х N = b 1 a 21 x 1 + a 22 x 2 + + a 2N Х N = b 2 a i1 x

Геометрическая интерпретация задачи линейного программирования
Геометрическая интерпретация задачи линейного программирования. Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств. Найти минимальное значение

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги