Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. Пособие для студентов вузов. М.: Высш. Шк., 1986. с.16-26.

2. Исследование операций в экономике: Учебн. пособ. Для вузов /Н.Ш.Кремер, Б.А.Путко и др.; Под. Ред. Проф. Н.Ш.Кремера. ­ М.: Банки и биржи, ЮНИТИ, 1997. 55-63.

3. Деордица Ю.С., Нефедов Ю.М. Исследование операций в планировании и управлении: Учебн. пособ. К.: Вища школа, 1991. с.35-36.

4. Зайченко Ю.П., Шумилова С.А. Исследование операций: сборник задач, 2-е изд. К.: Вища школа, 1990. с.14-16.

ЗАДАЧА 2

Решить задачу линейного программирования методом искусственного базиса

Рекомендации к решению задачи

Пусть следующая задача линейного программирования не имеет исходного опорного плана

(2.1)

(2.2)

(2.3)

Задача вида

(2.4)

(2.5)

(2.6)

где M – некоторое достаточно большое положительное число, называется расширенной задачей по отношению к задаче (2.1)-(2.3).

Расширенная задача имеет опорный план . Базисные переменные x_n+I, I = 1,.. т, называются искусственными. Так как расширенная задача имеет опорный план, то ее можно решать симплекс-методом.

ТЕОРЕМА 2.1. Если в оптимальном плане X* расширенной задачи (2.4) — (2.6) значения искусственных переменных X_n+i = 0, i = 1,..m, то X* является оптимальным планом задачи (2.1) — (2.3).

ТЕОРЕМА 2.2. Если в оптимальном плане X* расширенной задачи (2.4) — (2.6) хотя бы одна искусственная переменная отлична от нуля, то система ограничений (2.1) — (2.3) исходной задачи несовместна (область допустимых решений пустая).

Таким образом, теоремы 2.1 и 2.2 дополняют алгоритм симплекс-метода новыми условиями, которые учитываются при использовании искусственных переменных в исходной задаче.

Пример. Решить симплекс-методом следующую задачу линейного программирования:

Решение. Строим каноническую форму исходной задачи:

,

где исходное базисное решение Х = (0; 0; 20; —10; 80) не является опорным планом, так как x₄ = -10. Строим исходный опорный план, используя искусственную базисную переменную х₆, которую вводим во второе уравнение системы ограничений. Одновременно введем в функцию цели искусственную базисную переменную с отрицательным коэффициентом М и умножим второе уравнение на (-М):

Затем строим нулевое приведенное уравнение, исключая из функции цели искусственную базисную переменную х_6.

Далее задача решается прямым симплекс-методом. Отличие состоит только в том, что сначала оптимизация проводится по Z (признак оптимальности положительные коэффициенты при переменных), а затем по Z:

Построение исходной симплекс таблицы

хбаз	Х1	Х2	Х3	Х4	Х5	Х6	Bi
Х3	5	-2	1	0	0	0	20
Х6	1	2	0	-1	0	1	10
Х5	-7	10	0	0	1	0	80
Z	-4	3	0	0	0	0	0
Z	-M	-2M	0	M	0	0	-10M

Выбор разрешающего элемента производится так же, как при прямом симплекс-методе. Пересчет элементов симплекс-таблицы производится по тем же формулам (Жордана-Гаусса), что и при прямом симплекс-методе:

(2.7)

где a_lk – разрешающий элемент.