Раздел II. Специальные задачи лп Целочисленное программирование.
Пример, показывающий, что оптимальное значение задачи без условия целочисленности и с условием целочисленности далеки друг от друга.
З адача: z=5х1+2х2 max
x1+4x2 ≤33
-x1+2x2≤8
x1,x2 0
x1+4x2+x3=33
-x1+2x2+x4=8
x1,x2,x3,x4 0
|
Б |
СБ |
В |
A1 |
A2 |
A3 |
A4 |
|---|---|---|---|---|---|---|---|
|
С1=5 |
С2=2 |
С3=0 |
С4=0 |
|||
A1 |
0 |
33 |
1 |
4 |
1 |
0 |
|
A4 |
0 |
41 |
0 |
6 |
1 |
1 |
|
Zj-Cj |
165 |
0 |
18 |
5 |
0 |
||
Zmax=165 x=(33;0)
Этот пример показывает необходимость разработки специальных методов решения целочисленных (полностью или частично) и дискретных задач ЛП.
Определение: Задача ЛП называется задачей ЦЛП, если на переменные задачи наложено условие целочисленности:
Полностью целочисленные (когда на все переменные)
Частично целочисленные (когда на некоторые переменные)
Различие проявляется в методах решения. Обобщенный случай – это дискретные задачи, в которых область допустимых значений может быть представлена в виде совокупности несвязанных областей или же допустимые значения есть отдельно отстоящие друг от друга значения. Методы решения целочисленных и дискретных задач очень трудоемки и существенно зависят от размерности. Важным частным случаем является задача Булева программирования.
Б
улева
переменная принимает только два значения:
Х= 0
1
Важный класс – это задачи о назначении. Например, имеется 3 самолета и 15 маршрутов. Известны затраты и прибыль от посылки каждого самолета на каждый маршрут. Требуется составить такое направление маршрутов, чтобы получить максимальную прибыль. Х=(0;0;1;0;1;…;0;1;0)
Для данного класса задач свои методы решения.
Методы решения задач:
Метод отсечения Гомори
Комбинаторные методы - метод ветвей и границ.
Задачи целочисленного программирования.
В задачах ЦЛП переменные – есть выражение количества неделимой продукции (люди, единицы техники, комплекты).
В задачах о назначении и размещении – люди, единицы транспорта, предприятия.
В комбинаторных задачах и задачах теории расписания – обходы городов, мест назначения, расписания мероприятий.
При решении проблем выбора – проектов, инвестиций, транспорта.
Пример: «Задача о рюкзаке (задача загрузки корабля)»
Имеется n видов предметов, j-й предмет имеет массу aj и ценность cj. Следует загрузить рюкзак вместимостью В, так что ценность груза была максимальной.
Xj- -количество предметов j-ого вида (неделимых)
Тогда
при ограничениях:
