Математические методы исследования операций в экономике (стр. 25 из 37)

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же соображениями, что и на итерации 3, пометим вершину 5 числом m₅ =3 (рис. 3.9). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Из чего определяем ∆ = min{

_4,6,

_5,6}=2 и после преобразования имеем

_4,6 =3,

_5,6 =0.

Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m₆=5 (см. рис. 3.10). Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).

Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет несколько решений.

КЛЮЧЕВЫЕ ПОНЯТИЯ

- Транспортная таблица

- Метод северо-западного угла.

- Потенциал.

- Цепочка преобразования плана.

- Граф (ориентированный и неориентированный).

- Ребра и вершины.

- Путь и контур.

- Цепь и цикл.

- Связность.

- Дерево.

- Частичный граф.

- Транспортная сеть.

- Поток.

- Линейная сетевая задача.

- Остов сети.

- Опора потока.

- Невырожденный поток.

- Задача о кратчайшем пути.

- Алгоритм Минти.

КОНТРОЛЬНЫЕ ВОПРОСЫ

3.1. Какие специфические свойства позволяют выделить транспортные задачи в отдельный класс из

множества задач линейного программирования?

3.2. Опишите метод построения допустимого плана транспортной задачи.

3.3. Сколько ненулевых элементов должен содержать невырожденный базисный план транспортной

задачи?

3.4. Сформулируйте критерий оптимальности для допустимого плана транспортной задачи.

3.5. Что положено в основу метода потенциалов?

3.6. Из чего вытекает критерий оптимальности допустимого плана транспортной задачи?

3.7. Перечислите основные этапы метода потенциалов.

3.8. Какие условия должны быть соблюдены при построении цепочки преобразования плана в методе

потенциалов?

3.9. Что следует делать при возникновении ситуации вырожденности текущего плана в транспортной

задаче?

3.10. Приведите формулировку линейной сетевой задачи.

3.11. Покажите, что транспортная задача в матричной постановке является частным случаем

транспортной задачи в сетевой постановке.

3.12. Дайте определение понятия «остов сети». Какая связь существует между остовом сети и

базисом транспортной задачи в сетевой постановке?

3.13. Какой поток называют невырожденным?

3.14. Перечислите основные этапы метода потенциалов для транспортной задачи в сетевой

постановке.

3.15. Каким способом можно получить допустимый поток в транспортной сети?

3.16. В чем состоит задача о кратчайшем пути?

3.17. Перечислите основные этапы метода Минти.

ГЛАВА 4. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

4.1.1. Основные понятия. Многие экономические задачи характеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуаций приводит к моделям дискретного программирования. В общем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или минимума) целевой функцииf(x₁, x₂,...,x_n) на множествеD, определяемом системой ограничений

где Ω— некоторое конечное, или счетное*, множество. Условие х∊Ω. называется условием дискретности. Особое место среди дискретных задач занимает целочисленная задача линейного программирования в канонической форме (ЦКЗЛП):

* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.

где Z⁺ ={0; 1; 2; ...} — множество неотрицательных целых чисел.

Заметим, что в некоторых ситуациях требование «целочисленности» может быть наложено лишь на некоторые переменныеx_j, что кардинально не меняет характера задачи.

Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным аналогом и, найдя соответствующее решение, округлить его компоненты до ближайших целых значений. Пример, показанный на рис. 4.1, демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП до целых значений получается точка ([х₁*],[x₂^*]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа х_j. обозначать [х_j], а дробную — как {х_j}. Тогда х_j =[х_j]+{х_j}. Отдельно следует добавить, что если даже оптимальный план непрерывной задачи,округленный до целых значений компонент, окажется допустимым, то целевая функция может вести себя так, что ее значение будет на нем существенно «хуже», чем на оптимальном плане целочисленной задачи.

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

- задачи с неделимостями;

- экстремальные комбинаторные задачи;

- задачи с разрывными целевыми функциями;

- задачи на несвязных и невыпуклых областях и др.

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

Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула носит достаточно условный характер и состоит в том, что солдат (или турист), собирающийся в поход, может нести груз весом не болееW кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j веситw_j кг и характеризуется некоторой «полезностью» u_j, j∊ 1: n. В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была максимальной? Если в качестве компонент плана х_j. принять количество укладываемых предметов типа j, то данную задачу можно записать:

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

4.1.3. Комбинаторные задачи. К данному классу относятся задачи оптимизации функции, заданной на конечном множестве, элементами которого служат выборки из n объектов.

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

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

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

элементы которой определяются следующим образом:

1, если в маршруте предусмотрен переезд из пунктаi в j,

x_i,j = 0, если в маршруте не предусмотрен переезд из пункта i в j,