Пример:

Прибыль от выпуска изделий А, В, С составляет соответственно3, 4, 5 единиц соответственно. Для каждого изделия требуется время использования станка I и II типа, которые доступны 12 и 15 часов в день соответственно. Найти оптимальный план производства.

Таблица использования станков для изготовления продукции вида А, В, С:

	А	В	С
I	2	3	3
II	4	1	2

Решение:

Пусть , , - предполагаемое количество изделий А, В, С к выпуску.

Составим математическую модель задачи:

Приведем задачу к канонической форме:

Данная система ограничений задачи приведена к единичному базису. Введенные дополнительные неотрицательные балансовые переменные принимаем за базисные.

Составляем исходную симплекс–таблицу:

		0	3	4	5	0	0
	БП	БР
0		12	2	3	3	1	0
0		15	4	1	2	0	1
		0	-3	-4	-5	0	0

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

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

		0	3	4	5	0	0
	БП	БР
5		4		1	1		0
0		7		-1	0		1
		20		1	0		0

Решение получено, т.к. есть нет отрицательных оценок в индексной строке.

F_max =20, X^*=(0,0,4).

Утверждение (конечность симплекс-метода):

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

Целочисленное программирование.

Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.

Схема решения задачи целочисленного программирования:

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

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

.

3. Производим составление для этой переменной дополнительного ограничения по схеме Гомори :

, где [ ] – целая часть числа.

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

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

Замечание: При выборе строки для построения сечения по схеме Гомори может оказаться, что переменных с одинаковой максимальной дробной частью несколько. Тогда для образования сечения выбирается первая из них.