Алгоритм метода

1. В столбце ‘В’ выбирается наибольшая по абсолютной величине отрицатель­ная базисная переменная; если все базисные переменные неотрицательны, то процесс вычислений заканчивается, т.к. полученное решение допустимое и оптимальное.

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

Если знаменатели всех отношений равны нулю или положительные, то задача не имеет допустимых решений.

3. После выбора ключевого столбца для получения следующего решения осущест­вляется обычная процедура пересчёта элементов симплексной таб­лицы.

Пример. ОЗЛП

Решение. Выберем в качестве начальных базисных переменных .

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

1	Bi	x1	x2		2	Bi	x1	x4		3	Bi	x3	x4
x3	-3	-3	-1		x3	-1				x1
x4	-6	-4	-3		x2	2				x2
x5	3	1	2		x5	-1				x5	0	-1	1
L	0	-2	-1		L	2				L
		1/2	1/3				2/5	1

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

Ответ: при ;

Пример 2. Составить ОЗ к данной задаче, решить ОЗ двойственным симплекс-мето­дом. Записать ответ ПЗ по известному решению ОЗ.

.

Р е ш е н и е. ОЗ формулируется следующим

образом:

Нахождение оптимального решения ОЗ двойственным симплекс-методом.

ОЗЛП В качестве первоначальных базисных переменных

выбираются :

1	Bi	y1	y2		2	Bi	y5	y2
y3	-6	-1	-1		y3	-4
y4	-8	-1	-4		y4	-6
y5	-10	-5	-1		y1	2
F	0	-2	-1		F	4
		2/5	1				2	3/19
3	Bi	y5	y4		4	Bi	y5	y3
y3					y4	13
y2					y2	5
y1					y1	1
F					F	7
		7/3	3/4

Ответ ОЗ: , , .

Чтобы записать ответ ПЗ, нужно воспользоваться соответствием между перемен­ными прямой и обратной задач.

Ответ ПЗ: , , , .

Задания к практической № 7 (Двойственность в ЛП)

Задание 1. Составить обратные (двойственные) задачи к данным задачам ЛП.

(по примеру 1)

Задача а)

Задача б)

Задание 2. Составить обратные (двойственные) задачи к данной задаче ЛП. Запи­сать ответ по известному решению прямой задачи. (по примеру 3)

Вопросы для повторения

1. В чём заключается сущность двойственности в линейном программировании?

2. Пусть исходная задача состоит в оптимальном использовании ресурсов. Дайте экономическую интерпретацию двойственной задачи.

3. Сформулируйте теорему двойственности.

4. Какие задачи линейного программирования относятся к симметричным?

5. Чему равно количество переменных в обратной задаче?

6. Чему равно количество ограничений в обратной задаче?

7. Чем в обратной задаче становятся правые части ограничений исходной задачи?

8. Чем в обратной задаче становятся коэффициенты при переменных в целевой функции исходной задачи?

9. Как по решению исходной (двойственной) задачи найти решение двойственной (исходной) задачи?

Задания к практической № 8

(Двойственный симплекс-метод)

Задание 1. Составить ОЗ к данной задаче, решить ОЗ двойственным

симплекс-мето­дом. Записать ответ ПЗ по известному решению ОЗ. (по примеру 2)

а)

.

б)

.

Вопросы для повторения

10. В чём состоит сущность двойственного симплекс-метода?

11. Как в симплексной таблице выбирается ключевая строка при решении ЗЛП двойственным симплекс-методом?

12. Как в симплексной таблице выбирается ключевой столбец при решении ЗЛП двойственным симплекс-методом?

13. О чём свидетельствует отсутствие в ключевой строке отрицательных чисел?

14. Какова область применения двойственного симплекс-метода?

15. В чём заключается достоинство двойственного симплекс-метода?

16. Что является признаком окончания вычислений?