Целочисленные задачи линейного программирования
1. Обзор темы
Целочисленного программирования
1.1. Математическая постановка задачи целочисленного программирования.
1.2. Алгоритм решения задачи целочисленного программирования графическим методом.
1.3. Алгоритм метода Гомори.
1.1 Математическая постановка задачи целочисленного программирования
Для большинства экономических задач их решение должен быть выражен целыми числами. Например, количество единиц продукции, что нельзя делить, количество оборудования и тому подобное.
Экстремальная задача, переменные которой принимают только целочисленные значения, называется Задачей целочисленного программирования.
В математической модели задачи целочисленного программирования целевая функция и функции системы ограничений могут быть линейными, нелинейными и смешанными.
Сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения. В общем виде эту задачу можно записать так: найти максимум функции
(1.1)
При условиях
(1.2)
, (1.3)
— цели 
(1.4)
Если найти решение задачи симплексным методом, оно может быть как целочисленным, так и нет. В таком случае для нахождения оптимального плана задачи нужны специальные методы. В настоящее время есть несколько таких методов, из которых наиболее известны графический метод и метод Гомори.
1.2 Алгоритм решения задачи целочисленного программирования графическим методом
Графический метод решения задач целочисленного линейного программирования применяется в тех случаях, когда система ограничений и целевая функция содержат не более двух переменных.
Рассмотрим Алгоритм данного Метода на примере:
В цехе предприятия решили установить дополнительное оборудование, для размещения которого выделено 19/3 м2 площади. На приобретение оборудования предприятие может израсходовать 10000 грн., При этом оно может закупить оборудование двух видов. Комплект оборудования и вида стоит 1000 грн., А II вида — 3000 грн. Приобретение одного комплекта оборудования и вида позволит увеличить выпуск продукции в смену на 2 ед., А одного комплекта оборудования ИИ вида — на 4 ед. Для установки одного комплекта оборудования и вида требуется 2 м2 площади, а для оборудования ИИ вида — 1 м2 площади. Определить такой набор дополнительного оборудования, который позволит максимально увеличить выпуск продукции.
Решения. Пусть х1 — количество комплектов оборудования и вида, приобретающий предприятие, а х2 — количество комплектов оборудования ИИ вида. Тогда математическая модель задачи имеет вид:
1) Решить задачу графическим методом [см.. Часть 1, с. 19-20]. При получении целочисленный решение, то задача решена. В противном случае перейти к п.2.
2) Заменить контур многоугольника решений ломаной линией, вершины которой на выходящих за пределы многоугольника решений и имеют целочисленные координаты (см. рис.. 1.1)
3) Строят вектор 
с координатами, равными коэффициентам целевой функции, т. е. вектор с координатами (2, 4).
4) Через точку (0; 0) проводят перпендикулярную вектору прямую А.
5) Переcуваючы прямую А в направлении вектора , определяют первую и последнюю точки пересечения прямой с многоугольником решений. Первая точка — точка минимума, последняя — точка максимума.
6) Определяют координаты точки максимума (минимума).
7) Определяют значение целевой функции в точке максимума (минимума), подставляя в целевую функцию координаты точки максимума (минимума) 
Рис. 1.1
Решением приведенного примера является т. E (1, 3), в которой Целевая функция принимает максимальное значение 
. То есть предприятие должно приобрести 1 комплект оборудования первого вида и 3 комплекта оборудования второго вида. Это обеспечит предприятию максимальное увеличение выпуска продукции составляет 14 единиц в смену.
1.3 Алгоритм метода Гомори.
Другим способом решения задач целочисленного программирования является метод Гомори, который состоит из следующих этапов:
1) Находят решение задачи целочисленного программирования симплексным методом, несмотря на условие целочисленности переменных.
2) Анализируют найденное решение. Если среди Компонентов Нету дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования. В противном случае составляют дополнительное ограничение для переменной, в оптимальном плане задачи (1.1) — (1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (1.1) — (1.4) должна быть целочисленной.
(1.5)
В этой неровности значение 
выписывают из последней симплексной таблицы из строки, соответствующей переменной, для которой составляется дополнительное ограничение. 
— дробные части соответствующих чисел.
Дробной частью числа называется разность между этим числом и его целой частью.
Целой частью числа называется наибольшее целое число, не превышающее данное.
3) С помощью двойственного симплексного метода находят решение задачи, которую получили из задачи (1.1) — (1.4) путем введения дополнительного ограничения.
4) В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (1.1) — (1.4) или до установления невозможности ее решения.
Пример. Предприятие выпускает два вида продукции — А и В. Для этого использует два вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице 1. В ней также указано прибыль от реализации единицы продукции каждого вида и общее количество сырья по видам.
|
Вид сырья |
Нормы расхода сырья (кг) на единицу продукции вида |
Общее количество сырья (кг) |
|
|
А |
В |
||
|
И |
2 |
1 |
|
|
ИИ |
1 |
3 |
4 |
|
Прибыль от реализации одного изделия |
1 |
4 |
Составить такой план производства, при котором прибыль предприятия от реализации всех изделий будет максимальным.
Пусть 
— количество изделий вида А, 
— количество изделий вида В. Тогда прибыль предприятия составляет
При условиях
.
Запишем задачу в форме основной задачи ЛП:
Составлена задача является частично целочисленной, так как переменные 
и 
могут принимать не целочисленные значения.
Применим алгоритм розвьзання целочисленных задач ЛП методом Гомори.
1) Решим задачу симплексным методом без учета условия целочисленности переменных и .
|
№ |
Базис |
Сб |
План |
1 |
4 |
0 |
0 |
Оценочные отношения |
|
Х1 |
Х2 |
Х3 |
Х4 |
|||||
|
1 |
Х3 |
0 |
|
2 |
1 |
1 |
0 |
|
|
2 |
Х4 |
0 |
4 |
1 |
3 |
0 |
1 |
|
|
M +1 |
0 |
-1 |
-4 |
0 |
0 |
|||
|
1 |
Х3 |
0 |
5 |
5/3 |
0 |
1 |
-1/3 |
|
|
2 |
Х2 |
4 |
4/3 |
1/3 |
1 |
0 |
1/3 |
|
|
M +1 |
16/3 |
1/3 |
0 |
0 |
4/3 |
® min2) Анализируем найденное решение: 
. В этом плане переменная приобрела дробного значения. Поэтому необходимо перейти к новой задаче, добавив к системе ограничений еще одно ограничение:
.
Находим значение функции 
как дробной части указанных аргументов:
Или
Для того, чтобы переменная 
стала базисной, умножим полученное уравнение на 
.
|
№ |
Базис |
Сб |
План |
1 |
4 |
0 |
0 |
0 |
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
||||
|
1 |
Х3 |
0 |
5 |
5/3 |
0 |
1 |
-1/3 |
0 |
|
2 |
Х2 |
4 |
4/3 |
1/3 |
1 |
0 |
1/3 |
0 |
|
3 |
Х5 |
0 |
-1 |
-1 |
0 |
0 |
-1 |
1 |
|
M +1 |
16/3 |
1/3 |
0 |
0 |
4/3 |
0 |
3) С помощью двойственного симплексного метода находим решение полученной задачи.
|
№ |
Базис |
Сб |
План |
1 |
4 |
0 |
0 |
0 |
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
||||
|
1 |
Х3 |
0 |
5 |
5/3 |
0 |
1 |
-1/3 |
0 |
|
2 |
Х2 |
4 |
4/3 |
1/3 |
1 |
0 |
1/3 |
0 |
|
3 |
Х5 |
0 |
-1 |
-1 |
0 |
0 |
-1 |
1 |
|
M +1 |
16/3 |
1/3 |
0 |
0 |
4/3 |
0 |
||
|
1 |
Х3 |
0 |
10/3 |
0 |
0 |
1 |
-2 |
5/3 |
|
2 |
Х2 |
4 |
1 |
0 |
1 |
0 |
0 |
1/3 |
|
3 |
Х1 |
1 |
1 |
1 |
0 |
0 |
1 |
-1 |
|
M +1 |
5 |
0 |
0 |
0 |
1 |
1/3 |
Получили целочисленный решение: 
. Следовательно, предприятие должно производить 1 шт. изделий вида А и 1 шт. изделий вида В. При этом его доход составит 5 гр. ед.
3. Рекомендуемая литература
1. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997.
2. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
[…] […]