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

Оценкиимеют следующие значения:7;2;2;3;2.Положительная оценка соответствует коммуникации (5,8), на которой мы изамкнем цикл пересчета:

Определим величину корректировки min8, 688. Коммуникацию (8,5) включаем в базис, а (9,7) исключаем из базиса. Изменим перевозки вцикле. Получим план X3 (рис.

7).Рис. 7 — План Х3Для плана X3 заново вычислим потенциалы и оценки. Пусть a20,тогда: a3033;a6341;a1121;a4022;a5242;a7253;a8246;a9422;Оценки имеют вид:7; 2;2;3; 2.Положительных оценок нет, план X3 оптимален. Минимальноезначение функции равно f3732.В процессе решения сетевой задачи могут возникнутьследующие ситуации:

1) при построении пробного плана число базисных ребер меньше, чем m1;2) несколько наибольших положительных оценок;

3) величина корректировки достигается на нескольких перевозках;

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

5) наибольшая положительная оценка находится на ребре только чтовышедшем из базиса. В первом случае в базис вводятся фиктивные перевозки, получаетсявырожденный опорный план. Зацикливание при решении сетевой задачипроисходит крайне редко, поэтому с базисными нулями можно обращатьсятакже как и с положительными перевозками. Во втором случае выбор разрешающего ребра произволен, но чаще извсех претендентов выбирают то ребро, которому соответствует меньшаяудельная стоимость перевозки. В третьем — из базиса можно исключить только одно ребро, поэтомувыводят ребро с большей удельной стоимостью перевозки. Остальнымпретендентам будут соответствовать базисные нули, при этом направлениефиктивных перевозок должно оставаться прежним. Четвертая ситуация свидетельствует о том, что наряду с полученнымоптимальным планом существуют альтернативные оптимальные планы. В пятом случае говорят, что мы не только не то количество груза везем, но еще и не в ту сторону. Разрешающая стрелка должна быть направлена впротивоположную сторону по отношению к перевозке, только что вышедшейиз базиса предыдущего опорного плана. Графическое решение транспортной задачи достаточно трудоемко особенно при большем графе, поэтому для решения транспортной задачи в сетевой постановке используют различные программные комплексы. Среди них множество разработано в качестве небольших приложений с среде программирования Паскаль, Delphi, C++ и др. Однако наиболее простым решением является использование приложения ExcelMSOffice. Данный программный продукт располагает таким приложением как «Пакет анализа — Поиск решения». Рассмотрим решение вышеприведенной задачи с помощью данного пакета анализа.

Т.к. задать графически задачу в программе мы не можем, то для решения задачи необходимо свести ее к матричной форме, задав в виде матрицы продолжительность или стоимость перевозки, а в виде векторов — произведенное и требуемое количество материалов. Далее для решения задачи необходимо запустить пакет анализа «Поиск решений». В открывшемся окне задаем необходимые ограничения и нажимаем кнопку «Выполнить» (рис. 8).Рис. 8 — Задание необходимых параметров модуля «Поиск решений» В результате получаем необходимое решение задачи:

Таблица 1Исходные данные Поставщики 25 681 347

Требуется

Потребители180 200 005 183 303 990 169 375 316 281 700 130 568 497 552 199 655 382 321 303 131 085 000 933 376

Произведено397 537 680 000

Таблица 2Решение транспортной задачи Поставщики 25 681 347

Получено

Потребители100 180 000 018 331 024 656 830 848 597 260 145 483 065 462 456 706 761 799 982 156 097 156 791 792 566 272

Вывезено398 337 600 000

Остаток0−8 080 000

Целевая функция =732Таким образом, решение, полученное аналитически путем анализа графа, полностью совпадает с решением, полученным в Excelпри помощи функции «Поиск решений».

Заключение

На основании изложенного в курсовой работе можно сделать следующие выводы. Транспортная задача в сетевой постановке представляет собой графическое отображение классической транспортной задачи. Исходными данными для расчета являются объемы производства или запасов, объемы потребления некоторых объектов (узлов), а также пути от этих узлов, характеризующиеся стоимостью перевозки или ее длительностью. Целью решения транспортной задачи является составление такого плана перевозок, чтобы удовлетворитьзапросы всех потребителей и при этом суммарные затраты на перевозку былиминимальны. Различия между транспортными задачами в матричной и сетевой постановкахвесьма незначительны и методы их решения основаны на одних и тех же идеях. Алгоритм решения транспортной задачи в сетевой постановке состоит из следующих пунктов:

1. Построение пробного опорного плана2. Вычисление потенциалов3. Проверка плана на оптимальность4. Построение нового плана

Расчеты и анализ повторяются до тех пор, пока не будет получено оптимальное решение, т. е. до тех пор, пока все оценки не будет отрицательными. В курсовой работе изложены последовательно все этапы расчета на примере задачи, а также приведен расчет этой задачи при помощи приложения ExcelMSOffice. Решение, полученное аналитически путем анализа графа, полностью совпадает с решением, полученным в Excelпри помощи функции «Поиск решений». Список использованной литературы

Аксентьев В. А. Сборник задач по математическим методам в экономике. Учебное пособие для студентов экономических специальностей. Тюмень: издательство Тюм

ГУ, — 2003, 264 с. Аксентьев В. А., Пыткеев Е. Г., Хохлов А. Г. Математические методы в экономике и финансах. Учебное пособие для студентов экономических специальностей дистанционной формы обучения. Тюмень: издательство Тюм

ГУ, 2007. — 600 с. Акулич И. Л. Математическое программирование в примерах и задачах. «Высшая школа», 1986. — 318 с. Сборник задач по высшей математики дл экономистов: Учебное пособие / Под ред.

В.И. Ермакова. — М.: ИНФРА-М, 2001. — 575 с. Таха Хэмди А.

Введение

в исследование операций, 7-е издание.: Пер. с англ. -

М.: Издательский дом «Вильямс», 2005. — 902 с. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. — 2-е изд., исправленное.

— М.: «Дело», 2002. — 440 с.