Задача  ЦП. примеры задач  ЦП: задача о ранце, о распределении  капиталовложений между проектами.

Различают 4 типа задач целочисленного (дискретного) программирования (ЦП):

1. задача о неделимостях (с ранцем)
2. экстремальные комбинаторные задачи (з-ча о коммивояжере, м-д ветвей и границ)
3. задачи с разрывными целевыми функциями
4. задачи на несвязных невыпуклых множествах

     Задача  о ранце 

Имеются предметы n типов (наименований). Каждый предмет имеет массу a_j и стоимость c_j. Требуется загрузить ранец грузоподъемностью b так, чтобы он «не лопнул», и чтобы имел наибольшую ценность. 

Пусть x_j – количество предметов j-го наименования, которое мы собираемся погрузить в рюкзак, тогда задача формулируется:

     min     £b

      ³0, все целые – условие целочисленности.

     Аналогом  этой задачи является задача о загрузке корабля: в потру n видов груза, каждый вид груза имеет массу a_j и стоимость c_j. Известна грузоподъемность судна b (груз контейнерный). Требуется отобрать типы грузов в таких количествах, чтобы их общая стоимость была наибольшей, а грузоподъемность корабля не была превышена.

     Задачи  с разрывными целевыми функциями

Многие  экстремальные задачи характеризуются  наличием постоянных затрат, то есть затрат которые могут быть произведены независимо от объема производства, потребления, перевозок. 

пример

Транспортная  задача с фиксированными доплатами. Стоимость перевозок выглядит иначе.

     c_ij^’=0, x_ij=0

     c_ij^’= c_ij x_ij+ d_ij, ³0

     d_ij-фиксированная доплата за аренду транспортных средств.

     Тогда целевая функция суммарных затрат на перевозку примет вид:

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

Основной  прием при этом основывается на введении новой вспомогательной переменной y_ij

     y_y=0

          1…(1)

Второе  ограничение, кот при этом возникает:  x_ij £min{a_i,b_j} y_ij…(2)

  и тогда целевая функция примет вид

Действительно, если y_ij=0, то x_ij=0, а если y_ij=1 условие (2) не существенны, так как они и так выполняются из-за требований к алгоритму.

Задача (1)(3) эквивалентна исходной задаче, но эта задача частично ЦП

     Общая задача ЦП

Рассмотрим задачу ЛП с доп. условием целочисленности на переменные.

      max …(1)

      £b_i i=1..m …(2)

      ³0, j=1..n…(3)

      - целое

Задача (1)-(4) без условия (4) называется  ослаблением  задачи ЦП 

     пример

max (7x1+9x2)

-x1+3x2£6

7x1+x2£35

x1, x2 ³0

x1, x2 – целые 

L*=63 (9/2;7/2) 

основная  идея не предполагает округления полученного  решения (5;4), она вне многогранника  решения.