1 Линейное программирование
1.1 Расчет оптимального плана и экстремального значения функции цели
Найти максимальное значение функции F(x)=2x1-4x2-4x3 при следующих ограничениях:
Для удобства приведем все ограничения к виду умножив обе части второго неравенства на -1.
Введем дополнительные переменные x4, x5, x6, и искусственную переменную R, и преобразуем ограничения к виду равенств:
Предположим, что все исходные переменные задачи x1, x2, x3 – небазисные. Тогда дополнительные переменные будут базисными. вободные члены определяют решение задачи.
Функция цели: max
Если цель максимизация, то коэффициенты функции цели заносятся с изменением знака.
В первой симплекс-таблице (табл. 1.1) коэффициенты при небазисных переменных в F-строке меняют знаки на противоположные, т.к. осуществляется максимизация функции.
Т аблица 1.1
БП |
Своб. члены |
НП |
||
x1 |
x2 |
x3 |
||
R1 |
-9 |
2 |
-3 |
-2 |
x4 |
-21 |
3 |
-5 |
-5 |
x5 |
-9 |
-2 |
3 |
-4 |
x6 |
30 |
2 |
2 |
5 |
F |
0 |
-2 |
4 |
4 |
M |
9 |
-2 |
3 |
2 |
Решение, соответствующее таблице 1.1, не является допустимым, т.к. есть отрицательный свободный член.
Выберем ведущий столбец и строку: наибольший по модулю отрицательный свободный член находится в x4-строке, в этой строке наибольший по модулю отрицательный элемент соответствует столбцу x3, следовательно, столбец x3 – ведущий. На пересечении ведущей строки и ведущего столбца будет ведущий элемент.
Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов предыдущей таблицы. Элементы новой симплекс-таблицы пометим штрихом, т.е. b'j, a'ji, ci', F0'. Пересчет элементов производится по следующим образом:
Производим пересчет симплекс-таблицы 1.1 и получим таблицу 1.2:
Т аблица 1.2
БП |
Своб. члены |
НП |
||
x1 |
x2 |
x4 |
||
R1 |
-0,6 |
0,8 |
-1 |
-0,4 |
x3 |
4,2 |
-0,6 |
1 |
-0,2 |
x5 |
7,8 |
-4,4 |
7 |
-0,8 |
x6 |
9 |
5 |
-3 |
1 |
F |
-16,8 |
0,4 |
0 |
0,8 |
M |
0,6 |
-0,8 |
1 |
0,4 |
Производим пересчет симплекс-таблицы 1.2 и получим таблицу 1.3:
БП |
Своб. члены |
НП |
|
x1 |
x4 |
||
x2 |
0,6 |
-0,8 |
0,4 |
x3 |
3,6 |
0,2 |
-0,6 |
x5 |
3,6 |
1,2 |
-3,6 |
x6 |
10,8 |
2,6 |
2,2 |
F |
-16,8 |
0,4 |
0,8 |
M |
0 |
0 |
0 |
Искомый максимум функции F(x) равен свободному члену F-строки
табл. 1.3, взятому с обратным знаком, так как maxF(x) = -min(-F(x)).
x1=0;
x2=0,6;
x3=3,6;
x4=0;
x5=3,6;
x6=10,8.
Решение задачи в Matlab:
>> F=[-2 4 -4]
F =
-2 4 -4
>> A=[3 -5 -5;-2 3 -4; 2 2 5; -1 0 0; 0 -1 0 ; 0 0 -1 ]
A =
3 -5 -5
-2 3 -4
2 2 5
-1 0 0
0 -1 0
0 0 -1
>> B=[-21;-9;30;0;0;0]
B =
-21
-9
30
0
0
0
>> Aeq=[2 -3 -2]
Aeq =
2 -3 -2
>> Beq=[-9]
Beq =
-9
>> x=linprog(F,A,B,Aeq,Beq)
Optimal solution found.
x =
1.0714
0
5.5714