Без учета требования целочисленности симплекс-методом. Результаты пошагового решения приведены в табл. 12. 1

без учета требования целочисленности симплекс-методом. Результаты пошагового решения приведены в табл. 12.1-12.3.
Таблица 12.1

			1	-1	0	0	-М
-М		4	-1	[2]	-1	0	1
0		14	3	2	0	1	0	7
			М	-2М	М	0	- М
			1- М	-1+2М	- М	0	0

Вводим в базис переменную , выводим .

Таблица 12.2

			1	-1	0	0	-М
-1		2		1		0		--
0		10	[4]	0	1	1	-1
				-1		0	-
				0	-	0	-M+

Вводим в базис переменную , выводим .
Таблица 12.3

			1	-1	0	0	-М
-1			0	1			1
1			1	0			-
			1	-1			-
			0	0	-	-	-M+

Оптимальное решение (рис. 12.2) целочисленным не является, . Включаем в множество номеров задач, подлежащих ветвлению , и переходим к шагу 2.
2⁰. Так как выбираем для ветвления задачу ЗЛП-0 , исключаем из множества и переходим к шагу 3.
3⁰. Осуществим ветвление задачи ЗЛП-0. Выбираем координату , так как ее значение имеет наибольщую дробную часть, и сформируем:
а) дополнитльные ограничения
б) две задачи ЗЛП-
ЗЛП-1 ЗЛП-2

Перепишем их в расширенной форме (см.§11.1):
ЗЛП-1 ЗЛП-2

Полагаем и переходим к шагу 4.

4⁰. Решаем задачу ЗЛП-1. Результаты пошагового решения задачи ЗЛП-1 приведены в табл. 12.4-12.6.
Таблица 12.4

			1	-1	0	0	0	-М
-M		4	-1	[2]	-1	0	0	1
0		14	3	2	0	1	0	0	7
0		2	1	0	0	0	1	0	--
			M	- 2M	M	0	0	- M
			1- M	-1+ 2M	- M	0	0	0

Вводим в базис переменную , выводим .
Таблица 12.5

			1	-1	0	0	0	-М
-1		2		1		0	0		--
0		10	2	0	1	1	0	-1	5
0		2	[1]	0	0	0	1	0	2
				- 1		0	0	-
				0	-	0	0	-M+

Вводим в базис переменную , выводим .
Таблица 12.6

			1	-1	0	0	0	-М
-1		3	0	1		0
0		6	0	0	1	1	-2	-1
0		2	1	0	0	0	1	0
			1	- 1		0		-
			0	0	-	0	-	-M+

Оптимальное решение (точка на рис. 12.2) Переходим к шагу 5.

5⁰. Решение -первое целочисленное. Полагаем - первое целочисленное. Полагаем и включаем решение в множество . Так как , то сравнивать значение не с чем. Перейдем к шагу 6.
6⁰. Проверим вқполнение условия . Полагаем и переходим к шагу 4.
4¹. Решаем задачу ЗЛП-2. Результаты ее пошагового решения приведены в табл. 12.7-12.9.

Таблица 12.7

			1	-1	0	0	0	-М	-М
-M		4	-1	[2]	-1	0	0	1	0
0		14	3	2	0	1	0	0	0	7
-M		3	1	0	0	0	-1	0	1	--
			0	- 2M	M	0	M	- M	- M
			1	-1+ 2M	- M	0	- M	0	0

Вводим в базис переменную , выводим .
Таблица 12.8

			1	-1	0	0	0	-М	-М
-1		2	-	1	-	0	0		0	--
0		10	[4]	0	1	1	0	-1	0
-M		3	1	0	0	0	-1	0	1	3
			-M+	1		0	M	-	- M
			M+	0	-	0	- M	- M+	0

Вводим в базис переменную , выводим .
Таблица 12.9

			1	-1	0	0	0	0	-М
-1			0	1	-		0	-	0
1			1	0			0	-	0
-M			0	0	-	-	-1		1
			1	-1			M	-	- M
			0	0	-	-	- M	-	0

Решение закончено , но из табл. 12.9 следует , что ограничения задачи ЗЛП-2 несовместны – множество допустимых решений пусто (рис.12.2) , потому что искусственная переменная в оптимальном решении не равна нулю. Исключаем задачу ЗЛП-2 из рассмотрения. Переходим к шагу 6.
6¹. Проверим выполнение условия . Переходим к шагу 2.
2¹. Так как множество , переходим к шагу 7.
7⁰. Так как множество содержит единственное целочисленное решение, то решение исходной задачи. ■
Пример 12.2. Найти оптимальное решение задачи

□ 1. Положим . Решаем ЗЛП-0 , т.е. исходную задачу без учета требования целочисленности, графически. Как следует из рис. 12.3, , максимум достигается в точке . Решение не является целочисленным. Включаем номер в множество и переходим к шагу 2.
2⁰. Так как , выбираем для ветвления задачу ЗЛП-0 , исключаем и из множества и переходим к шагу 3.
3⁰. Осуществим ветвление задачи ЗЛП-0. Выберем нецелочисленную координату с наименьшим индексом: . Сформируем:
а) дополнительные ограничения:
б) две задачи ЗЛП-
ЗЛП-1 ЗЛП-2