Постановка и основные свойства транспортной задачи

Рефераты / Экономико-математическое моделирование / Постановка и основные свойства транспортной задачи

Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1, с объемом производства и транспортными издержками В таком случае Т-задача будет иметь вид

минимизировать

при условиях

В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. .

Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса . Пусть - это убытки (штраф) в пункте Аі за единицу невывезенного продукта. Обозначим через сии,n+1 = удельные транспортные издержки на перевозку единицы продукта с Аі в Вn+1. Тогда соответствующая Т-задача запишется так:

минимизировать (1.16)

при условиях

(1.17) – (1.18)

В найденном решении все перевозки в фиктивный пункт Вn+1 считают равными нулю.

Опорные планы Т-задачи

Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

Последовательность коммуникаций

(1.19)

называют маршрутом, соединяющим пункты (рис. 2).

…

Рис. 2

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

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

Маршрут (1.19), к которому добавлена коммуникация называется замкнутым маршрутом или циклом.

Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).

Теорема 4. Система, составленная из векторов Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.

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

(1.20)

которое указывает на линейную зависимость векторов

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

Достаточность. Допустим, что из коммуникаций, отвечающих векторам системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа , среди которых не все нули, для которых выполняется условие