Дискретное программирование

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

Дискретными являются задачи с логическими переменными, принимающими только два значения - нуль или единица

Искомые переменные

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

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

Зависимости между переменными (как целевые функции, так и ограничения):

• Линейные зависимости, в которых переменные входят в первой степени и с ними выполняются только действия сложения или вычитания.

Задачи дискретного программирования

Задачи дискретного программирования:

• Задача о контейнерных перевозках (о рюкзаке)
• Задача о назначении (проблема выбора)
• Транспортные задачи.

Задача о назначении является исторически первой задачей дискретного программирования.

Методы решения

Метод Гомори

Используя симплексный метод, находят решения задачи без учета целочисленных переменных

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

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

В случае необходимости составляют еще одно дополнительное ограничение и продолжают процесс до получения оптимального плана задачи.

Метод ветвей и границ

!Pasted image 20241002124504.png

Задача решается без учета целочисленности.

Далее ...

На основе полученного решения составляются дополнительные ограничения:

Решается еще две задачи ЛП, в каждую из которых вошли все исходные ограничения и одно из дополнительных

Если одно из решений удовлетворяет целочисленности, значение целочисленной функции принимается за граничное $Е$.
При этом рассмотрение других задач продолжается до тех пор, пока не будет получено на одной из ветвей недопустимое решение, тогда дальнейшее вычисление по этой ветви прекращается.

На одной из ветвей целочисленной решение, тогда значение целочисленной функции при данных значениях переменных сравнивается с верхним () граничным значением $Е$, если полученное значение хуже, то оно отбрасывается, а если лучше, то принимается за граничное

Типы задач дискретного программирования

• Тип - при целочисленных значениях некоторых исходных данных они обладают целочисленным оптимальным планом. (транспортная задача и ее модификация)
• ...

Задачи о контейнерных перевозках

Задачи о назначении

Транспортные задачи

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

Экономическая постановка задачи

Имеется $m$ поставщиков и $n$ потребителей некоторой продукции.
Заданы тарифы (стоимость) перевозок единицы продукции от поставщиков к потребителям.
Известны объемы запасов у поставщиков и потребности каждого потребителя.
Требуется составить план поставок продукции от поставщиков к потребителям так, чтобы суммарная стоимость перевозок была минимальной.

Задачу можно представить в виде матрицы размерами $m$ x $n$ где поставщики это строчки, а потребители это столбцы. Ячейки содержат в себе стоимость перевозки единицы продукции от поставщиков к потребителям.

Математическая постановка задачи

$min\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{X}_{ij}$ - целевая функция
Ограничения:
$\sum _{i=1}^m{X}_{ij}=b_j,j=1,2,\dots ,n$ - Каждый потребитель должен быть удовлетворен
$\sum _{j=1}^n{X}_{ij}=a_i,i=1,2,\dots ,m$ - Каждый поставщик должен вывезти со склада всю продукцию
$X_{ij}\ge 0$

$X_{ij}$ - количество продукции вывозимое от $i$-го поставщика к $j$-ому потребителю
Здесь:
$x_{ij}$ - объем;
$c_{ij}$ - тариф поставки продукции от $i$-го поставщика к $j$-ому потребителю;
$b_j$ - потребности потребителей в продукции;
$a_i$ - запасы продукции у поставщиков.

Исходные данные транспортной задачи

Заданы мощности поставщиков и потребности потребителей, а также транспортные затраты на перевозку единицы продукции от поставщиков к потребителям.

Пример

!Pasted image 20241002131428.png

Целевая функция: $5X_{11}+9X_{12}+4X_{13}+5X_{14}+X_{21}+5X_{22}+5X_{23}+6X_{24}+2X_{31}+2X_{32}+10X_{33}+4X_{34}+3X_{41}+7X_{42}+2X_{43}+6X_{44}\to min$
Ограничения:
$X_{11}+X_{21}+X_{31}+X_{41}=20$
$X_{12}+X_{22}+X_{32}+X_{42}=50$
$X_{13}+X_{23}+X_{33}+X_{43}=20$
$X_{14}+X_{24}+X_{34}+X_{44}=35$

$X_{11}+X_{12}+X_{13}+X_{14}=30$
$X_{21}+X_{22}+X_{23}+X_{24}=20$
$X_{31}+X_{32}+X_{33}+X_{34}=30$
$X_{41}+X_{42}+X_{43}+X_{44}=40$

Для того чтобы решить задачу, надо проверить задачу на условие закрытости
Для этого находим суммы:
Объема производства: $30+20+30+40=120$
Объема потребления: $20+50+20+35=125$

Модель открытая, так как объем производства не покрывает объем потребления. Необходимо добавить еще одного поставщика
${\mathrm{\Delta }}_{Объемпотребления-Объемпроизводства}=5$
Значит вводим фиктивного поставщика с тарификацией перевозок 0, (т.к. $120<125$).
т.е. в таблицу вводим фиктивный объем производства = 5, ($125-120=5$)

Задача принимает вид:

Целевая функция:
$5X_{11}+9X_{12}+4X_{13}+5X_{14}+X_{21}+5X_{22}+5X_{23}+$
$6X_{24}+2X_{31}+2X_{32}+10X_{33}+4X_{34}+3X_{41}+7X_{42}+2X_{43}+6X_{44}+0X_{51}+0X_{52}+0X53+0X54\to min$
Ограничения:
$X_{11}+X_{21}+X_{31}+X_{41}+X_{51}=20$
$X_{12}+X_{22}+X_{32}+X_{42}+X_{52}=50$
$X_{13}+X_{23}+X_{33}+X_{43}+X_{53}=20$
$X_{14}+X_{24}+X_{34}+X_{44}+X_{54}=35$

$X_{11}+X_{12}+X_{13}+X_{14}=30$
$X_{21}+X_{22}+X_{23}+X_{24}=20$
$X_{31}+X_{32}+X_{33}+X_{34}=30$
$X_{41}+X_{42}+X_{43}+X_{44}=40$
$X_{51}+X_{52}+X_{53}+X_{54}=5$

Теперь модель закрытая и можно решать задачу.
=СУМПРОИЗВЕД((план), (тарифы)) $\to min$