Использование линейного программирования для решения задач оптимизации

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (2;5): 10

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (2,5; 2,2; 1,2; 1,5; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 4*65 + 14*55 + 7*75 + 2*60 + 10*15 + 4*85 + 12*15  = 2345

2.2 Решение производственной задачи

Вариант 1.

Предприятие предполагает выпускать два вида продукции А и В, для производства которых используется сырьё трех видов. Производство обеспечено сырьем каждого вида в количествах: 432, 424, 532 кг. На изготовление единицы изделия А требуется затратить сырья каждого вида 2, 3, 5 кг, соответственно, а для единицы изделия В – 5, 4, 3 кг. Прибыль от реализации единицы изделия А составляет 34 ден.ед., для единицы изделия В – 50 ден.ед.

Требуется составить план производства изделий А1 и А2 обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Требуется составить план производства изделий А и В обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Решение.

Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (2х1 +5 х2) единиц ресурса I, (3х1 +4х2) единиц ресурса II, (5х1 +3х2) единиц ресурса III. Так как потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

2х1 +5х2 ≤ 432;                         

3х1 +4х2 ≤ 424;                     (6)

5х1 +3х2 ≤ 532.                              

По смыслу задачи переменные:

х1 ≥ 0, х2 ≥ 0.                       (7)

Суммарная прибыль составит 34х1 от реализации продукции А и 50х 2 от реализации продукции В, то есть :

F = 34х1 +50х 2                    max                     (8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком « + », так как все неравенства имеют вид « ≤ ».

Получим систему ограничений в виде :

2х 1 +5х2 + х3 ≤ 432;

3х1 +4х2 + х4 ≤ 424; (9)

5х1 + 3х2 + х5 ≤ 532.

Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х3, х4, х5 отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х3, х4, х5.

Не основные переменные: х1, х2. .

Выразим основные переменные через не основные :

х3 = 432 - 2х1 - 5х2 ;

х4 = 424-3х1 - 4х2; (10)

х5 = 532 - 5х1 - 3х2.

Положив основные переменные равными нулю, то есть х1 = 0, х2 = 0, получим базисное решение Х1 = (0, 0, 432, 424, 532), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:

F = 34х1 + 50х2 . max

При решении Х1 значение функции равно F(Х1). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение F с положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х1 и х2 входят в выражение для F со знаком «+». Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х2. Система (10) накладывает ограничения на рост переменной х2 . Поскольку необходимо сохранять допустимость решений, то есть все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х1 = 0 как не основная переменная):