Сущность транспортной задачи линейного программирования. Понятие вырожденности. Открытая модель.

Цель транспортных задач: определение наиболее экономичных планов транспортировки заданного вида ресурса из нескольких пунктов - поставщиков ресурса (склады, заводы и т.д.) к нескольким потребителям ресурса (магазины, склады и т.д.).

Сущность:

1. Заданы m источников ресурса и n пунктов его потребления.

2.Запасы ресурса в источниках - Ai, i =1,¼, m;

3. Потребности ресурсов - Bj, j =1,¼, n.

4. Стоимость транспортировки единицы ресурса от i -го источника к j -му потребителю - Cij;

5. Хij - количество ресурса, транспортируемого от i -го источника к j -му потребителю.

6. Требуется определить такие значения Хij, при которых общие транспортные расходы будут минимальны- Z.

Вырожденность в транспортной задаче — ситуация, когда в процессе решения транспортной задачи число базисных (занятых перевозками) ячеек транспортной таблицы меньше <math>m+n-1</math> (где m и n — число поставщиков и потребителей, соответственно), и алгоритм решения впадает в бесконечный цикл или завершается с ошибкой.

Условие вырожденности ® m+n-1 – число независимых условий. Количество занятых клеток должно быть равно условию вырожденности, где m - количество строк, n - количество столбцов.

Если количество занятых клеток будет равно условию, то план невырожден.

Если количество занятых клеток > условия, то план составлен ошибочно, либо задача открытая.

Если количество занятых клеток < условия, то план вырожден.

Признаки врожденности плана:

а=b1, a1=b2, a2=b3;

a1=b1+b2, b1=a1+a4;

a1+a2=b2+b3

a1+a2 = b1+b2+b3+ и др.

Преодоление вырожденности производят в процессе решения задачи методом аппроксимации; В случае, когда выходит по алгоритму и столбец и строка, то на одном шаге выходит только один элемент (либо столбец, либо строка), а второй элемент остается и участвует в дальнейшем решении задачи; в оставшийся элемент, когда на него выпадает максимальная разность, вносится «нулевая» поставка и т.о. преодолевается вырожденность, а нулей в матрице будет столько, насколько количество занятых клеток меньше m+n-1.

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие, называется открытой. Для открытой модели может быть два случая:
a) суммарные запасы превышают суммарные потребности;
b) суммарные потребности превышают суммарные запасы.
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
при ограничениях
, i = 1, 2,..., m, (случай а)
, j = 1, 2,..., n;
, i = 1, 2,..., m, (случай б)
, j = 1, 2,..., n,
xij ³ 0 (i = 1, 2,..., m; j = 1, 2,..., n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 =. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 =.
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.
Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения.

**Для решения открытую модель задачи приводят к закрытому виду путем введения фиктивного пункта отправления с запасом, равным:

или фиктивного пункта назначения с потребностью, равной:

A_m+i = SB_j -SA _i

^{j=1 i=1}

Стоимость перевозок грузов по фиктивному

b_n+i = Sa_{i *}- S b _j

^{i =1 j =1}

пункту принимают равными «0». С _{in +i} = 0 (i=1,2,...m) или

C _{im +i} = 0 (j=1,2,...n)

При расчете разностей mк фиктивные элементы (столбец или строка) участвуют