XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 26
Текст из файла (страница 26)
В чем заключается принципиальное отличие метода ветвей и границ от метода полного перебора? 4.9. П риведите обоснование того, что реализация вариантов действий, указанных в замечании 4.1, приведет к ускорению процесса нахождения оптимального решения.
4,10. г . С чем связаны основные недостатки метода ветвей и границ? 4.11. .11. Чем обусловлен нелинейный характер целевой функции у (Х) в задаче планирования производства с постоянными элементами затрат, рассмотренной в 4.4? 187 Вопроси и задачи 186 4. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 4.12, Дана полностью целочисленная задача 20хг + 10хг+ 10хз -4 шах; 2хг + 20хг+ 4хз ( 15, бхг + 20хг + 4хз = 20, х1, хг, хз) О, хмхг, хэви 1ЧО(0). Докажите, что решение этой задачи нельзя получить методом округления.
4.13, На примере полностью целочисленной задачи х, + 2хг -+ шах; хг+0,5хг (3,25, хг, хг ) О, х1, хг 6 1ч0(0), покажите, что метод Гомори для полностью целочисленной задачи не приводит к оптимальному решению, если не выполняется требование целочисленности значений ее параметров. Преобразуйте рассматриваемую задачу и методом Гомори найдите ее оптимальное решение. Ответ: Х' = (О 6) .
4.14. Методом Гомори найдите оптимальное решение полностью целочисленной задачи Зх1+ хг+Зхз -+ шах; — хг+2хг+хз < 4, 4хг — Зхз <2, хг — Зхг+2хз < 3, х„х„х,) О, хд, х„хз 6 МО(0). Ответ: Х'= (5 2 2) . 4.15. Докажите правомочность использования в методе Гомори отсечения, определяемого согласно (4.24). 4.16. Пусть в задаче 4.14 требование целочисленности наложено только на переменные модели хг и хз. Методом Гомори найдите оптимальное решение этой частично целочисленной задачи. Ответ: Х" = (5 11/4 3) . 4.17.
В примере 4.7, игнорируя замечание 4.1, продолжите процесс ветвления из вершины 5 дерева решений, представленного на рис. 4.7. Единственно ли оптимальное решение исходной полностью целочисленной эадачи7 Ответ: нет. Оптимальному значению целевой функции у = 14 соответствуют оптимальные решения Х~ — — (4 2) и Хг —— =(7 О) . 4.18, Методом ветвей и границ найдите все оптимальные решения следующей полностью целочисленной задачи: хг + хг -+ шах; 2хг + 5хг ( 16, бх1+ 5хг ( 30, хг, хг ) О, хг, хг 6 МО(0). Ответ: оптимальному значению целевой функции 7" = 5 соответствуют оптимальные решения Хг" = (5 0), Хг —— (4 1) Х" = (3 2) .
4,19. Методом ветвей и границ найдите оптимальное решение следующей полностью целочисленной задачи: Зхг+Зхг+13хз -+ шах; — Зхг + бхг+ 7хз ( 8, бх1 — Зхг Ф 7хз ( 8, хг, хг, хз ) О, хг, хг, хз 6 М 1.1 (О). Ответ: Х'= (О 0 1) 5.!. Классическая транс!тертнал задача 5.1. Классическая транспортная задача 189 5. ЗАДА'ЧИ ТРАНСПОРТНОГО ТИПА Эта глава посвящена изучению задач линейного программирования, известных в исследовании операций как задачи транспортного типа.
Интерес к этим задачам обусловлен не только спецификой их формализации и прикладной значимостью, но и рядом других причин, среди которых отметим следующие. 1. Любая задача транспортного типа, как задача линейного программирования, может быть решена симплекс-метподом. Однако специфические особенности задач рассматриваемого класса позволили разработать более эффективные вычислительные методы. А поскольку в реальных задачах транспортного типа число ограничений и переменных, как правило, бывает весьма значительным, то использование эффективных вычислительных алгоритмов становится не только выгодным, но и просто необходимым.
2. Для задач транспортного типа естественным и удобным является их геометрическое представление в виде графа специального вида. Это представление в ряде случаев позволяет преобразовывать к задачам транспортного типа даже такие задачи исследования операций, которые на первый взгляд не имеют с ними ничего общего, и использовать для их решения эффективные вычислительные алгоритмы.
3. Задачи транспортного типа тесно связаны с детерминированными динамическими задачами исследования операций, в том числе и с мнагошаговыми задачами принятия решений в условиях определенности, имеющими большое прикладное значение. Изучение задач транспортного типа начнем не с их формального определения, а с обсуждения математической постановки классической транспортной задачи.
с; х; — тш1п; Е ~=! 1=1 Е х;,=5;, т=1,т, (5.2) ху — — О., 1=1,п, Е хз>0, т=1,т, т'=1,п. В исследовании операций под тпранспорптной задачей обычно понимают задачу выбора плана перевозок некоторого товара (изделий, груза) от т источников (пунктов производства, поставщиков) к и сто!сам (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что: а) мощность т-го источника (объем поставок товара от т-го источника) равна 5! > О, ! = 1, т; б) мощностпь т'-го стона (объем поставок товара к тьму стоку) равна 1л > О, т'= 1, и; в) стоимость перевозки единицы товара (в условных денежных единицах) от т-го источника к ~-му стоку равна с;", г) суммарная мощность всех источников равна суммарной мощности всех стоков, т.е.
ет е Е =Е' ('5 . 1 ) Ье! т=! Далее под объемом товара будем понимать его количество в фиксированных единицах измерения. Для математического описания транспортной задачи вводят переменные хт, обозначающие объемы поставок товара от т-го источника к у-му стоку. В этом случае хт+хтз+... +х,„— общий объем поставок товара от т-го источника, т.е. мощность этого источника; хту+ хз +... + х — общий объем поставок товара к т-му стоку, т.е.
мощность этого стока; спхы+сшхтз+...+с „х „— суммарная стоимость перевозок товара от источников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде: 191 хы ... х1 ... х,„ (5.3) Х = х11 " хй ... х;„ х 1 ... х ... х (5.4) Таблица 5.1 (5.5) х; = О , 1 = 1,п. Е 1=1 (5.6) 190 5. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Заменание 5,1. Один из важнейших теоретических результатов исследования операций может быть сформулирован следующим образом (см.
теорему 5.3): если выполнены условия о;ЕМ, 1=1,т, В1 ЕМ, 1'=1,п, то среди всех оптимальных решений транспортной задачи (5.2) по крайней мере одно оптимальное решение удовлетворяет требованию целочисленности. В дальнейших рассуждениях мы всегда будем предполагать выполнение условий (5.3). В этом случае транспортную задачу можно рассматривать как полностью целочисленную задачу, поскольку введение дополнительного ограничения не может повлиять на опгаи,нальное значение целевой функ- ции. В исследовании операций полностью целочисленную зада- чу (5.2), (5.4) называют нлассичесной транспортной за- дачей. Рассмотрим более подробно ограничения типа равенства, входящие в задачу (5.2): Заметим, что каждое переменное модели х; с ненулевым коэффициентом, равным единице, входит лишь в 1-е уравнение системы (5.5), соответствующее 1-му источнику (поставки), и в 1ье уравнение системы (5.6), соответствующее 1'-му пункту ВЗ.
Классическая транепортнав эадвча потребления (спрос). Поэтому, если ввести матрицу пере- менных модели (5.2), (5.4) то легко увидеть, что элементы ее 1-й строки с коэффициентами 1 входят в 1-е уравнение системы (5.5), отражающей мощность источников, а элементы 1'-го столбца с коэффициентами 1 входят в 1-е уравнение системы (5.6), отражающей спрос потребителей.
Таким образом, классическую транспортную задачу (5.2), (5.4) можно представить в виде так называемой тпранспортпной таблицы (табл. 5.1). Эта таблица соответствует матрице переменных модели Х, в которую добавлен один столбец (поставки) и одна строка (спрос), а в правой половине клетки, соответствующей каждому переменному х;,, вписано соответствующее значение сб. Заметим также, что при решении транспортных задач транспортные таблицы играют ту же роль, что и симплекс-таблицы при решении задач линейного программирования.
193 Л.1. Классическая транспартнав эадача 192 Л. ЗАДА ЧИ ТРАНСПОРТНОГО ТИПА Если каждое уравнение системы (5.6) умножить на — 1, то вид системы ограничений в классической транспортной задаче (5.2), (5.4) изменится. В этом случае для ее наглядного представления используют табл. 5.2, отличную от транспортной таблицы. Таблица 5.с В каждом столбце табл. 5.2, соответствующем переменному х! (2 = 1, т, 1' = 1, и), содержится лишь два ненулевых коэффициента 1 и -1, так как свободные места соответствуют нулевым коэффициентам. Коэффициент 1 соответствует 1-му источнику (пункт производства), а коэффициент — 1 — лчму стоку (пункт потребления или станция назначения). По табл.
5.1, как и по табл. 5.2, можно полностью восстановить классическую транспортную задачу. Действительно, согласно соотношениям (5.2), (5.4), для этого нужно лишь знать; а) значение е;- стоимости перевозки единицы товара от !чго к 1-стоку (в табл. 5.1 эта информация указана в правой половине соответствующих клеток, а в табл. 5.2 — в последней ее строке); б) значение 5, мощности каждого 2-го источника (в табл. 5.1 и 5.2 эта информация представлена в последнем столбце); в) значение В мощности каждого 1-го стока (в табл. 5.1 эта информация дана в последней строке, а в табл. 5.2 — в последнем столбце).
Для удобства геометрической интерпретации классической транспортной задачи, представленной в табл. 5.2, каждый 1'-й сток и каждый 2-й источник изобразим в виде уээва се222и, т.е. в виде окружности, в центре которой укажем его мощность ( — В. для 1'-го стока и э, для 2-го источника). Если узел сети, соответствующий 2-му источнику (2 = 1, т), соединить ориен- -О тированной дугой с узлом сети, соот- 11 ! ветствующим 1-му стоку (2 = 1, п), и а1 сгл см на этой дуге указать стоимость с, пе- б О2 ревозки единицы товара от 2-го пункта производства к 1-му пункту по- Я С22 требления, то получим представление Оэ рассматриваемой задачи в виде сети.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
