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

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

Экономические задачи, сводящиеся к транспортной модели

Для изучения данного раздела дисциплины необходимы знания, полученные при изучении тем 3 и 4.

Изучив данную тему, студент должен:

- уметь решать транспортную задачу;

- иметь общие представления о экономических задачах, сводящихся к транспортной модели.

Цель изучения – получить представление об особенностях решения транспортной задачи и задачи о назначении.

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

Транспортная задача представляет собой ЗЛП, однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся более эффективными. При разработке метода решения транспортной задачи существенную роль играет теория двойственности.

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

Некоторый однородный продукт, сосредоточенный у m поставщиков А_i в количестве а_i(i = 1,..., m) единиц соответственно, необходимо доставить n потребителям В_j в количестве b_j(j = 1,..., n) единиц. Известна стоимость с_ij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке х_ij единиц груза, то стоимость перевозки составит с_ijx_ij.

Стоимость всего плана выразится двойной суммой:

.

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

.

Таким образом, математическая модель транспортной задачи имеет следующий вид:

найти минимальное значение линейной функции

; (6.1)

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

; (6.2)

(6.3)

x_ij ³ 0, i = 1,…, m; j = 1,…, n. (6.4)

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

. (6.5)

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (6.5), называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности

;

б) суммарные потребности превышают суммарные запасы

.

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции:

.

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

(случай «а»)

(случай «б»)

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

В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель В_{n + 1}, потребность которого:

.

В случае «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик А_{m + 1}, запасы которого:

.

Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, поскольку груз в обоих случаях не перевозится.

Транспортная задача имеет n + m уравнений с mn неизвестными.

Матрицу Х = (х_ij)_m,n, удовлетворяющую условиям (6.2) – (6.4), называют планом перевозок транспортной задачи (х_ij-перевозками).

План Х*, при котором целевая функция (6.1) обращается в минимум, называется оптимальным.

Теорема 6.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса:

.

План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов (i = 1... m, j = 1… n), где – векторы при переменных х_ij (i = 1… m, j = 1… n) в матрице системы ограничений (6.2) – (6.4).

Теорема 6.2. Существует план, содержащий не более m + n – 1 положительных перевозок, при этом система векторов , соответствующая таким перевозкам (х_ij > 0), линейно независима.

Таким образом, опорный план транспортной задачи содержит m + n – 1 положительных перевозок. Если менее (m + n – 1) компонент оперного плана положительны, то он называется вырожденным. Дадим другое определение опорного плана.

План транспортной задачи называется опорным, если из его основных коммуникаций невозможно составить замкнутый маршрут.

Дата добавления: 2014-12-29