1 Линейное программирование

1.1 Расчет оптимального плана и экстремального значения функции цели

Найти максимальное значение функции F(x)=2x₁-4x₂-4x₃ при следующих ограничениях:

Для удобства приведем все ограничения к виду умножив обе части второго неравенства на -1.

Введем дополнительные переменные x₄, x₅, x₆, и искусственную переменную R, и преобразуем ограничения к виду равенств:

Предположим, что все исходные переменные задачи x₁, x₂, x₃ – небазисные. Тогда дополнительные переменные будут базисными. вободные члены определяют решение задачи.

Функция цели: 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, не является допустимым, т.к. есть отрицательный свободный член.

Выберем ведущий столбец и строку: наибольший по модулю отрицательный свободный член находится в x₄-строке, в этой строке наибольший по модулю отрицательный элемент соответствует столбцу x₃, следовательно, столбец x₃ – ведущий. На пересечении ведущей строки и ведущего столбца будет ведущий элемент.

Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов предыдущей таблицы. Элементы новой симплекс-таблицы пометим штрихом, т.е. b^'_j, a^'_ji, c_i^', F₀^'. Пересчет элементов производится по следующим образом:

Производим пересчет симплекс-таблицы 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

Таблица 1.3

Искомый максимум функции F(x) равен свободному члену F-строки

табл. 1.3, взятому с обратным знаком, так как maxF(x) = -min(-F(x)).

x₁=0;

x₂=0,6;

x₃=3,6;

x₄=0;

x₅=3,6;

x₆=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