Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры)




НазваниеРеферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры)
страница2/5
Дата публикации30.06.2013
Размер0.91 Mb.
ТипРеферат
zadocs.ru > Спорт > Реферат
1   2   3   4   5
^

Пример № 2.

Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности


Сетевой способ решения задачи не требует составления матрицы перевозок, а позволяет вести расчет прямо на схеме путей сообщения – сети.

Сеть состоит из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель внутри квадрата – номер вершины (станции) отправления, знаменатель – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) ci,j+1 между станциями i и j+1.

Условия задачи взяты из примера № 1. Схема (сеть) дороги с указанием объема отправления, прибытия вагонов и расстояния между станциями указаны на рис.1.





Рис. 1. Исходные данные к примеру № 2

Эта задача закрытого типа, так как суммарное количество избыточных пустых вагонов равно суммарному количеству требующихся вагонов (420 = 420). Математическая модель задачи будет выглядеть следующим образом.

Общее суммарное расстояние перевозки (целевая функция)

Система ограничений:


(i=1,2,3,4)


(j= 1,2..7)

xij ? 0, (i = 1,2,...,4; j = 1,2,...,7), где ai – ресурсы i-го пункта отправления; bj – потребность j-го пункта назначения.

Решение транспортной задачи в сетевой форме начинают с составления исходного плана.

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

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

Рис. 2. Исходный план перевозок

Начальное значение целевой функции (общее суммарное расстояние перевозки) для исходного плана перевозок составит

Lнач = 70· 15 +30· 70 + 50· 17 + 30· 11 + 40· 18 + 50· 25 + 30· 11 + 20· 9 + 60· 16 + 70· 17 = 7370 ваг-км.

Звенья называются базисными (занятыми), если по ним осуществляются перевозки. Направление перевозки указывается стрелкой, число около стрелки – объем перевозки по данному звену (количество вагонов) xj,j+1.
Алгоритм решения транспортной задачи, представленной в сетевой форме, методом потенциалов такой же, как и транспортной задачи, представленной в матричной форме:

1. Исходный опорный план проверяется на условие «вырождения».

Кз S – 1 ,                    (10)

где Кз – число занятых звеньев сети; S – число вершин, вошедших в полигон сети.

Данному условию должен отвечать любой план перевозок, в том числе исходный опорный план. Если это условие не выполняется, то исходный опорный план составлен неверно и необходимо найти замкнутый контур (или контуры) из базисных звеньев и “снять” с него минимальную перевозку.

Если Кз = S – 1 , задача решается обычным порядком.

Если Кз < S – 1 , задача называется “вырожденной” и распадается на несколько самостоятельных задач. Чтобы этого избежать, на свободные звенья назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие вырождения выполняется (10 = 11 – 1), поэтому задача не является “вырожденной “ и решается обычным порядком.

2. Начальный потенциал выбирается произвольно и присваивается произвольной вершине (рекомендуется начинать с наиболее удаленной вершины).

Первой вершине присваивается потенциал V1 = 100 ( см. рис. 2).

3.Через занятые базисные звенья определяют потенциалы каждой последующей вершины Vj+1, связанной с предыдущей вершиной Vj по формулам:

перевозка “попутная”

Vj+1 = Vj + cj,j+1,              (11)

перевозка “встречная”

Vj+1 = Vj - cj,j+1,              (12)

где cj,j+1 – критерий расстояния (или другой показатель критерия оптимизации) на заданном звене.

4. Пункт 3 повторяется до тех пор, пока всем вершинам сети не будет присвоен потенциал. Это возможно, если выполняется условие «вырождения» Кз = S – 1. Звенья с фиктивными перевозками рассматриваются как занятые.

Исходя из формулы (11), потенциал вершины 5 будет равен V= 100 + 15 =115, а потенциал вершины 2 равен V2 = 100 + 17 = 117. Далее присваиваются потенциалы от вершин 5 и 2. Вершина 5 не имеет связующих (занятых) звеньев ни с одной из вершин сети. Вершина 2 связана с вершиной 6 (V6 = 117+17 = 134), вершиной 8 (V8 = 117 + 11 =128), вершиной 11 (V11 = 117+18 = 135) и вершиной 9 (V9 = 117 +11 = 128). От вершины 11 по формуле (12) определяется потенциал вершины 4 (V= 135 – 25 =110). От вершины 9 определяется потенциал вершины 3 (V3 = 128 – 9 = 119). От вершины 3 определяются потенциалы вершины 10 (V10 = 119 + 17 = 136) и вершины 7 (V7 = 119 + 16 = 135). Присвоенные потенциалы обозначены подчеркнутой цифрой около вершины (рис.2).

5. Полученный начальный план проверяется на оптимальность. План считается оптимальным, если соблюдаются следующие условия:

/Vj+1 – Vj /≤ cj,j+1, при xj,j+1 = 0 (звено свободно),               (13)

/ Vj+1 – Vj /= cj,j+1, при xj,j+1 > 0 (по звену назначена перевозка).

В нашем примере для звена 5–2 условие оптимальности выполняется (/115 – 117/ = 2 < 24), а для звена 5–6 – не выполняется (/134 – 115/ = 19 > 12) и нарушение составляет 7. Аналогично, имеются нарушения на звене 1–7 (/135 – 100/ = 35 > 28) и звене 8–4 (/110 – 128/ = 18 > 16). Нарушения соответственно 7 и 2. Для остальных звеньев условие оптимальности выполняется. Данный план не является оптимальным, так как имеются нарушения условия оптимальности [см. формулу (13)].

6. Корректировка плана производится в следующей последовательности:

а) строится замкнутый контур, состоящий из звена с наибольшим нарушением, и базисных звеньев: (5–6) – (6–2) – (2–1) – (1–5);

б) выбирается направление движения по контуру от вершины звена с нарушением, имеющей меньший потенциал, к вершине с большим потенциалом (от вершины 5 к вершине 6) и далее по выбранному контуру;

в) определяется минимальная встречная перевозка в данном контуре: min {50;30} = 30 в звене (1–2). Это значение принимается для дальнейшей корректировки;

г) “обходится” контур по выбранному направлению и вычитается найденное значение из всех встречных потоков, прибавляется к попутным. При этом звено 2–1 освобождается от перевозки, а на звеньях вне контура перевозки остаются без изменений (рис. 3).16 20 50 18

Рис. 3. Скорректированный план перевозок (первая корректировка)

Значение целевой функции составит

L = 100· 15 + 30· 12 + 20· 17 + 30· 11 + 30· 11 + 40· 18 + 50· 25 + 20· 9 + 70· 17 +  60· 16 = =7160 ваг-км.

Согласно алгоритму решения транспортной задачи, представленной в сетевой форме, методом потенциалов (пункты 1–5), данный скорректированный план также проверяется на оптимальность [формулы (10–13)].

В данном плане имеется нарушение условия оптимальности [см. формулы (13)] в звене 4–8 (/121 – 103/ = 18 > 16). Поэтому согласно пункту 6 алгоритма решения транспортной задачи, представленной в сети, методом потенциалов корректируется план перевозок (рис. 4).



Рис. 4. Скорректированный план перевозок (вторая корректировка)

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

Конечное значение целевой функции составит

Lкон = 100· 15 + 30· 12 + 20·17 + 30· 11 + 70· 18 + 30· 16 + 2· 25 + 20· 9 + 70· 17 + 60· 16 = 7100 ваг-км.

Как видно из расчетов, итоговый план перевозок улучшен по сравнению с исходным на 270 ваг-км (Lнач – Lкон = 7370 – 7100).

ревозок) относительно начального плана на 20 ваг-км (5790 – 5770 = 20).

1   2   3   4   5

Похожие:

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение задач линейного программирования Цель работы
Цель работы: Изучение возможностей пакета Ms Excel при решении задач линейного программирования. Приобретение навыков решения задач...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconКафедра экономико-математических методов и вычислительной техники...
Алгоритм решения задач линейного программирования симплексным методом: Методические указания студентам направления 100700 «Торговое...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconТранспортная задача
Методические указания предназначены для студентов дневного и заочного отделения по направлениям: 250300, 190700, 250400. В методических...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconИсследование операций” Модель и эффективность операции
Индивидуальные задания для решения задач линейного программирования графическим методом

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПонятие программы и программирования. Свойства программ. Назначение...
Системы счисления. Сущность перевода чисел из одной системы счисления в другую: примеры

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПрограммирование для начинающих turbo Pascal 0
В практической части рассмотрены основы алгоритмизации решения задач и их программирования на языке Паскаль. Приводятся примеры разработки...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение. Часть 1
Конституции РФ. Тест состоит из двух частей: первая часть состоит из 20 простых вопросов, на которые предусмотрен только один ответ;...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение: в 1954 г в компании ibm под руководством Джона Бэкуса был...
Тема: Эволюция и классификация языков программирования. Основные понятия языков программирования

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconЗадачи курса изучение языка программирования Турбо-Паскаль в объеме,...
Знакомство с методами отладки программ. Реше- ние задач с использованием основных пакетов прикладных программ

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПрактикум по решению линейных задач математического программирования
Акульшина Т. С., Стебко Т. В. Практикум по решению линейных задач математического программирования. – Симферополь, уэу, 2006 – 44...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов