Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Транспортная задача в матричной постановке





 

Имеется n пунктов производства и m пунктов потребления некоторого однородного продукта. Заданы объемы производства a[i], iÎ [1..n], в каждом пункте производства и размеры спроса b[j], jÎ [1..m] в каждом пункте потребления. Известны также транcпортные расходы c[i, j], связанные с перевозом единицы продукта из пункта i в пункт j. Требуется определить объемы перевозок x[i, j] из i -го пункта в j -ый для всех iÎ [1..n], jÎ [1..n], при минимальных общих транспортных издержках, при этом весь груз из пунктов производства должен быть вывезен, и весь спрос в пунктах потребления должен быть удовлетворен.

Дадим математическую постановку транспортной задачи:

L(x)= S {с[i, j]´ x[i, j] | iÎ [1..n], jÎ [1..n]} ® min

при ограничениях

S { x[i, j] | jÎ [1..m]} = a[i] для всех iÎ [1..n], (5.6)

S { x[i, j] | iÎ [1..n]} = b[j] для всех jÎ [1..m], (5.7)

x[i, j]³ 0, для всех iÎ [1..n], jÎ [1..m]. (5.8)

Транспортная задача имеет решение тогда и только тогда, когда выполняется соотношение:

S { a[i] | iÎ [1..n]} = S { b[j] | jÎ [1..m]}, (5.9)

т.е. объем производства должен быть равен объему потребления. В реальных задачах условие (5.9) часто нарушается и имеет место соотношение

S { a[i] | iÎ [1..n]} ³ S { b[j] | jÎ [1..m]}, (5.10)

В этом случае необходимо ввести в рассмотрение фиктивного (внешнего) потребителя j1 c

b[j1]= S{ a[i] | iÎ [1..n]} - S{ b[j] | jÎ [1..m]}.

Для всех iÎ [1..n] с[i, j1] полагают равным достаточно большому числу. Аналогично, если

S{ a[i] | iÎ [1..n]} £ S{ b[j] | jÎ [1..m]}, (5.11)

то вводится дополнительный (внешний) пункт производства i1.

Транспортные задачи, в которых выполняется соотношение (5.9) называют замкнутыми, в случаях (5.10-5.11) открытыми.

Транспортную задачу решают методом потенциалов, который является частным случаем метода потенциалов для транспортной задачи в сетевой постановке. Общая схема которого такова:

Определяют исходное базисное решение.

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

Если критерий оптимальности не выполняется, то переходим к новому базису и возвращаемся к пункту 2, иначе переходим к пункту 4.

Конец алгоритма.

 

Опишем алгоритм решения транспортной задачи более детально. Запишем ее условия в таблицу следующего вида:

 

  j 1 ... j ... m  
i b[j] a[i] b[1] ... b[j] ... b[m] b[j] u[j]
1 a[1] ... ... ... ... ... u[1]
2 a[2] ... ... ... ... ... u[2]
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
i a[i] ... ... ... ... ... u[i]
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
n a[n] ... ... ... ... ... u[n]
a[i] v[j] v[1]   v[j]   v[m] u[j] v[j]

 

Будем называть клеткой [i, j] клетку, находящуюся на пересечении i - той строки и j -го столбца. Каждую клетку [i, j] будем заполнять следующей информацией:

 

c[i, j] x[i, j]
d[i, j] q

 

Описание позиций d[i, j] и q будет приведено ниже.

 







Дата добавления: 2014-12-06; просмотров: 741. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Механизм действия гормонов а) Цитозольный механизм действия гормонов. По цитозольному механизму действуют гормоны 1 группы...

Алгоритм выполнения манипуляции Приемы наружного акушерского исследования. Приемы Леопольда – Левицкого. Цель...

ИГРЫ НА ТАКТИЛЬНОЕ ВЗАИМОДЕЙСТВИЕ Методические рекомендации по проведению игр на тактильное взаимодействие...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия