Алгоритмическая схема метода

Шаг 1. Найти точку - решение задачи линейного программирования (1)-(3) (без условия целочисленности). Положить к=1.

Шаг 2. Если -целочисленная, то решение найдено, останов. Иначе зафиксировать множества I и J –индексов базисных и небазисных переменных.

Шаг 3. Выбрать номер   такой, что координата - дробная.

Шаг 4. Добавить в симплекс-таблицу новое ограничение: .

Шаг 5. С учетом добавленного ограничения отыскать новое решение . Положить k = k +1. Перейти на шаг 2.

Замечание 2. Использование обычного симплекс-метода при решении данной задачи неудобно, так как добавление нового ограничения каждый раз будет приводить к необходимости вызова метода искусственного базиса. Более предпочтительным в данной ситуации является двойственный симплекс-алгоритм. В таком случае новое ограничение вводится в систему в виде:

,

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

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

Решение. Приведем задачу к каноническому виду (предварительно умножив второе ограничение на 2).

Оформим решение в виде симплекс-таблицы

 

B	CB		1	4	0	0	0	0	0	0		Коммен-тарий
			x1	x2	x3	x4	x5	x6	x7	x8
x3	0	10	-1	2	1	0	0				10 /2
x4	0	15	2	2	0	1	0				15/2
x5	0	10	-1	-1	0	0	1				-
Dj			-1	-4	0	0	0
x2	4	5	-1/2	1	1/2	0	0				-
x4	0	5	3	0	-1	1	0				5 /3
x5	0	15	3/2	0	1/2	0	1				10
Dj			-3	0	2	0	0
x2	4	35/6	0	1	1/3	1/6	0	0
x1	1	5/3	1	0	-1/3	1/3	0	0				Найдена
x5	0	25/2	0	0	1	-1/2	1	0				точка
Dj			0	0	1	1	0					x^1!
x6	0	-2/3	0	0	-2/3	-1/3	0	1
x2	4	11/2	0	1	0	0	0	1/2	0
x1	1	2	1	0	0	1/2	0	-1/2	0
x5	0	23/2	0	0	0	-1	1	3/2	0			Найдена
x3	0	1	0	0	1	1/2	0	-3/2	0			точка
Dj			0	0	0	1/2	0	3/2				x^2!
x7	0	-1/2	0	0	0	0	0	-1/2	1
x2	4	5	0	1	0	0	0	0	1	0
x1	1	5/2	1	0	0	1/2	0	0	-1	0
x5	0	10	0	0	0	-1	1	0	-6	0
x3	0	5/2	0	0	1	1/2	0	0	6	0		Найдена
x6	0	1	0	0	0	0	0	1	-2	0		точка
Dj			0	0	0	1/2	0	0	3			x^3!
x8	0	-1/2	0	0	0	-1/2	0	0	0	1
x2	4	5	0	1	0	0	0	0	1	0
x1	1	2	1	0	0	0	0	0	-1	1
x5	0	11	0	0	0	0	1	0	-6	-2
x3	0	2	0	0	1	0	0	0	6	1		Найдено
x6	0	1	0	0	0	0	0	1	-2	0		целочисл.
x4	0	1	0	0	0	1	0	0	0	-2		решение!
Dj			0	0	0	0	0	0	3	1

 

На 3-й итерации симплекс-метода найдено нецелочисленное решение . Выбираем, например,  - дробную базисную координату и по соответствующей строке таблицы формируем новое ограничение: . Или: . Добавляем это ограничение в таблицу и осуществляем одну итерацию двойственного симплекс-метода. В результате получаем точку . Выбираем дробную координату  и добавляем ограничение  и т.д.

На последней итерации получена точка , которая является целочисленной. Останов.

Ответ: ,

 

УПРАЖНЕНИЯ

1. Решить ЦЗЛП методом отсечений:

 

                  

Ответ: =(5,3)              Ответ: =(6,9)                 Ответ: =(2,5)

 

 

Приложение

1. Решение задач линейного программирования 2. Решение задач нелинейного программирования

 

РЕШЕНИЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ СРЕДСТВАМИ EXCEL

 

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