Конспект лекций по курсу «Математическое программирование»

После выбора генерального элемента нужно перейти к новому опорному плану, при котором переменная становится базисной, а переменная х₁- свободной. Коэффициент при в новой жордановой форме должен быть равен 1. Поэтому первая строка таблицы 3.5 делится на 2. Умножив затем полученную первую строку на (-3) и прибавив ко второй строке, исключим из второго уравнения. Аналогично, с помощью жордановой процедуры исключаем из третьего уравнения и из целевой функции (последнее требует табличный вид ЗЛП).

В результате получим  следующую таблицу.

Таблица 3.6

Б						Q
		0	0	1		2
		1	0	0	3	2
	1	0	1	0	5	7
f		0	0	0		-2

 

Обратим внимание, что в столбце Q в первых трех строках стоят неотрицательные числа, т.е. новый базис по-прежнему является допустимым. Это не случайный факт: так будет всегда при точном соблюдении правила выбора генеральной строки. Далее, значение целевой функции при новом опорном плане равно -2, при старом оно было равно 12. "Улучшение" опорного плана гарантирует правило выбора генерального столбца. Хотя эти факты мы строго не доказываем, следует иметь в виду, что они всегда имеют место.

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

  

3.6. Табличный симплекс-алгоритм.

 

Пусть имеется  заполненная симплекс-таблица.  Подводя итоги изложенному, получим следующий  алгоритм решения ЗЛП симплекс-методом. 

1.  Если в  нижней строке симплекс-таблицы  все числа, кроме, быть может,  самого правого, неположительны, то опорный план, соответствующий   симплекс-таблице,  оптимален,  и   алгоритм останавливается. В противном случае - переход пункту 2.

2. Если симплекс-таблица  содержит столбец, отличный от  самого правого, у которого  в нижней строке стоит положительное  число, а во всех остальных  строках - неположительные числа,  то ЗЛП неразрешима из-за неограниченности  снизу на ОДР целевой функции, и алгоритм останавливается. В противном случае - переход к пункту 3.

3.  Выбираем любой столбец,  отличный от самого правого,  у которого в нижней строке  стоит положительное число - назовем  его генеральным. Затем рассматриваем  строки симплекс-таблицы, отличные от самой нижней, у которых в генеральном столбце стоят положительные числа. Для каждой из таких строк вычисляем отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, является генеральной строкой. Элемент, стоящий на пересечении генерального столбца и генеральной строки, будет генеральным элементом. Переход к пункту 4.

4. Составляем  новую симплекс-таблицу, в которой:

1) из базиса  выведена переменная, стоящая в  генеральной строке; в базис введена переменная, стоящая в генеральном столбце;

2) генеральная  строка поделена на генеральный  элемент;

3) с помощью  жордановой процедуры все числа  генерального столбца, за исключением  1, стоящей в генеральной строке, делаются равными нулю. Переход к пункту 1.

Пример I.  Решить симплекс-методом

Задача записана в каноническом виде, нужно привести ее к табличному виду. Система уравнений  записана в жордановой форме с неотрицательными правыми частями (базисные переменные и ). Необходимо привести к табличному виду целевую функцию. Для этого выразим базисные переменные через свободные

x₃=10 - 2x₁ - x₂

x₄= 8 - x₁ - 2x₂

и подставим в целевую функцию

Для получения табличного вида функцию  запишем так:

Теперь имеем  табличный вид ЗЛП:

Заполним первую симплекс-таблицу    

  

Таблица 3.7

Б					Q
	2	1	1	0	10
	1	2	0	1	8
F	10	6	0	0	28

 

В таблице 3.7 условия  оптимальности и неразрешимости не выполняются. Выберем в качестве генерального столбец , у которого в нижней строке стоит положительное число. Затем, сравнивая отношения 10:3 и 8:1, выберем первую строку в качестве генеральной. В таблице генеральный элемент 2 .

Действуя в соответствии с пунктом 4 табличного симплекс-алгоритма, перейдем к таблице 3.8.

Таблица 3.8

Б					Q
	1			0	5
	0			1	3
F	0	1	-5	0	-22

 

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

Таблица 3.9

Б					Q
	1	0			4
	0	1			2
F	0	0			-24

 

Таблица 3.9 удовлетворяет  условию оптимальности.

Ответ: оптимальный  план

Минимальное значение целевой функции f_min = - 24.

 

Пример 2. Решить симплекс-методом:

 

Прежде всего, ЗЛП нужно привести к каноническому виду

 

Теперь приводим ЗЛП к  табличному  виду.  Видим,   что  система уравнений записана в жордановой форме с неотрицательными правыми частями ( и z- базисные переменные).    Однако в целевую функцию входит базисная переменная . Имеем:

Следовательно, табличный вид ЗЛП  таков:

Заполняем симплекс-таблицу (таблица 3.10).

Таблица 3.10

Б				z	Q
	-1	1	1	0	1
z	1	-2	0	1	4
g	2	0	0	0	-1

После выбора генерального элемента переходим к таблице 3.11

Таблица 3.11

Б				z	Q
	0	-1	1	1	5
z	1	-2	0	1	4
g	0	4	0	-2	-9

 

Обратим внимание на столбец . Он показывает, что целевая функция g не ограничена снизу на ОДР. Вспоминая, что g =-f, получаем ответ.

Ответ: ЗЛП неразрешима  из-за неограниченности  сверху  на ОДР целевой функции f.

 

Пример 3. Решим симплекс-методом задачу об использовании оборудования, поставленную в параграфе 2.1. Там же приводилась ее математическая модель

                                       

Приводим ЗЛП  к каноническому виду

 

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

Заполняем симплекс-таблицу (таблица 3.12).

Таблица 3.12

Б						Q
	2	3	1	0	0	30
	4	2	0	1	0	40
	3	4	0	0	1	60
G	6	7	0	0	0	0

 

Условия оптимальности  и неразрешимости не выполняются. Столбец  (в нижней строке которого стоит наибольшее положительное число) выберем в качестве генерального. Сравнивая отношения 30:3, 40:2, и 60:4, объявляем генеральной первую строку. Поделив ее на 3 и сделав с помощью жордановой процедуры нули во всех остальных строках генерального столбца, после замены базисной переменной на переменную , получим таблицу 3.13.

Таблица 3.13

Б						Q
x2		1		0	0	10
z2		0		1	0	20
		0		0	1	20
g		0		0	0	-70