<<

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

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

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

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

Геометрически дополнительному ограничению соответствует гиперплоскость, которая отсекает от многогранника решений какую-то часть вместе с вершиной, которой соответствует нецелочисленное решение. При этом все точки с целочисленными координатами остаются в новом многограннике, так что через несколько операций такая точка становится вершиной с целочисленными координатами (рис. 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

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

  1. ТЕСТ 6.1 Оценка способностей к принятию творческих ответственных управленческих решений
  2. Решение логических задач
  3. 4.4. Информационный способ оценки принятого решения
  4. 1.4 Основные выводы по литературному обзору и постановка задачи исследования
  5. 1.3.2 Математическая формулировка задачи обработки навигационных измерений навигационного приемника при потере свойств целостности СРНС
  6. 3.4 Аналитическое исследование эффективности алгоритма на модельной задаче
  7. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  8. 3.1. Методы решения образовательных, развивающих и воспитательных задач
  9. 3.3. Формы педагогического взаимодействия при решении образовательных, развивающих и воспитательных задач
  10. Технология выработки и реализации управленческих решений.
  11. Постановка задачи и алгоритм решения
  12. Тактические принципы и методика экспертиз при решении ситуационных задач.
  13. ОРГАНИЗАЦИЯ РАЗРАБОТКИ ТЕХНИЧЕСКОГО ПРОЕКТА
  14. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ИСПОЛЬЗОВАНИЯ РЕКУРРЕНТНЫХ СХЕМ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ В ЗАДАЧАХ ФИНАНСОВОГО АНАЛИЗА
  15. ЗАДАЧА О НАЗНАЧЕНИЯХ
  16. 4. Методы расщепления для прикладных задач математической физики
  17. Симплекс-метод. Основная идея, этапы поиска решений, алгоритм метода.
  18. Лекция 1. Предмет теории принятия решений.
  19. Краткий обзор методов решения задачи векторной оптимизации