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

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

Сначала решаем задачу линейного программирования, затем преобразуем полученные решения и получаем задачу целочисленного программирования.

В общем виде задача ЦП формулируется следующим образом: найти

максимум или минимум функции

Методы решения задач целочисленного программирования.

Таблица 12

Целевая функция стремится к максимуму или к минимуму

Система линейных ограничений- неравенств записывается в каноническом виде

Метод Гомори.

Задача решается симплекс- методом без учета целочосленности переменных.

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

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

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

Задача 4

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

Пусть дана целевая функция

Вводим искусственные переменные и . Приведем систему ограничений к виду:

Составим соответствующую таблицу

Таблица 13

БП СП				СЧ
	-3	6	7	8
	6	-3	7	8
	-3	-3	-13	0

Получим опорный план (0,0,0,0), который не является оптимальным, так как в последней строке, соответствующей целевой функции, содержатся отрицательные элементы. Выберем минимальный из элементов последней строки: Этот элемент определяет выбор разрешающего столбца.

Таблица 14

БП СП				СЧ
	-3	6	7	8
	6	-3	7	8
	-3	-3	-13	0

Свободные члены разделим на соответствующие элементы разрешающего столбца и выберем минимальное из отношений:

(8/7;8/7)

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

Таблица 15

БП СП				СЧ
	-3	6	7	8
	6	-3	7	8
	-3	-3	-13	0

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

Элементы разрешающей строки разделим на разрешающий элемент

Элементы разрешающего столбца(кроме разрешающего элемента), заменим нулями.

Все остальные элементы пересчитаем по правилу прямоугольника.

Таблица 16

БП СП				СЧ
	-3/7	6/7	7/7=1	8/7
	9	-9	0	0
	-60/7	57/7	0	104/7

Получим опорный план (0;0;8/7)

Так как в последней строке содержатся отрицательные элементы, то данный план не оптимален. Выберем минимальный из элементов последней строки:

Этот элемент определяет выбор разрешающего столбца.

Таблица 17

БП СП				СЧ
	-3/7	6/7	1	8/7
	9	-9	0	0
	-60/7	57/7	0	104/7

Разделим свободные члены на элементы разрешающего столбца и выберем минимальное из отношений: ((8/7):(-3/7);0:9) Этот элемент определяет выбор разрешающего столбца.

Таблица 18

БП СП				СЧ
	-3/7	6/7	1	8/7
	9	-9	0	0
	-60/7	57/7	0	104/7

Преобразуем данную таблицу по указанным выше правилам:

Таблица 19

БП СП				СЧ
	0	3/7	1	8/7
	9/9=1	-9/9=-1	0/9=0	0/9=0
	0	3/7	0	104/7

Получим новый опорный план (0;0;8/7).

План является оптимальным, но не удовлетворяет условиям целочисленности. 8/7=1

Запишем значения в виде смешанных чисел:

Таблица 20

БП СП				СЧ
	0		1
	1	-1	0	0
	0		0

Отсекаем дробную часть

Составим соответствующую новую таблицу:

Таблица 21

БП СП				СЧ
	0		1
	1	-1	0	0
	0		0
	0		0

Таблица 22

БП СП				СЧ
	0	0	1	1
	2	0	0
	0	0	0	15
	0	1	0

План является оптимальным, но не удовлетворяет условиям целочисленности. Отсекаем дробную часть

Таблица 23

БП СП				СЧ
	0	0	1	1
	2	0	0
	0	0	0	15
	0	1	0
	-1	0	0

Таблица 24

БП СП				СЧ
	0	0	1	1
	1	0	0	0
	0	0	0	13
	0	0	0	0
	0	0	0	0

Получим новый опорный план (0;0;1).План является оптимальным и удовлетворяет условиям целочисленности. Функция имеет максимальное значение Z(X)=13

Задания для самостоятельного решения по теме №3