Целочисленное программирование

.

 

Второй алгоритм Гомори

      Второй алгоритм Гомори используется для решения частично целочисленных линейных задач и отличается от первого лишь способом определения коэффициентов дополнительного ограничения.

     Пусть xk – целочисленная переменная в ЗЛП, а остальные переменные вещественные; в оптимальной симплекс-таблице для ЗЛП без учета целочисленности переменной xk эта переменная является базисной, нецелочисленной и все элементы таблицы – aij , bi . Введем обозначения:       J ={1,..,n}, JH – совокупность индексов небазисных переменных в плане x,

JH+ ={ j∈JH : akj ≥ 0}, JH− ={ j∈JH : akj < 0}. Тогда разложение базисной переменной xk по небазисным будет иметь вид:

 

где bk – значение базисной переменной хk, а дополнительное ограничение будет следующим:

 

где s1 – неотрицательная базисная дополнительная переменная.

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

 

МЕТОД ВЕТВЕЙ И ГРАНИЦ

        Впервые метод ветвей и границ (МВГр) был предложен А. Лэндом и Дж. Дойгом в 1960 г. Он является наиболее широко применяемым комбинаторным методом [1, 2, 3, 7, 8]. Его можно использовать для решения как полностью, так и частично целочисленных задач. Рассмотрим полностью целочисленную задачу. Согласно общей идее метода сначала, так же, как и в методе Гомори, решают задачу линейного программирования с ослабленными ограничениями, без учета требования целочисленности.

        Пусть x* – ее оптимальный план, в котором xk* = bk – не целое число. Так как интервал не содержит целых значений xk , то любое допустимое целое значение этой переменной удовлетворяет одному из неравенств:

1.  или б)

        Введение этих ограничений в ЗЛП порождает две новые задачи: ЛП1 и ЛП2, допустимые множества которых не пересекаются (говорят, что исходная задача разветвляется на две новые подзадачи, а саму процедуру ее замены совокупностью двух задач, эквивалентных ей в смысле оптимального решения, называют ветвлением, переменную xk – переменной разветвления). Оптимальный план целочисленной задачи находится в допустимом множестве либо ЛП1, либо ЛП2. Проводимый в процессе ветвления учет требования целочисленности позволяет исключить из рассмотрения часть множества допустимых решений.

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

Замечание. Если некоторая переменная является непрерывной, то ее не выбирают в качестве переменной разветвления.

     Для повышения эффективности рассмотренной процедуры вводят понятие границы, на основе которого можно судить о необходимости дальнейшего ветвления каждой из подзадач, порожденных исходной ЗЦЛП. Сначала задаем нижнюю границу оптимального значения целевой функции исходной задачи равной – ∞ (в случае минимизации она равна + ∞).

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

      Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.

Рассмотрим использование метода ветвей и границ на примере.

 Пример. Максимизировать:

z = 350x1 +150x2

при ограничениях

25x1 +10x2 ≤100,

40x1 + 20x2 ≤190,  x1, x2 ≥ 0, x1, x2 – целые числа

Отбросив условие целочисленности, решим ЗЛП симплекс-методом.

Получим решение =1, = 7, =1475. Так как переменная нецелочисленная, то выберем ее в качестве переменной ветвления. Допустимое целое значение переменной должно удовлетворять одному из неравенств:

    или

       Далее добавляем к последней симплекс-таблице одно из этих ограничений и получаем задачи ЛП1 (с ограничением ≤ 7) и ЛП2 (с ограничением ≥8). Для задачи ЛП1 оптимальным будет решение =1.2, = 7, z =1470, для задачи ЛП2: = 0.75, =8, z =1462.5.

       Так как целочисленный план не найден, то процесс необходимо продолжить, взяв для следующего разветвления задачу ЛП1, оптимальный план которой дает большее значение целевой функции. Переменной разветвления будет x1. Далее решаем задачи ЛП3 и ЛП4, добавляя ограничения  ≤1, ≥ 2 соответственно.

       Задача ЛП3 решения не имеет, т. к. ее допустимое множество пусто. Решение задачи ЛП4 имеет вид: = 2, = 5, z =1450. Это значение целевой функции меньше, чем значение целевой функции при решении задачи ЛП2, поэтому возвращаемся к ветви, соответствующей ЛП2, и проводим ее ветвление по переменной , добавляя ограничения ≤ 0 и ≥1.

      Первое неравенство с учетом требования неотрицательности переменных дает ограничение = 0, поэтому в ЛП5 дополнительное ограничение имеет вид = 0. В ЛП6 дополнительное ограничение будет в виде ≥1. Допустимое множество задачи ЛП6 пусто. А решением задачи ЛП5 будет вектор с компонентами = 0, , z =1425.

    Значение целевой функции для задачи ЛП5 меньше, чем в задаче ЛП4, поэтому эта ветка неперспективна (при ее ветвлении значения целевых функций не превысят значения 1425). Следовательно, оптимальным решением исходной задачи будет решение задачи ЛП4:  

 = 2, = 5, z* =1450.

Решение задачи проиллюстрируем следующей схемой:

 

Задача о рюкзаке

       Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характеризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, ... единиц. Пусть aij- расход i-го отсека для перевозки единицы j-ой продукции. Обозначим через cj полезность единицы j-ой продукции. Требуется найти план перевозки, при котором максимизируется общая полезность рейса.

Модель задачи примет вид:

 

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

 

условии неотрицательности:

 

условии целочисленности:

 
Когда для перевозки имеется один отсек и каждый вид продукции может быть взят или нет, то модель задачи принимает вид:

 

 

 

 

Задача коммивояжера

        Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

Математическая модель задачи:

 

Условия неотрицательности и целочисленности:

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.

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

Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. Эти задачи интересны и с математической точки зрения. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.

 

 

Список используемой литературы.

1. Н.Ш. Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; под ред. Проф.Н.Ш.Кремера. : Исследование операций в экономике; учеб. Пособие для вузов.
2. Лекция. Целочисленное программирование. (стр.15) https://studfiles.net/preview/6223759/page:15/
3. Методы и способы решения задач целочисленного параметрического программирования. http://works.doklad.ru/view/xw-Tn2gqSl8/3.html
4. Целочисленное программирование.

https://math.semestr.ru/lp/integer_programming.php

5. электронный учебник "Экономико-математические методы”       http://www.math.mrsu.ru/text/courses/method/tselprogr.htm
6. В. Н. Шевченко, Н.Ю. Золотых. Линейное и целочисленное линейное программирование.   http://www.itlab.unn.ru/uploads/opt/optBook1.pdf