1.4 Выводы к Главе 1

• В первой главе на примере данных трех задач продемонстрированы основные этапы и приемы, применяемые при решении задач линейного программирования.

• Сложность решения задач линейного программирования определяется количеством переменных и ограничений в исходной задачe. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.

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

2.1 Решение полностью целочисленных задач Решение задачи методом отсекающих плоскостей

Максимизировать целевую функцию

При ограничениях:

и целые.

Для решения этой полностью целочисленной задачи воспользуемся методом Гомори. Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

Таблица 2.1.1
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8
x5	5	0	0	0	-5	1	0	-2	1
x1	9/2	1	0	0	-1	0	-1/2	0	0
x2	7/4	0	1	0	-2	0	1/4	-1	1/2
x3	5/4	0	0	1	-1	0	-1/4	0	1/2
Y	-16	0	0	0	5	0	1	1	1

Значения целевой функции и переменных:

На основе этой симплексной таблицы для базисной переменной , у которой наибольшая дробная часть, строим уравнение отсекающей плоскости.

Вводим новую свободную переменную:

Выражаем новое ограничение в форме Куна-Таккера:

Добавляем это ограничение к условиям оптимального решения и решаем новую расширенную задачу симплекс методом.

Таблица 2.1.2
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	5	0	0	0	-5	1	0	-2	1	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0
x2	7/4	0	1	0	-2	0	1/4	-1	1/2	0
x3	5/4	0	0	1	-1	0	-1/4	0	1/2	0
x9	-3/4	0	0	0	0	0	-1/4	0	-1/2	1
Y	-16	0	0	0	5	0	1	1	1	0

Таблица 2.1.3
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	7/2	0	0	0	-5	1	-1/2	-2	0	2
x1	9/2	1	0	0	-1	0	-1/2	0	0	0
x2	1	0	1	0	-2	0	0	-1	0	1
x3	½	0	0	1	-1	0	-1/2	0	0	1
x8	3/2	0	0	0	0	0	1/2	0	1	-2
Y	-35/2	0	0	0	5	0	1/2	1	0	2

Требование целочисленности не выполнено. Составляем следующее уравнение отсекающей плоскости. Т.к. дробные части у всех нецелых значений базисных переменных равны, выберем любую, например .

Аналогично:

.

Теперь решаем новую расширенную задачу.

Таблица 2.1.4
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	7/2	0	0	0	-5	1	-1/2	-2	0	2	0
x1	9/2	1	0	0	-1	0	-1/2	0	0	0	0
x2	1	0	1	0	-2	0	0	-1	0	1	0
x3	½	0	0	1	-1	0	-1/2	0	0	1	0
x8	3/2	0	0	0	0	0	1/2	0	1	-2	0
x10	-1/2	0	0	0	0	0	-1/2	0	0	0	1
Y	-35/2	0	0	0	5	0	1/2	1	0	2	0

Таблица 2.1.5
БП	СЧ	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x5	4	0	0	0	-5	1	0	-2	0	2	-1
x1	5	1	0	0	-1	0	0	0	0	0	-1
x2	1	0	1	0	-2	0	0	-1	0	1	0
x3	1	0	0	1	-1	0	0	0	0	1	-1
x8	1	0	0	0	0	0	0	0	1	-2	1
x6	1	0	0	0	0	0	1	0	0	0	-2
Y	-18	0	0	0	5	0	0	1	0	2	1

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

Ответ: .