Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задание 6. Поместить исходные данные задачи в форму:
|
|
Поместить исходные данные задачи в форму:
Форма исходных данных для ТЗ
| Пункт отправления | Пункт назначения | Запасы | ||||
| B1 | B2 | B3 | B4 | B5 | ||
| A1 | с11= | c12= | c13= | с14= | c15= |  =
|
| A2 |  =
|  =
|  =
|  =
|  =
|  =
|
| A3 |  =
|  =
|  =
|  =
|  =
|  =
|
| A4 |  =
|  =
|  =
|  =
|  =
|  =
|
Потребность 
|
 =
|  =
|
 =
|
 =
|
 =
|
Решить транспортную задачу методом потенциалов, предварительно построив исходные распределительные таблицы и исходные опорные планы (аккуратно выписывать все промежуточные таблицы).
Исходные данные для ТЗ.
Задача:
Имеется 4 склада содержащие некоторое количество единиц однотипной продукции (см.таблицу 1), имеется также 5 потребителей нуждающихся в определенном количестве данной продукции (см.таблицу 2). При перевозке одной единицы продукции со склада i потребителю j возникают издержки Pij. Величины издержек приведены в таблице 3. При перевозке K единиц продукции со склада i потребителю j суммарные затраты на перевозку составляют K*Pij.
Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны.
Таблица 1
| Таблица 2
|
Таблица 3
Издержки на перевозку единицы продукции со склада i потребителю j
| Потребители | |||||
| Склад № | |||||
Шаг: 1
Проверка на сбалансированность
| Общее число запасов на складах: | ; Общая потребность: |
Задача являетя сбалансированной (закрытой).
Шаг: 2
Отыскание начального решения. Метод северо-западного угла
Запишем настоящую задачу в виде транспортной таблицы. В верхней строке перечислим потребности потребителей по порядку номеров. В левом столбце перечислим имеющиеся запасы на складах. На пересечении j-го столбца и i-й строки будем записывать количество продукции, поставляемое с i-го склада j-му потребителю. Пока начальное решение не найдено, оставим эти клетки пустыми.
|
|
|
|
| |||||||||||
| |||||||||||||||
| |||||||||||||||
| |||||||||||||||
|
Введем вспомогательные строку и столбец, в которых будем отмечать оставшиеся нераспределенные запасы и соответственно потребности (остатки). Изначально их содержимое равно исходным запасам и потребностям, так как еще ничего не распределялось. На рисунке они представлены желтым цветом.
Выберем клетку в которую будем распределять продкуцию на следующей итерации, это левая верхняя клетка (севрозападный угол). На рисунке как сама клетка так и соответсвующие ей остатки отображаются красным шрифтом.
|
|
|
|
| ||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Итерация: 1
Заполним клетку a1, b1.
Сравним значения остатков для производителя a1 и потребителя b1.
Нераспределенных остатков по потребностям для b1 меньше (см. таблицу выше, красный шрифт), запишем меньшее число в клетку a1, b1 одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по потребностям обнулится указывая, что все потребности для b1 удовлетворены (см. таблицу ниже). Поэтому исключим столбец b1 из дальнейшего рассмотрения (серый фон).
Ненулевое значение остатка по запасам для a1 показывает, сколько единиц продукции у него осталось не потребленной.
|
|
|
|
| ||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Итерация: 2
Заполним клетку a1, b2.
Сравним значения остатков для производителя a1 и потребителя b2.
Нераспределенных остатков по потребностям для b2 меньше (см. таблицу выше, красный шрифт), запишем меньшее число в клетку a1, b2 одновременно вычитая его из обеих клеток остатков (см. таблицу ниже). При этом клетка остатков по потребностям обнулится указывая, что все потребности для b2 удовлетворены (см. таблицу ниже). Поэтому исключим столбец b2 из дальнейшего рассмотрения (серый фон).
Ненулевое значение остатка по запасам для a1 показывает, сколько единиц продукции у него осталось не потребленной.
|
|
|
|
| ||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Итерация: 3
|
|
|
|
| ||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Итерация: 4
|
|
|
|
| ||||||||||||
| ||||||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Итерация: 5
|
|
|
|
| ||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| X | |||||||||||||||
| ||||||||||||||||
Итерация: 6
|
|
|
|
| ||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| X | |||||||||||||||
Итерация: 7
|
|
|
|
| ||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| X | |||||||||||||||
Итерация: 8
|
|
|
|
| ||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
| ||||||||||||||||
Получено допустимое начальное решение (опорный план) (см. таблицу ниже), удовлетворенны нужды всех потребителей и использованы все запасы производителей.
|
|
|
|
| |||||||||||
| |||||||||||||||
| |||||||||||||||
| |||||||||||||||
|
Шаг: 3
Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=8, n+m=5+4=9, что удовлетворяет условию невырожденности плана.
Шаг: 4
Вычислим общие затраты на перевозку всей продукции. Для этого запишем транспортную таблицу в которой совместим найденный опорный план с величинами издержек. В левом верхнем углу каждой клетки будем указывать количество единиц продукции а в правом нижнем затраты на перевозку единицы продукции. (см. таблицу ниже)
|
|
|
|
| |||||||||||||||||||||||
|
|
|
|
|
| ||||||||||||||||||||||
|
|
|
|
|
| ||||||||||||||||||||||
|
|
|
|
|
| ||||||||||||||||||||||
|
|
|
|
|
|
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения.
| Pнач= |
Шаг: 5
Проведем поэтапное улучшение начального решения, используя метод потенциалов.