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

 

     От  элементов строки 1 отнимает соответствующие элементы строки 3, умноженные на 3.

     От  элементов строки 2 отнимает соответствующие  элементы строки 3, умноженные на 2.

     От  элементов строки L отнимает соответствующие элементы строки 3, умноженные на -9. 

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены
X4	1	2	0	1	0	-1	7
X5	-5/3	6	0	0	1	-2/3	8
X6	4/3	0	1	0	0	1/3	6
L	6	-5	0	0	0	3	54

 

X₁ = ( 0 , 0 , 6 , 7 , 8 , 0 ) L =    54 - 6 x₁  + 5 x₂  - 3 x₆

     Значение  функции L для данного решения: L (X₁) = 54

     Шаг 2

     За  ведущий выберем столбец 2 , так  как -5 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.

     За  ведущую выберем строку 2, так  как отношение свободного члена  к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	1	2	0	1	0	-1	7	7/2
X5	-5/3	6	0	0	1	-2/3	8	4/3
X6	4/3	0	1	0	0	1/3	6	-
L	6	-5	0	0	0	3	54	-

 

 

     Разделим  элементы строки 2 на 6.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	1	2	0	1	0	-1	7	7/2
X5	-5/18	1	0	0	1/6	-1/9	4/3	4/3
X6	4/3	0	1	0	0	1/3	6	-
L	6	-5	0	0	0	3	54	-

 

     От  элементов строки 1 отнимает соответствующие  элементы строки 2, умноженные на 2.

     От  элементов строки L отнимает соответствующие  элементы строки 2, умноженные на -5.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены
X4	14/9	0	0	1	-1/3	-7/9	13/3
X5	-5/18	1	0	0	1/6	-1/9	4/3
X6	4/3	0	1	0	0	1/3	6
L	83/18	0	0	0	5/6	22/9	182/3

 

     X₂ = ( 0 , 4/3 , 6 , 13/3 , 0 , 0 ) L =    182/3  - 83/18 x₁ - 5/6 x₅  - 22/9 x₆

     Значение  функции L для данного решения: L (X₂) = 182/3

     Учитывая, что все x_i  ≥ 0, по условию задачи, наибольшее значение функции L равно свободному члену 182/3, т.е. мы получили оптимальное решение.

Ответ: X опт = (0 , 4/3 , 6 , 13/3 , 0 , 0);  Значение функции: L = 182/3 
 

     3.2.Графический  метод решения  задач линейного  программирования.

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

     Каждое  из неравенств задачи линейного программирования определяет на координатной плоскости  некоторую полуплоскость (рис.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

     Все вышесказанное относится и к  случаю, когда система ограничений  включает равенства, поскольку любое  равенство

можно представить в виде системы двух неравенств (см. рис.1)

     Целевая функция(ЦФ) при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

     Это связано с тем, что изменение  значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис. 1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

     Вектор  с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

     Суть  графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

     При поиске оптимального решения задач  линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное  множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

Рисунок 1. Геометрическая интерпретация ограничений  и ЦФ задачи.

     Методика  решения задач ЛП графическим  методом.

1. В ограничениях задачи заменить знаки неравенств знаками  точных равенств и построить соответствующие  прямые.
2. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

     Если  неравенство истинное, то    надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси   и правее оси , т.е. в I-м квадранте.

     Ограничения-равенства  разрешают только те точки, которые  лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
4. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
5. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.
6. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
7. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

     Пример: Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

Переменные  задачи

     В задаче  требуется установить, сколько радиоприемников первой и второй модели надо производить. Поэтому искомыми величинами, а значит, и переменными задачи являются суточные объемы производства каждого типа радиоприемников:

 – суточный объем производства радиоприемников первой модели, [шт/сутки];

 – суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция

     Цель  задачи  – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи радиоприемников обоих моделей, необходимо знать:

• их объемы производства, т.е. и радиоприемников в сутки;
• прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

     Таким образом, доход от продажи суточного  объема производства радиоприемников  первой модели равен  $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

     Возможные объемы производства радиоприемников и ограничиваются следующими условиями:

• количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;
• суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;
• объемы производства радиоприемников не могут быть отрицательными.