Задачи для решения

3. Привести к канонической форме и найти решение симплексным методом следующие задачи линейного программирования.

1. 3.2.

2. 3.4.

5. 3.6.

5. 3.8.

9. 3.10.

9. 3.12.

13. 3.14.

3. Метод искусственного базиса

Этот метод используется также для определения исходного опорного плана. Он особенно удобен, когда число переменных значительно превосходит число уравнений.

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

(1.11)

при ограничениях

(1.12)

(1.13)

где - дополнительные неотрицательные переменные.

Составленная задача называется М – задачей. Для задачи на минимум целевая функция имеет вид:

. (1.14)

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

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

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

Теорема.

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

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

3. Если М – задача неразрешима, то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции.

Так как целевая функция состоит из двух частей

, (1.15)

то при решении табличным симплекс – методом после F – строки необходимо ввести М – строку. Решение сначала осуществляется по М – строке. Выводимые из базиса переменные можно опускать, так как вводить их снова в базис нецелесообразно. Процесс симплексных преобразований продолжается до тех пор, пока из базиса не будут исключены все искусственные переменные. Дальнейшие вычисления ведутся по F – строке, а М – строка опускается.

Первоначальная симплексная таблица для М – задачи имеет вид:

Таблица 1.19

Б.П.	1	С.П.
		-	-	…	-
F				…
М				…

где - коэффициенты при переменных М – слагаемого целевой функции.

Пример 11. Найти решение методом искусственного базиса следующей задачи

,

.

Решение. 1. Составляем М – задачу. Уравнения системы ограничений не разрешены относительно естественных базисных переменных. Поэтому вводим в них искусственные переменные: - в первое уравнение и - во второе. В результате получим следующую М – задачу:

,

.

2. Выразим целевую функцию и базисные переменные через свободные переменные

Подставляем выражения для базисных переменных в целевую функцию М – задачи, получим:

( + )=

= ( .

3. Составим симплексную таблицу 1.20.

Таблица 1.20

Б.П.	1	С.П.
		-	-	-	-
=	2	1	1	-1	1
=	24	1		10	-10
F =	0	-1	-2	-3	4
М=	-26	-2	-15	-9	9

4. Расчёт ведём по М – строке. Сделав шаг симплексных преобразований с разрешающим элементом 14, придём к таблице 2. Переменную после вывода из базиса мы исключили из дальнейшего рассмотрения (соответствующий ей столбец опустили). В этой таблице ещё содержится решение М – задачи .

Таблица 1.21

Б.П.	1	С.П.
		-	-	-
=	2/14	13/14	-24/14
=	24/14	1/14	10/14	-10/14
F =	48/14	-12/14	-22/14	66/14
М=	-4/14	-13/14	24/14	-24/14

5. Фиксируем столбец, соответствующий и снова делаем шаг симплексных преобразований с разрешающим элементом 24/14, таблица 1.22.

Таблица 1.22

Б.П.	1	С.П.
		-	-
=	2/24		-1
=	596/336	154/336	0
F =	1020/336	-370/336	1056/336
М=	-2/14	0	0

Полученное решение является оптимальным для М – задачи. Для исходной задачи оно ещё не является оптимальным, так как в F – строке есть отрицательный элемент.

6. Отбрасываем М – строку и по F – строке фиксируем первый столбец. В качестве разрешающего элемента принимаем 13/24. Делаем ещё шаг симплексных преобразований, результаты которого в таблице 1.23.

Таблица 1.23

Б.П.	1	С.П.
		-
	2/13
	596/182
f	875/273	1413/273

Получили оптимальный план исходной задачи , .