я балансовая переменная

ПРИМЕРЫ НА МОП

 

Задача № 2.2.1.

С использованием алгоритма Гомори метода отсекающих плоскостей (МОП) решить следующую задачу дискретного программирования:

Решение (см. раздел 3.3.в [1]):

Для применения алгоритма Гомори необходимо, чтобы все коэффициенты исходного ограничения неравенства были представлены в целочисленной форме, чтобы и на балансовую переменную х [3] распространилось условие целочисленности. Умножая левую и правую часть ограничения на 10, обеспечиваем выполнение этого условия. После перехода к равенству задача принимает следующий вид:

Снимая условие целочисленности, ищем оптимальное решение соответствующей ЗЛП на D´ с использованием алгоритма с-т , начиная с очевидного допустимого базиса () (табл. 2.8, 2.9).

Таблица 2.8 Таблица 2.9

	13/7		4/7	1/7
	-39		-1	-3

 

(см. рис. 2.2).

Первая большая итерация:

Вводим в с- т 1-е правильное отсечение (табл. 2.10). С ним в ЗЛП ввелась

я балансовая переменная.

Таблица 2.10

	13/7		4/7	1/7
	-6/7		-4/7	-1/7
	-39		-1	-3

После одной итерации двойственного симплекс-метода получаем таблицу 2.11.

Таблица 2.11

	3/2			1/4	-7/4
	-75/2			-11/4	-7/4

 

Результат первой большой итерации .

Для графического отображения этого результата первое правильное отсечение в пространстве переменных x [1] и x [2] на основе соответствующей симплекс таблицы может быть получено следующим образом:

Графическое решение ЗЛП на первой большой итерации приведено

на рис. 2.3.

 

Вторая большая итерация.

Вводим 2-е правильное отсечение (табл. 2.13).

Таблица 2.13

	3/2			1/4	-7/4
	-1/2			-1/4	-1/4
	-75/2			-11/4	-7/4

После первой итерации двойственного симплекс метода получаем табл. 2.13.

 

Таблица 2.13

	-1			-1
						-7
	-34			-1		-7

Так как балансовая переменная x [4] первого правильного отсечения вновь стала базисной, то реализуем процедуру сжатия с-т, удаляя соответствующие этой переменной строку и столбец (тал. 2.14).

Таблица 2.14

	-1			-1
					-7
	-34			-1	-7

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

Таблица 2.15

		-1			-4
	-33	-1			-11

Графическое решение ЗЛП на второй большой итерации приведено

на рис. 2.4.

Результат второй большой итерации - оптимальное решение исходной задачи: .

 

 

Задание на дом

 

С использованием алгоритма Гомори решить следующую задачу дискретного программирования: