Студопедия
Карамелька - детский развивающий канал


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

I. Метод наименьшей стоимости




РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Решение открытой задачи сводится к решению закрытой

Лекция 12

Транспортная задача

Транспортные задачи – специальный класс задач линейного программирования. Эти задачи описывают перемещение (перевозку) какого-либо товара из пункта направления (например, места производства) в пункт назначения (склад или магазин). Назначение транспортной задачи – определение объемов перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок.

m
 
 
 
n
 
 
 
 
 
 
 
 
 
 
 
 

– количество поставщиков продукции;

– количество потребителей продукции;

– индекс для поставщиков;

– индекс для потребителей;

, – наличие продукции у каждого поставщика;

, – потребность в продукции каждого потребителя;

– стоимость доставки продукции единицы продукции от - поставщика к -потребителю.

Необходимо найти план доставки продукцию от поставщиков потребителям с минимальными транспортными издержками.

– задача называется закрытой

– задача называется открытой(с нарушенным балансом).

С этой целью при a < b добавляем фиктивного поставщика с запасом b-a. Если же a > b , то добавляем фиктивного потребителя с заказом груза a-b. В обоих случаях соответствующие фиктивным объектам тарифы перевозок cij полагаем равными нулю. В результате суммарная стоимость перевозок не изменяется.

Математическая модель

– решение задачи

Целевая функция

– целевая функция

Ограничения

, , ,


Этапы:

I. Построение начального базисного решения : метод северо-западного угла, метод наименьшей стоимости (минимального элемента), метод Фогеля.

II. Итеративный процесс поиска оптимального решения (метод потенциалов).

Общая транспортная задача с m пунктами отправления и n пунктами назначения имеет m+n ограничений в виде равенств, по одному на каждый пункт отправления и назначения. Т. к. транспортная задача д.б. сбалансированной, то одно из этих равенств избыточно. Т.о. транспортная задача имеет m+n+1 независимых ограничений, отсюда вытекает, что начальное базисное решение состоит из m+n+1 базисных переменных.

Пусть поставщиков продукции,

потребителей продукции

Запасы ,

Потребность

Затраты на перевозку продукции

  Запасы
Потребность

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




1)Выбор ячейки с наименьшим значением

Потребители Поставщики Запасы
Потребность

2)

Выбор ячейки с наименьшим значением

Потребители Поставщики Запасы
2| 15
Потребность

3)

Выбор ячейки с наименьшим значением

Потребители Поставщики Запасы
2| 15
4|5
Потребность

4)

Выбор ячейки с наименьшим значением

Потребители Поставщики Запасы
2| 15
9 | 15
4 |5
Потребность

5)

Выбор ячейки с наименьшим значением



Потребители Поставщики Запасы
2| 15
9 | 15
4 |5 18 | 5
Потребность

6)

Должно быть базовых переменных

Есть только 5, поэтому выбираем любую

Потребители Поставщики Запасы
2| 15 11 | 0
9 | 15 20 | 10
4 |5 18 | 5
Потребность

Первое допустимое решение

, , , , ,

Значение функции цели

30 135 200 20 90





Дата добавления: 2014-02-02; просмотров: 1415; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 8910 - | 6981 - или читать все...

Читайте также:

 

54.90.86.231 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.003 сек.