Основы математического программирования (стр. 6 )

Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны 0.

x1 = 0;
x2 = 3;
x3 = 0;
x4 = 0;
x5 = 0;
x6 = 0;
x7 = 12;
Z = 150

Вариант задачи будет недопустимым, если в первоначальном опорном решении, хотя бы один их свободных членов отрицателен.

Выбор разрешающего элемента при недопустимом варианте.

Разрешающая строка – выбрать из отрицательных свободных членов наибольший по модулю. Это и будет разрешающая строка.

Разрешающий столбец – выбранный свободный член поделить на каждый элемент разрешающей строки. Наименьшее положительное отношение и укажет на столбец.

2.6. Приведение общей задачи математического программирования к канонической форме

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

Это можно сделать следующим образом:

Возьмем линейное неравенство

а1х1 + а2х2 + … + аnxn ≤ b (1)

прибавим к его левой части некоторую величину хn+1, такую чтобы неравенство превратилось в равенство

а1х1 + а2х2 + … + аnxn + хn+1 = b (2)

где хn+1 = b - а1х1 - а2х2 - … - аnxn

Неотрицательная переменная хn+1 ≥ 0 называется дополнительной переменной.

Следующая теорема дает основание для такого преобразования.

Каждому решению β = (β1, β2, …, βn) неравенства (1) соответствует единственное решение β* = (β1, β2, …, βn, βn+1) уравнения.

Пример:

Дано: х1 + х2 ≤ 4

Получаем: х1 + х2 + х3 = 4

Дано: х1 + х2 ≥ 4

Умножим левую и правую части на -1

–х1 – х2 ≤ - 4

Переходим к уравнению.

–х1 – х2 + х3 = - 4 или х1 + х2 – х3 = 4

Пример.

Z = 30x1 + 35x2 + 136x3 max

x1 + x2 + 10x3 ≤ 136

0,2x1 + 0,2x2 ≤ 22

3x3 ≤ 15

x1 ≥ 100

xj ≥ (j = 1, 2, 3)

x4 + x1 + x2 + 10x3 = 136

x5 + 0,2x1 + 0,2x2 = 22

x6 +3x3 = 15

x7 – x1 = –100

Zmax -30x1 – 35 x2 – 136 x3 = 0

БП	СЧ	Х1 *	Х2	Х3	Х4	Х5	Х6	Х7
X4	136	1	1	10	1	0	0	0
X5	22	2/10	2/10	0	0	1	0	0
X6	15	0	0	3	0	0	1	0
X7 *	-100	-1	0	0	0	0	0	1
Z	0	-30	-35	-136	0	0	0	0

БП	СЧ	Х1	Х2	Х3 *	Х4	Х5	Х6	Х7
X4 *	36	0	1	10	1	0	0	1
X5	2	0	2/10	0	0	1	0	2/10
X6	15	0	0	3	0	0	1	0
X1	100	1	0	0	0	0	0	-1
Z	3000	0	-35	-136	0	0	0	-30

БП	СЧ	Х1	Х2*	Х3	Х4	Х5	Х6	Х7
X3	36/10	0	1/10	1	1/10	0	0	1/10
X5	2	0	2/10	0	0	1	0	2/10
X6	42/10	0	-3/10	0	-3/10	0	1	-3/10
X1	100	1	0	0	0	0	0	-1
Z	3489,6	0	-214/10	0	136/10	0	0	-164/10

БП	СЧ	Х1	Х2	Х3	Х4	Х5	Х6	Х7
X3	26/10	0	0	1	1/10	-1/2	0	0
X2	10	0	1	0	0	5	0	1
X6	72/10	0	0	0	-3/10	3/2	1	0
X1	100	1	0	0	0	0	0	-1
Z	3703,6	0	0	214	35	0	0	5

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