Глава II. Модели линейного программирования 3 страница

Метод искусственного базиса (М-метод).

Применительно к рассматриваемой задаче М-метод заключается в следующем. В каждое уравнение системы ограничений (5.11), введем свою новую искусственную неизвестную: , и . Включим их в число базисных неизвестных и составим новую функцию цели

, (6.3)

где М – произвольно большое положительное число.

В результате получили следующую ЗЛП, приведенную к допустимому виду

(6.4)

(6.5)

. (6.6)

Задачу (6.4) – (6.6) называют М-задачей.

Сформулируем утверждения, устанавливающие связь между решениями исходной задачи и М-задачи.

1. Если в оптимальном решении М-задачи все искусственные неизвестные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т. е. , если ).

2. Если имеется оптимальное решение М-задачи, в котором хотя бы одна из искусственных переменных отлична от 0, то исходная задача не имеет допустимого решения.

3. Если М-задача не имеет оптимального решения, то исходная задача неразрешима (т. е. если , то либо , либо нет ни одного допустимого решения).

Из этих утверждений следует следующее правило решения M-задачи симплекс-методом:

а) Необходимо выбирать последовательность шагов таким образом, чтобы все искусственные неизвестные , , вышли из базиса, т. е. стали свободными.

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

в) Если при решении М-задачи получена симплекс-таблица, дающая оптимальное решение, и в этой таблице хотя бы одна искусственная неизвестная входит в базис, причем в строке для свободный член положителен, то исходная задача не имеет ни одного допустимого решения.

Составим симплекс-таблицы 6.5 решаемой задачи.

Таблица 6.5

Базисные неизвестные	Свободные члены
				–1
					–1
						–1
G
				–1
					–1
G
				–1
G
									–1
G				–5	–1

В строке (G) нет положительных элементов (кроме столбца «свободные члены»). Все искусственные неизвестные , и вышли из базиса. Задача решена. Получили оптимальное решение:

при , , , .

Взаимно двойственные задачи линейного программирования. Первая и вторая теоремы двойственности

С каждой ЗЛП связана двойственная к ней задача. Из решения одной задачи находят решение другой.

Пара взаимно двойственных ЗЛП имеет следующий вид.

Таблица 7.1

Задача I (исходная)	Задача I¢ (двойственная)
(7.1)   (7.2)     Найти (7.3) при условиях (7.1), (7.2)	(7.1¢) (7.2¢)     Найти (7.3¢) при условиях (7.1¢), (7.2¢)

Если ввести в рассмотрение матрицу

из коэффициентов при неизвестных в системе (7.1), а также матрицы-столбцы

, , , ,

то получим другую (матричную) форму записи задач I и I¢:

Таблица 7.2

Задача I (исходная)	Задача I¢ (двойственная)
(7.1)   (7.2)   (7.3) при условиях (7.1), (7.2)	(7.1¢)   (7.2¢)   (7.3¢) при условиях (7.1¢), (7.2¢)

Задачи I и I¢ называются двойственными друг другу. Смысл, который вкладывается в это название, состоит в следующем.

1. Если первая задача имеет размеры (т ограничений с п неизвестными), то вторая ‑ размеры .Так, в задаче I два ограничения с тремя неизвестными, а в задаче I¢ ‑ три ограничения с двумя неизвестными.

2.Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными. Так, в задаче I матрица из коэффициентов при , , есть A в то время как в задаче I¢матрица из коэффициентов при , есть .

3. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.

4. В задаче I все ограничения представляют собой неравенства типа £, причем в этой задаче требуется достичь максимума f. Напротив, в задаче I¢ все ограничения суть неравенства типа ³, причем требуется достичь минимума j.

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

Первая теорема двойственности. Если одна из взаимно двойственных задач (I) и (I¢) имеет оптимальное решение, то его имеет и другая, причем

.

Если в одной из задач (I) и (I¢) целевая функция не ограничена, то другая задача не имеет допустимых решений.

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

Связь между первоначальными неизвестными одной из двойственных ЗЛП и дополнительными неизвестными другой задачи в общем виде устанавливается таблицей 7.3

Таблица 7.3

Неизвестные исходной задачи I
Первоначальные	Дополнительные
Первоначальные	Дополнительные
Неизвестные исходной задачи I¢

Перейдем к примерам.

Пусть исходная задача – первая основная задача Лекции 4. Запишем ее в виде:

(7.4)

(7.5)

(7.6)

Тогда двойственная ей задача имеет вид:

(7.4¢)

(7.5¢)

(7.6¢)

Решим ЗЛП (7.4¢) – (7.6¢) М-методом.

Сначала введем балансовые неизвестные и , чтобы привести ЗЛП к каноническому виду, а затем и искусственные неизвестные и . В результате получим следующую М-задачу:

Составим симплекс-таблицы 7.4 решаемой задачи.

Таблица 7.4

Базисные неизвестные	Свободные члены
					–1
						–1
G
					–1
G
G					–32	–10
				–2	–2			–1
						–1	–1
G				–12	–36	–6

В последней строке четвертой симплекс-таблицы нет положительных чисел ( достаточны большие) в столбцах неизвестных ( достаточны большие). Задача решена.

при .

Пользуясь теоремами двойственности, нетрудно найти решение первой основной задачи.

Действительно, по первой теореме двойственности

.

Учитывая связь между переменными двойственных задач

по второй теореме двойственности из последней строки четвертой симплекс-таблицы, имеем

т. е. – оптимальное решение первой основной задачи (ранее оно было получено в Лекциях 4 и 6).

Обратно, из последней строки симплекс-таблицы решения первой основной задачи (см. Лекцию 6) легко находим решение двойственной задачи:

,

.

Экономический смысл рассмотренных взаимно двойственных ЗЛП.

Задача I об использовании сырья , и привела нас к плану выпуска продукции (36; 6), при котором прибыль от реализации продукции максимальная и составляет 1104 единиц.