Методы и способы решения задач целочисленного параметрического программирования (стр. 2 из 15)

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

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

получен на базисе ; тогда последняя симплексная таблица имеет следующий вид:

Предположим, что

– дробное; тогда некоторые – также дробные (в противном случае задача не имеет целочисленного решения). Обозначим через и целые части чисел и , т. е. наибольшие целые числа, не превосходящие чисел и . Тогда величины дробных частей и чисел и определяются как разности:

где

и – неотрицательные.

Так как по условию

- неотрицательные целые числа, то и разность

(2.1.5)

также целое неотрицательное число.

Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную

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

Если в оптимальном плане несколько дробных

, то дополнительное ограничение составляется для максимального . Это ускоряет процесс получения оптимального целочисленного решения.

Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы:

1. Используя симплексный метод, находят решение задачи (2.1.1)-(2.1.3) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (2.1.1)-(2.1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (2.1.1)-(2.1.4) должна быть целочисленной.

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

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (2.1.1)-(2.1.4) или установления ее неразрешимости.

Метод ветвей и границ. Продолжим рассмотрение задачи (2.1.1)-(2.1.4),состоящей в определении минимального значения линейной функции

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

- целые.

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

. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и .

Если же среди компонент плана

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

Предположим, что найденный оптимальный план

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

При решении задач линейного программирования

и возможен один из следующих четырех случаев:

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

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам

и .

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

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

и .

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

и .

Итак, процесс нахождения решения задачи целочисленного программирования (2.1.1)-(2.1.4) методом ветвей и границ включает следующие основные этапы: