2015-03-07
482
Определение. Задачи математического программирования с требованием целочисленности переменных называются задачами целочисленного программирования.
Задача о назначениях - задача целочисленного программирования. Она решается проще, чем задача линейного программирования, но это, скорее, исключение, чем правило. Обычно требование целочисленности усложняет задачу.
Запишем задачу линейного программирования в стандартной форме с требованием целочисленности.
На практике применяется несколько способов решения таких задач.
1. Решить эту задачу симплекс-методом, и если получится нецелочисленное оптимальное решение, то округлить до ближайшего допустимого целочисленного решения. Этот путь возможен тогда, когда значения X в оптимальном решении достаточно велики.
2. Найти точное решение целочисленной задачи линейного программирования (ЦЗЛП).
Важными методами нахождения таких решений являются методы отсечений нецелочисленных решений. Отсечения должны удовлетворять следующим условиям.
1. Они должны отсекать оптимальное нецелочисленное решение задачи, полученное на предыдущем шаге.
2. Они не должны отсечь ни одного допустимого целочисленного решения.
Разберем один из таких методов - метод отсечения Гомори.
Алгоритм решения ЦЗЛП методом Гомори
1. Решаем задачу линейного программирования без требования целочисленности симплекс-методом.
| X1 | Х2 | … | Хk | Хk+1 | … | Xn | ||
| X1 | … | 
| 
| 
| ||||
| X2 | … | 
| 
| 
| ||||
| … | … | … | … | … | … | … | … | … |
| Хk | … | 
| 
| 
|
Х1*=
Х2*=
…………
Хk*=
Хk+1*=0
…………
Хn*=0
Если все значения в оптимальном решении целочисленные, то получено решение ЦЗЛП. Если множество допустимых решений исходной задачи пусто или целевая функция на этом множестве не ограничена, то же самое будет верно и для ЦЗЛП.
2.Определение. Целой частью числа X называется ближайшее целое число, меньшее X. Обозначается [X].
Например, если х = 3,45; [x] = 3.
Определение. Дробной частью числа X называется разность
между X и целой частью этого числа.
Например, если x = 3,45; {x} =0,45.
На втором шаге всегда есть хотя бы одно нецелое среди 
. Выбираем из нецелых то, которое имеет наибольшую дробную часть, обозначим такое через 
.
Гомори доказал, что неравенство
определяет отсечение, удовлетворяющее всем сформулированным выше требованиям. Это неравенство добавляем к ограничениям задачи и возвращаемся на шаг 1, и так до тех пор, пока не получится оптимальное целочисленное решение. Если на каком-то шаге алгоритма все коэффициенты 
- целочисленные, а среди есть нецелые, то задача не имеет целочисленного решения.
Пример. Фермеры некоторого района решили оборудовать сортировочный ток. На закупку оборудования имеется 34 тыс.$, имеется площадь для тока размером 60 м2, имеется два типа сортировочных машин, которые можно закупить. Машина типа А стоит 3 тыс.$, занимает площадь 3 м2 с учетом проходов и сортирует 2 тонны зерна за смену; машина типа В стоит 4 тыс.$, занимает площадь 5 м2 с учетом проходов и сортирует 3 тонны зерна за смену. Поставщик сообщил, что машин тина В в наличии не более 8. Сколько и каких машин нужно закупить, чтобы обеспечить максимальную производительность тока за смену, не превысив имеющихся ресурсов?
Введём управляющие переменные. Обозначим x1 - количество купленных машин типа А, х2 - количество купленных машин типа В.
| X1 | X2 | Х3 | Х4 | х5 | ||
| Х3 | ||||||
| х4 | ||||||
| Х5 | ||||||
| F | -2 | -3 | ||||
| X3 | -5 | |||||
| X4 | -4 | |||||
| Х2 | ||||||
| F | -2 | |||||
| Х3 | -1 | -1 | ||||
| X1 | 1/3 | -4/3 | 2/3 | |||
| Х2 | ||||||
| F | 2/3 | 1/3 | 251/3 |
По условию задачи очевидно, что закупать 2/3 машины типа А бессмысленно. Если данное решение округлить до допустимого решения, то получим
х1 =0
х2 = 8.
F = 24
Найдём точное решение. Строим отсечение.
;
| X1 | Х2 | Х3 | X4 | X5 | X6 | ||
| -1 | -1 | ||||||
| 1/3 | -4/3 | 2/3 | |||||
| 1/3 | 2/3 | -1 | 2/3 | ||||
| Х3 | -1/2 | -3/2 | |||||
| X1 | -2 | ||||||
| х2 | -1/2 | 3/2 | |||||
| Х5 | 1/2 | -3/2 | |||||
| F | 1/2 | 1/2 |
Полученное решение целочисленно. Нужно закупить две машины типа А и семь машин типа В.
Вопросы для самоконтроля
1. Какая задача линейного программирования называется целочисленной?
2. Структура экономико-математической модели задачи
целочисленного программирования?
3. Какие существуют методы решения задач целочисленного программирования?
4. Пояснить суть метода Гомори.
5. Что называется сечением Гомори?
6. Пояснить принципиальную суть метода ветвей и границ.
7. Пояснить происхождение названия метода ветвей и границ.
