<<

Постановка задачи и алгоритм решения

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

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

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

Геометрически дополнительному ограничению соответствует гиперплоскость, которая отсекает от многогранника решений какую-то часть вместе с вершиной, которой соответствует нецелочисленное решение. При этом все точки с целочисленными координатами остаются в новом многограннике, так что через несколько операций такая точка становится вершиной с целочисленными координатами (рис. 13.1).

(координаты целые)

^Оі і

Пусть требуется найти максимум целевой функции

(13.1)

^тах = + Р2*2 + - + ЛЛ, при ограничениях

а\ 1*1 + <*12*2 +~.

+ а1„х„<а1

(13.2)

ат\х\ *ат2х2 + - + атпхп^ат Xj>О / = 1, П.

Не нарушая общности, можно предположить, что все коэффициенты системы (13.2) выражаются целыми числами. Приводим систему к виду

(13.3)

ах 1*1 + апх2 +... + а1пхп + ух = ах атххх + ат2х 2 + ...+ атпхп + Ут ~ ат

где yj — выравнивающие неизвестные.

Отметим, ЧТО целочисленность переменных Xj влечет за собой целочисленность переменных yg.

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

Таблица 13.1 Общий вид первой симплекс-таблицы решения задачи целочисленного программирования с

Б Свободный член Ух- Уе Хе+\ Хп Хх Ьх ьи Ь\п Хе ьел\ bu btn Уе+1 Ь?+\ b(t+1)1 b(t+Dt b?+1 \п Ут Ьт bm\- bmi bmn z

^тах Q Ях- Яе Яп

Если все свободные члены целые - задача решена. Для удобства все базисные переменные обозначим г)Д/ = 1,/и), а все свободные переменные = 1, п, тогда таблица примет вид (табл. 13.2):

Таблица 13.2 С

Б Свободный член і, Пі Ьх Ам- b\i] b\n Л/ bt bi ,... bv bin Лт Ьт bm і- bmj Ьщп 7

^тах Q Я\- 1] Яп

С целью упрощения в таблице опущены:

а) столбцы, соответствующие базисным переменным;

б) целевая строка;

в) контрольный столбец.

Пусть свободный член bt является дробным, в этой же строка среди коэффициентов by могут быть как дробные, так и целые. Обозначим буквой п с соответствующими индексами антье от by и Ь{.

Е(Ьу) = пу\ E(bj) = щ.

Вычислим разности между соответствующими коэффициентами и Е:

a h п <13'4)

Р i=bi~»r

Эти разности удовлетворяют условиям

0<|3,у(1;

0SM. <13'5)

Выпишем из таблицы выражение для г|, и заменим в нем коэффициенты согласно условию (13.4), тогда получим:

Л/ = 0/1 +Я/іМЧі) + - + (Рш + + л/;

л л (13.6)

Л/ = Е + 2 Ру(Чу)+Р/-

у=1 у= 1

Перепишем последнее выражение в другом виде

+ (13.7)

j J

Если и г),- — целые, то из правой части (13.7) следует, что 5/ — целое; так как ^ > 0; rj/ > 0, а из средней части (13.7) следует Si > -P/j учитывая выражение (13.5), заключаем, что St может принимать значения: 0, 1,2, ...

и т. д.

Вывод. При любых целых неотрицательных г], и St принимает целые неотрицательные значения.

Введем в задачу дополнительное ограничение (табл. 13.3), используя подчеркнутую часть выражения (13.7).

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

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

Б Х^ Свободный член їх... Лі bx bxx- bxij b\n Лт ~ЬтХ ~Ьц— -bmj ~bmn $ -р/ -Рп- -P* ~P/„ Z Q Ях- qj Я„

Если в какой-либо строке таблицы (кроме строки Z) свободный член дробный, а все прочие коэффициенты целые, целочисленных решений нет.

Пример

^max = 2*1 + х2 ~ Зх3; х\ + - 2х3 + Уі = 4;

5xj - х3 + >>2 = 12; 2х{ - х2 + Зх3 + = 4; xj>0]j= Ь_3; Л^О; /= 1, 3.

После двух шагов применения симплекс-метода приходим к оптимальному плану, представленному в табл. 13.4.

Решение оптимальное, но дробное х = (16/7; 4/7; 0).

Выбираем среди свободных членов дробный, например, 4/7 из первой строки. По формулам (13.6) находим коэффициент дополнительного ограничения:

Рп =-у-(-1)=|; Pi2 =|-о=|;

Р13=-1-(-1) = 0; pj =1-0 = 1

Ограничение Sj имеет вид: Уз У\ *з Свободный член *2 -1/7 2/7 -1 4/7 У2 -15/7 -5/7 -6 4/7 Х\ 3/7 1/7 1 16/7 Z 5/7 4/7 4 36/7 Введем это ограничение в табл. 13.4 и получим следующее:

Таблица 13.5 ^3 Уі *з , Свободный член *2 -1/7 2/7 -1 4/7 Уг -15/7 -5/7 -6 4/7 3/7 1/7 1 16/7 -6/7 -2/7 0 -4/7 Z 5/7 4/7 4 36/7 Применяя теорему, находим допустимое решение, представлен-ное в табл. 13.6.

Таблица 13.6 Уз *з Свободный член *2 -1 1 -1 0 Уг 0 -5/2 -6 2 0 1/2 1 2 У\ 3 -7/2 0 2 Z -1 2 4 4

Полученный план неоптимален (в последней строке имеются отрицательные элементы): после еще одного шага получаем оптимальный план, но нецелочисленный, поэтому составляем дополнительное ограничение по первой строке и получаем табл. 13.7. Уз *з Свободный член *2 1/3 -1/6 -1 2/3 Уг 0 -5/2 -6 2 0 1/2 1 2 Уъ 1/3 -7/6 0 2/3 -1/3 -5/6 0 -2/3 Z 1/3 5/6 4 14/3

Pll = і/з Pi2 = 5/6

Pi3 = 0

Pi =2/3

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

<< |
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме Постановка задачи и алгоритм решения: