![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
II. Решить транспортную задачу ⇐ ПредыдущаяСтр 2 из 2
Транспортная задача (ТЗ) формулируется следующим образом. В m пунктах отправления А 1... A m сосредоточен однородный груз в количествах соответственно а 1... а m единиц. Имеющийся груз необходимо доставить потребителям В 1... В n, спрос которых выражается величинами b 1... b п единиц. Известна стоимость с ij перевозки единицы груза из i -го пункта отправления в j -й пункт назначения. Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются. Для наглядности условия ТЗ можно представить таблицей (табл. 1.), которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ. Цель ТЗ — минимизировать общие затраты на реализацию плана перевозок. Итерационный процесс по отысканию оптимального плана транспортной задачи начинают с опорного плана, который находят методом северо-западного угла. Решение задачи осуществить методом потенциалов с помощью программы Optimal.
Представление транспортной задачи в матричной форме
Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Помещаем в клетку (1, 1) меньшее из чисел A1*=40 и B1*=30
Этап 1
Опорный план является вырожденным, так как число занятых клеток меньше, чем m+n-1=7. Сделаем его невырожденным, поместив базисные нули в клетки с координатами (i, j): (2, 4)
Определяем значения оценок Si, j=Ci, j-(Ui+Vj) для всех свободных клеток: Так как все оценки Si, j > =0, то полученный план является оптимальным.
|