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

--PAGE_BREAK--Свойства транспортной задачи
1. Для разрешимости Т-задачи необходимо и достаточно, чтобы выполнялось условие баланса
<img width=«69» height=«40» src=«ref-1_888351835-373.coolpic» v:shapes="_x0000_i1040">, (1.6)
то есть, чтобы суммарный объем производства равнялся объему потребления.

Доказательство. Пусть переменные xij, i = 1., m; j = 1., n удовлетворяют условиям (1.1), (1.2). Суммируя (1.1) по <img width=«9» height=«17» src=«ref-1_888352208-206.coolpic» v:shapes="_x0000_i1041">, а (1.2) по <img width=«13» height=«20» src=«ref-1_888352414-213.coolpic» v:shapes="_x0000_i1042">, получим:
<img width=«203» height=«48» src=«ref-1_888352627-988.coolpic» v:shapes="_x0000_i1043">.я
Отсюда <img width=«69» height=«40» src=«ref-1_888351835-373.coolpic» v:shapes="_x0000_i1044">, что и доказывает необходимость условия баланса Т-задачи.

Пусть справедливо условие (1.6). Обозначим <img width=«58» height=«35» src=«ref-1_888353988-320.coolpic» v:shapes="_x0000_i1045">, где <img width=«89» height=«37» src=«ref-1_888354308-271.coolpic» v:shapes="_x0000_i1046">.

Нетрудно доказать, что хij составляет план задачи. Действительно
<img width=«156» height=«78» src=«ref-1_888354579-1151.coolpic» v:shapes="_x0000_i1047">
Таким образом, доказана достаточность условия баланса для решения Т-задачи.

2. Ранг системы ограничений (1.1), (1.2) равен <img width=«69» height=«14» src=«ref-1_888355730-137.coolpic» v:shapes="_x0000_i1048">

Доказательство. Так как количество уравнений (1.1), (1.2) равно <img width=«32» height=«14» src=«ref-1_888355867-243.coolpic» v:shapes="_x0000_i1049">, то ранг этой системы <img width=«52» height=«14» src=«ref-1_888356110-131.coolpic» v:shapes="_x0000_i1050">. Пусть, набор <img width=«46» height=«29» src=«ref-1_888356241-383.coolpic» v:shapes="_x0000_i1051"> удовлетворяет всем уравнениям, кроме первых. Покажем, что он удовлетворяет также и первому уравнению.

Очевидно
<img width=«167» height=«46» src=«ref-1_888356624-898.coolpic» v:shapes="_x0000_i1052">
Так как
<img width=«101» height=«75» src=«ref-1_888357522-813.coolpic» v:shapes="_x0000_i1053">, то

<img width=«98» height=«37» src=«ref-1_888358335-939.coolpic» v:shapes="_x0000_i1054"> <img width=«92» height=«37» src=«ref-1_888359274-1017.coolpic» v:shapes="_x0000_i1055">, отсюда

<img width=«141» height=«46» src=«ref-1_888360291-742.coolpic» v:shapes="_x0000_i1056">,
Учитывая условие баланса (1.6), получим
<img width=«138» height=«37» src=«ref-1_888361033-366.coolpic» v:shapes="_x0000_i1057">,
т.е. первое уравнение системы (1.1) тоже удовлетворяется.

Таким образом, ранг системы уравнений (1.1), (1.2) <img width=«69» height=«14» src=«ref-1_888361399-143.coolpic» v:shapes="_x0000_i1058">.

Докажем, что ранг системы уравнений (1.1), (1.2) равен точно <img width=«52» height=«14» src=«ref-1_888361542-127.coolpic» v:shapes="_x0000_i1059">. Для этого составим матрицу из первых (<img width=«52» height=«14» src=«ref-1_888361542-127.coolpic» v:shapes="_x0000_i1060">) компонентов векторов <img width=«184» height=«17» src=«ref-1_888361796-586.coolpic» v:shapes="_x0000_i1061">


<img width=«279» height=«216» src=«ref-1_888362382-2046.coolpic» v:shapes="_x0000_i1062">
Очевидно, что эта матрица не вырождена. Поэтому векторы {<img width=«173» height=«20» src=«ref-1_888364428-622.coolpic» v:shapes="_x0000_i1063">} образуют базис. Так как базис системы состоит из (<img width=«52» height=«14» src=«ref-1_888361542-127.coolpic» v:shapes="_x0000_i1064">) векторов, то и ранг системы (1.1), (1.2) <img width=«69» height=«14» src=«ref-1_888355730-137.coolpic» v:shapes="_x0000_i1065">.

Двойственная транспортная задача (<img width=«14» height=«17» src=«ref-1_888365314-95.coolpic» v:shapes="_x0000_i1066"> – задача).Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней <img width=«14» height=«17» src=«ref-1_888365314-95.coolpic» v:shapes="_x0000_i1067">-задача.

Переменные <img width=«14» height=«17» src=«ref-1_888365314-95.coolpic» v:shapes="_x0000_i1068">-задачи обозначим v1, v2., vn, – u1, – u2., – um…

Теорема 1.<img width=«14» height=«17» src=«ref-1_888365314-95.coolpic» v:shapes="_x0000_i1069">-задача имеет решение и если Xопт = <img width=«26» height=«29» src=«ref-1_888365694-271.coolpic» v:shapes="_x0000_i1070">,

<img width=«323» height=«23» src=«ref-1_888365965-779.coolpic» v:shapes="_x0000_i1071"> – оптимальные решения T и <img width=«14» height=«17» src=«ref-1_888365314-95.coolpic» v:shapes="_x0000_i1072">-задачи соответственно, то
<img width=«233» height=«40» src=«ref-1_888366839-1251.coolpic» v:shapes="_x0000_i1073">. (1.7)
Если учесть, что ui – стоимость единицы продукции в пункте Аі, а vj – стоимость после перевозки в пункт Bj, то смысл теоремы будет такой:

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

Переменные uiиvj называют потенциалами пунктов AiиBj для Т-задачи.

Таким образом, теорема 1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой.

Справедливость теоремы 1. следует из основной теоремы двойственной ЛП (теорема 2.5).

Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.

Теорема 2.Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, что
vj – ui<img width=«12» height=«14» src=«ref-1_888368090-91.coolpic» v:shapes="_x0000_i1074">cij, i = 1., m; j=1., n… (1.8)
При этом, если
<img width=«55» height=«26» src=«ref-1_888368181-300.coolpic» v:shapes="_x0000_i1075"> это vj– ui= cij.
Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).

Дадим экономическую интерпретацию условий теоремы 2.

Разность между потенциалами пунктов BjиAi, т.е. величину vj – ui, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj. Поэтому, если vj – ui < cij, то перевозка по коммуникации Ai Bj нерентабельна, и <img width=«37» height=«23» src=«ref-1_888368481-259.coolpic» v:shapes="_x0000_i1076">. Если vj – ui = cij, то такая перевозка рентабельна, и <img width=«49» height=«23» src=«ref-1_888368740-153.coolpic» v:shapes="_x0000_i1077"> (см. Теорему 2.7).

Транспортная задача с ограниченными пропускными способностями.

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

Пусть <img width=«17» height=«23» src=«ref-1_888368893-104.coolpic» v:shapes="_x0000_i1078"> — пропускная способность коммуникации Ai Bj.
Тогда <img width=«150» height=«26» src=«ref-1_888368997-425.coolpic» v:shapes="_x0000_i1079"> (1.9)
Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Тd – задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. Аі, и полного ввоза продукта в п. Вj. Поэтому для Тd – задачи вводят еще два условия:
<img width=«115» height=«43» src=«ref-1_888369422-599.coolpic» v:shapes="_x0000_i1080"> (1.10)

<img width=«115» height=«40» src=«ref-1_888370021-592.coolpic» v:shapes="_x0000_i1081"> (1.11)
Но и при добавочных условиях (1.10), (1.11) Тd – задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Тd – задача неразрешима.

Теорема 3.Для оптимальности плана Х0 Тd – задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, при которых
<img width=«69» height=«23» src=«ref-1_888370613-365.coolpic» v:shapes="_x0000_i1082"> если <img width=«43» height=«23» src=«ref-1_888370978-149.coolpic» v:shapes="_x0000_i1083">, (1.12)

<img width=«71» height=«23» src=«ref-1_888371127-357.coolpic» v:shapes="_x0000_i1084"> если 0 <<img width=«55» height=«26» src=«ref-1_888371484-308.coolpic» v:shapes="_x0000_i1085">, (1.13)

<img width=«69» height=«23» src=«ref-1_888371792-365.coolpic» v:shapes="_x0000_i1086"> если<img width=«52» height=«23» src=«ref-1_888372157-163.coolpic» v:shapes="_x0000_i1087">. (1.14)
Смысл условий оптимальности (1.12) – (1.14) состоит в следующем:

если приращение стоимости продукта vj – uj меньше транспортных расходов cij, то такая перевозка убыточна, а потому <img width=«43» height=«23» src=«ref-1_888370978-149.coolpic» v:shapes="_x0000_i1088">. Если же приращение стоимости продукта vj – uj больше транспортных расходов cij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. <img width=«52» height=«23» src=«ref-1_888372157-163.coolpic» v:shapes="_x0000_i1089">.

Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td – задачи.

Открытые транспортные модели.Существует ряд практических задач, в которых условие баланса <img width=«69» height=«37» src=«ref-1_888372632-244.coolpic» v:shapes="_x0000_i1090">не выполняется. Такие модели называются открытыми. Возможные два случая:
1)<img width=«72» height=«37» src=«ref-1_888372876-245.coolpic» v:shapes="_x0000_i1091">

2)<img width=«72» height=«37» src=«ref-1_888373121-247.coolpic» v:shapes="_x0000_i1092">
В первом случае полное удовлетворение спроса невозможно.

Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через <img width=«14» height=«23» src=«ref-1_888373368-94.coolpic» v:shapes="_x0000_i1093">величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте Bj.

Тогда требуется минимизировать
<img width=«107» height=«37» src=«ref-1_888373462-332.coolpic» v:shapes="_x0000_i1094"> (1.15)
при условиях
<img width=«104» height=«78» src=«ref-1_888373794-835.coolpic» v:shapes="_x0000_i1095">

где <img width=«84» height=«37» src=«ref-1_888374629-370.coolpic» v:shapes="_x0000_i1096"> — неудовлетворенный спрос.


Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1, с объемом производства <img width=«98» height=«35» src=«ref-1_888374999-414.coolpic» v:shapes="_x0000_i1097"> и транспортными издержками <img width=«104» height=«23» src=«ref-1_888375413-354.coolpic» v:shapes="_x0000_i1098"> В таком случае Т-задача будет иметь вид

минимизировать <img width=«58» height=«37» src=«ref-1_888375767-237.coolpic» v:shapes="_x0000_i1099">

при условиях
<img width=«55» height=«72» src=«ref-1_888376004-650.coolpic» v:shapes="_x0000_i1100">
В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. <img width=«112» height=«26» src=«ref-1_888376654-392.coolpic» v:shapes="_x0000_i1101">.

Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса <img width=«98» height=«37» src=«ref-1_888377046-423.coolpic» v:shapes="_x0000_i1102">. Пусть <img width=«12» height=«17» src=«ref-1_888377469-86.coolpic» v:shapes="_x0000_i1103"> — это убытки (штраф) в пункте Аі за единицу невывезенного продукта. Обозначим через сии,n+1 = <img width=«12» height=«17» src=«ref-1_888377469-86.coolpic» v:shapes="_x0000_i1104"> удельные транспортные издержки на перевозку единицы продукта с Аі в Вn+1. Тогда соответствующая Т-задача запишется так:
минимизировать <img width=«55» height=«37» src=«ref-1_888377641-235.coolpic» v:shapes="_x0000_i1105"> (1.16)
при условиях
<img width=«124» height=«72» src=«ref-1_888377876-825.coolpic» v:shapes="_x0000_i1106"> (1.17) – (1.18)


В найденном решении <img width=«26» height=«17» src=«ref-1_888378701-106.coolpic» v:shapes="_x0000_i1107"> все перевозки <img width=«29» height=«20» src=«ref-1_888378807-246.coolpic» v:shapes="_x0000_i1108">в фиктивный пункт Вn+1 считают равными нулю.
    продолжение
--PAGE_BREAK--Опорные планы Т-задачи
Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

Последовательность коммуникаций
<img width=«222» height=«23» src=«ref-1_888379053-820.coolpic» v:shapes="_x0000_i1109"> (1.19)
называют маршрутом, соединяющим пункты <img width=«40» height=«20» src=«ref-1_888379873-370.coolpic» v:shapes="_x0000_i1110"> (рис. 2).
<img width=«420» height=«78» src=«ref-1_888380243-570.coolpic» v:shapes="_x0000_i1111"><img width=«60» height=«72» src=«ref-1_888380813-328.coolpic» v:shapes="_x0000_i1112"><img width=«52» height=«72» src=«ref-1_888381141-313.coolpic» v:shapes="_x0000_i1113"><img width=«43» height=«72» src=«ref-1_888381454-304.coolpic» v:shapes="_x0000_i1114"><img width=«43» height=«81» src=«ref-1_888381758-326.coolpic» v:shapes="_x0000_i1115"><img width=«17» height=«23» src=«ref-1_888382084-152.coolpic» v:shapes="_x0000_i1116"> <img width=«17» height=«23» src=«ref-1_888382236-156.coolpic» v:shapes="_x0000_i1117"> <img width=«17» height=«23» src=«ref-1_888382392-155.coolpic» v:shapes="_x0000_i1118"> … <img width=«17» height=«23» src=«ref-1_888382547-155.coolpic» v:shapes="_x0000_i1119">

<img width=«20» height=«23» src=«ref-1_888384008-283.coolpic» v:shapes="_x0000_i1122"> <img width=«23» height=«23» src=«ref-1_888384291-289.coolpic» v:shapes="_x0000_i1123"> <img width=«20» height=«23» src=«ref-1_888384580-285.coolpic» v:shapes="_x0000_i1124">. <img width=«26» height=«23» src=«ref-1_888384865-171.coolpic» v:shapes="_x0000_i1125"> <img width=«20» height=«23» src=«ref-1_888385036-283.coolpic» v:shapes="_x0000_i1126">

Рис. 2
Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта <img width=«17» height=«17» src=«ref-1_888385319-97.coolpic» v:shapes="_x0000_i1127"> в пункт <img width=«23» height=«23» src=«ref-1_888385416-237.coolpic» v:shapes="_x0000_i1128">, проходя через пункты <img width=«78» height=«23» src=«ref-1_888385653-325.coolpic» v:shapes="_x0000_i1129">.

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

Маршрут (1.19), к которому добавлена коммуникация <img width=«35» height=«23» src=«ref-1_888385978-268.coolpic» v:shapes="_x0000_i1130"> называется замкнутым маршрутом или циклом.

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

Теорема 4.Система, составленная из векторов <img width=«17» height=«23» src=«ref-1_888386246-218.coolpic» v:shapes="_x0000_i1131"> Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.

<img width=«26» height=«9» src=«ref-1_888386464-88.coolpic» v:shapes="_x0000_i1132"><img width=«26» height=«9» src=«ref-1_888386552-88.coolpic» v:shapes="_x0000_i1133"><img width=«26» height=«9» src=«ref-1_888386640-85.coolpic» v:shapes="_x0000_i1134"><img width=«26» height=«9» src=«ref-1_888386640-85.coolpic» v:shapes="_x0000_i1135"><img width=«26» height=«9» src=«ref-1_888386810-88.coolpic» v:shapes="_x0000_i1136">Доказательство. Необходимость. Пусть векторы <img width=«104» height=«23» src=«ref-1_888386898-528.coolpic» v:shapes="_x0000_i1137"> линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций <img width=«167» height=«20» src=«ref-1_888387426-656.coolpic» v:shapes="_x0000_i1138"> и <img width=«35» height=«23» src=«ref-1_888385978-268.coolpic» v:shapes="_x0000_i1139">, то, очевидно, начиная движение из пункта <img width=«17» height=«17» src=«ref-1_888385319-97.coolpic» v:shapes="_x0000_i1140"> и последовательно проходя все пункты <img width=«181» height=«20» src=«ref-1_888388447-494.coolpic» v:shapes="_x0000_i1141"> по последней коммуникации <img width=«37» height=«23» src=«ref-1_888388941-270.coolpic» v:shapes="_x0000_i1142"> мы вернемся в начальный пункт <img width=«17» height=«17» src=«ref-1_888385319-97.coolpic» v:shapes="_x0000_i1143">. Тогда справедливое равенство
<img width=«184» height=«23» src=«ref-1_888389308-886.coolpic» v:shapes="_x0000_i1144"> (1.20)
которое указывает на линейную зависимость векторов
<img width=«104» height=«23» src=«ref-1_888390194-512.coolpic» v:shapes="_x0000_i1145">.
Полученное противоречие доказывает необходимость условий теоремы 4.

Достаточность. Допустим, что из коммуникаций, отвечающих векторам <img width=«20» height=«23» src=«ref-1_888390706-225.coolpic» v:shapes="_x0000_i1146">системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа <img width=«66» height=«23» src=«ref-1_888390931-320.coolpic» v:shapes="_x0000_i1147">, среди которых не все нули, для которых выполняется условие
<img width=«86» height=«37» src=«ref-1_888391251-558.coolpic» v:shapes="_x0000_i1148">. (1.21)
Пусть, например <img width=«43» height=«23» src=«ref-1_888391809-325.coolpic» v:shapes="_x0000_i1149">. Перенесем тогда соответствующий вектор вправо и получим
<img width=«130» height=«37» src=«ref-1_888392134-666.coolpic» v:shapes="_x0000_i1150">, (1.22)
где Е1 образуется вычеркиванием в Е пары индексов (<img width=«26» height=«17» src=«ref-1_888392800-105.coolpic» v:shapes="_x0000_i1151">). Компонента с номером <img width=«12» height=«17» src=«ref-1_888392905-87.coolpic» v:shapes="_x0000_i1152"> в правой части (3.1.22) не равна нулю.

Следовательно, это же относится и к левой части этого равенства, т.е. среди

векторов <img width=«75» height=«23» src=«ref-1_888392992-391.coolpic» v:shapes="_x0000_i1153"> найдется хотя бы один вектор вида <img width=«26» height=«23» src=«ref-1_888393383-354.coolpic» v:shapes="_x0000_i1154"> с

коэффициентом <img width=«46» height=«23» src=«ref-1_888393737-387.coolpic» v:shapes="_x0000_i1155">. Перенеся его в правую чатсть равенства (1.22), получим
<img width=«12» height=«23» src=«ref-1_888394124-208.coolpic» v:shapes="_x0000_i1156"><img width=«184» height=«35» src=«ref-1_888394332-770.coolpic» v:shapes="_x0000_i1157">, (1.23)
где <img width=«89» height=«17» src=«ref-1_888395102-190.coolpic» v:shapes="_x0000_i1158">. Но поскольку <img width=«40» height=«17» src=«ref-1_888395292-124.coolpic» v:shapes="_x0000_i1159">, компонента с номером <img width=«37» height=«17» src=«ref-1_888395416-115.coolpic» v:shapes="_x0000_i1160"> правой части (1.23) отлична от нуля. Поэтому среди векторов левой части (1.23) найдется хотя бы один вектор вида <img width=«26» height=«23» src=«ref-1_888395531-303.coolpic» v:shapes="_x0000_i1161">, для которого <img width=«49» height=«23» src=«ref-1_888395834-336.coolpic» v:shapes="_x0000_i1162">. Перенося его в правую часть (1.23), находим




<img width=«242» height=«35» src=«ref-1_888396170-878.coolpic» v:shapes="_x0000_i1163"> (1.24)

где <img width=«89» height=«17» src=«ref-1_888397048-190.coolpic» v:shapes="_x0000_i1164">
Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
<img width=«245» height=«40» src=«ref-1_888397238-950.coolpic» v:shapes="_x0000_i1165"> (1.25)
где <img width=«121» height=«17» src=«ref-1_888398188-230.coolpic» v:shapes="_x0000_i1166">

Возможные два случая:

1) <img width=«35» height=«17» src=«ref-1_888398418-113.coolpic» v:shapes="_x0000_i1167"> при некотором <img width=«66» height=«14» src=«ref-1_888398531-143.coolpic» v:shapes="_x0000_i1168">

2) <img width=«35» height=«17» src=«ref-1_888398674-116.coolpic» v:shapes="_x0000_i1169">.

В первом случае процесс переноса заканчивается, причем из векторов в правой части (1.25) можно образовать замкнутый маршрут. Таким маршрутом является
<img width=«190» height=«23» src=«ref-1_888398790-672.coolpic» v:shapes="_x0000_i1170">
Во втором случае процесс переноса продолжается, и поскольку <img width=«107» height=«17» src=«ref-1_888399462-316.coolpic» v:shapes="_x0000_i1171">, среди векторов Рij, где (i, j) <img width=«40» height=«17» src=«ref-1_888399778-127.coolpic» v:shapes="_x0000_i1172"> обязательно найдется вектор <img width=«32» height=«23» src=«ref-1_888399905-374.coolpic» v:shapes="_x0000_i1173">с коэффициентом <img width=«55» height=«23» src=«ref-1_888400279-404.coolpic» v:shapes="_x0000_i1174">.

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

Итак, допустив, что система векторов <img width=«14» height=«23» src=«ref-1_888400683-219.coolpic» v:shapes="_x0000_i1175">линейно зависима, мы пришли к противоречию с условием теоремы, согласно которому из коммуникаций <img width=«14» height=«23» src=«ref-1_888400683-219.coolpic» v:shapes="_x0000_i1176"> системы R нельзя составить замкнутый маршрут. Остается принять, что система R состоит из линейно независимых векторов.

Достаточность условий теоремы доказана.

Назовем коммуникацию <img width=«29» height=«20» src=«ref-1_888401121-251.coolpic» v:shapes="_x0000_i1177"> Т-задачи основной коммуникацией плана Х, если <img width=«40» height=«23» src=«ref-1_888401372-135.coolpic» v:shapes="_x0000_i1178"> Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность.

План <img width=«55» height=«29» src=«ref-1_888401507-469.coolpic» v:shapes="_x0000_i1179"> Т-задачи является опорным (базисным), если из его основных коммуникаций нельзя составить замкнутый маршрут.

Теорема 5.Вектор <img width=«20» height=«23» src=«ref-1_888401976-292.coolpic» v:shapes="_x0000_i1180"> является линейной комбинацией векторов системы R тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak и <img width=«14» height=«17» src=«ref-1_888402268-94.coolpic» v:shapes="_x0000_i1181">. Если этот маршрут имеет вид
<img width=«184» height=«23» src=«ref-1_888402362-556.coolpic» v:shapes="_x0000_i1182">
то
<img width=«222» height=«23» src=«ref-1_888402918-668.coolpic» v:shapes="_x0000_i1183">. (1.26)
Доказательство этой теоремы основано на теореме 3.4. Пусть <img width=«20» height=«23» src=«ref-1_888401976-292.coolpic» v:shapes="_x0000_i1184"> выражен в виде линейной комбинации векторов системы R. Добавив к ней вектор <img width=«20» height=«23» src=«ref-1_888401976-292.coolpic» v:shapes="_x0000_i1185">, получим систему линейно зависимых векторов. Тогда в силу теоремы 3.4 появляется замкнутый маршрут <img width=«12» height=«14» src=«ref-1_888404170-82.coolpic» v:shapes="_x0000_i1186">. Этот замкнутый маршрут должен содержать коммуникацию <img width=«32» height=«17» src=«ref-1_888404252-120.coolpic» v:shapes="_x0000_i1187"> и, следовательно, все остальные коммуникации должны соединить <img width=«17» height=«17» src=«ref-1_888404372-97.coolpic» v:shapes="_x0000_i1188"> и <img width=«14» height=«17» src=«ref-1_888402268-94.coolpic» v:shapes="_x0000_i1189">.

Тогда
<img width=«207» height=«20» src=«ref-1_888404563-640.coolpic» v:shapes="_x0000_i1190">.


Перенеся <img width=«17» height=«17» src=«ref-1_888405203-99.coolpic» v:shapes="_x0000_i1191"> в правую часть, получим выражение (1.26), что и требовалось доказать.





Рассмотрим произвольную матрицу <img width=«32» height=«17» src=«ref-1_888406730-357.coolpic» v:shapes="_x0000_i1202">. Между позициями матрицы Х и векторами <img width=«17» height=«23» src=«ref-1_888407087-216.coolpic» v:shapes="_x0000_i1203"> можно установить следующее соответствие. Вектор <img width=«17» height=«23» src=«ref-1_888407087-216.coolpic» v:shapes="_x0000_i1204"> соответствует элементу <img width=«14» height=«23» src=«ref-1_888407519-95.coolpic» v:shapes="_x0000_i1205"> матрицы Х. Тогда можно задать систему из векторов <img width=«32» height=«23» src=«ref-1_888407614-254.coolpic» v:shapes="_x0000_i1206">, выделив единицами соответствующие элементы матрицы Х. Рассмотрим матрицу на рис3. Здесь единицами отмечена система векторов R:
<img width=«291» height=«23» src=«ref-1_888407868-811.coolpic» v:shapes="_x0000_i1207">.
При использовании матрицы Х критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов<img width=«32» height=«23» src=«ref-1_888407614-254.coolpic» v:shapes="_x0000_i1208"> необходимо и достаточно, чтобы из ненулевых элементов матрицы Х, отвечающих этим векторам, невозможно было составить замкнутый маршрут (цикл).

Так как из выделенных единицами позиций на рис. 3 нельзя составить замкнутый маршрут, то данная система линейно независима и образует базис.

Введем теперь в систему <img width=«29» height=«23» src=«ref-1_888408933-371.coolpic» v:shapes="_x0000_i1209"> вектор <img width=«20» height=«20» src=«ref-1_888409304-218.coolpic» v:shapes="_x0000_i1210">, отметив его знаком '+'. Чтобы разложить <img width=«20» height=«20» src=«ref-1_888409304-218.coolpic» v:shapes="_x0000_i1211"> по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе <img width=«17» height=«17» src=«ref-1_888409740-94.coolpic» v:shapes="_x0000_i1212">:
<img width=«323» height=«23» src=«ref-1_888409834-723.coolpic» v:shapes="_x0000_i1213">.
При небольших размерах матрицы Х визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х Т-задачи замкнутую цепочку, если она существует.

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

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

После конечного числа шагов этот процесс заканчивается одним из следующих двух исходов: 1) все строки (столбцы) матрицы вычеркнуты; 2) получена подматрица, в каждой строке и столбце которой содержится не менее двух элементов S.

В первом случае из элементов множества S составить цикл невозможно. Следовательно, соответствующий план Х является опорным.

Во втором случае множество S содержит цикл (циклы) и соответствующий план Х не является опорным (базисным). На рис. 4 показаны два плана Т-задачи: небазисный (рис. 4, а) и базисный (рис. 4, б). Номера линий указывают порядок вычеркивания. Звездочками отмечены элементы, которые вычеркнуть нельзя. Они образуют цикл.


    продолжение
--PAGE_BREAK--Нахождение начальных опорных планов
Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.

Метод северо-западного угла.Основную идею метода рассмотрим на конкретном примере.

Пусть дана Т-задача с четырьмя пунктами производства А1,А2,А3,А4 с объемами производства <img width=«147» height=«17» src=«ref-1_888412418-239.coolpic» v:shapes="_x0000_i1216"> и пунктами потребления <img width=«58» height=«23» src=«ref-1_888412657-294.coolpic» v:shapes="_x0000_i1217"> с объемами потребления соответственно <img width=«147» height=«17» src=«ref-1_888412951-369.coolpic» v:shapes="_x0000_i1218">.

Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку bj, справа столбец ai. Кроме того, снизу от bj образуем строки <img width=«63» height=«23» src=«ref-1_888413320-182.coolpic» v:shapes="_x0000_i1219">, где будем записывать неудовлетворенные потребности, а справа от ai – столбцы <img width=«66» height=«23» src=«ref-1_888413502-311.coolpic» v:shapes="_x0000_i1220">, где будем записывать остатки невывезенного продукта (табл. 2).

Заполнение таблицы начинают с левого верхнего элемента таблицы X – x11, что и обусловило название метода. Сравнив <img width=«35» height=«17» src=«ref-1_888413813-115.coolpic» v:shapes="_x0000_i1221"> с <img width=«35» height=«17» src=«ref-1_888413928-118.coolpic» v:shapes="_x0000_i1222"> и выбрав меньшее из них, получим x11=1. Записываем это значение в матрицу Х0. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце <img width=«23» height=«23» src=«ref-1_888414046-245.coolpic» v:shapes="_x0000_i1223"> записываем остатки невывезенного продукта, <img width=«86» height=«23» src=«ref-1_888414291-328.coolpic» v:shapes="_x0000_i1224">, а в строке <img width=«23» height=«23» src=«ref-1_888414619-121.coolpic» v:shapes="_x0000_i1225"> – неудовлетворенные потребности после одного шага заполнения.

Переходим к второй строке и начинаем заполнение с элемента <img width=«20» height=«17» src=«ref-1_888414740-100.coolpic» v:shapes="_x0000_i1226"> (новый северо-западный угол незаполненной части таблицы 2). Сравнивая <img width=«89» height=«23» src=«ref-1_888414840-353.coolpic» v:shapes="_x0000_i1227"> выбираем меньшее из них, и потому <img width=«40» height=«17» src=«ref-1_888415193-121.coolpic» v:shapes="_x0000_i1228">. Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х0. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как
<img width=«196» height=«37» src=«ref-1_888415314-584.coolpic» v:shapes="_x0000_i1229">.
Таблица 2


Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:
<img width=«107» height=«23» src=«ref-1_888417443-372.coolpic» v:shapes="_x0000_i1242">.
Возможные три случая: а) если <img width=«43» height=«17» src=«ref-1_888417815-126.coolpic» v:shapes="_x0000_i1243">то <img width=«43» height=«17» src=«ref-1_888417941-121.coolpic» v:shapes="_x0000_i1244"> и всю первую строку, начиная со второго элемента, заполняют нулями; б) если <img width=«40» height=«20» src=«ref-1_888418062-265.coolpic» v:shapes="_x0000_i1245">, то <img width=«43» height=«17» src=«ref-1_888418327-128.coolpic» v:shapes="_x0000_i1246">, а все оставшиеся элементы первого столбца заполняют нулями; в) если
<img width=«43» height=«17» src=«ref-1_888418455-126.coolpic» v:shapes="_x0000_i1247"> то <img width=«69» height=«17» src=«ref-1_888418581-156.coolpic» v:shapes="_x0000_i1248">
и все оставшиеся элементы первых столбцов и строки заполняют нулями.

Находим
<img width=«78» height=«40» src=«ref-1_888418737-546.coolpic» v:shapes="_x0000_i1249">
на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент
<img width=«118» height=«23» src=«ref-1_888419283-378.coolpic» v:shapes="_x0000_i1250">


причем
<img width=«118» height=«23» src=«ref-1_888419661-600.coolpic» v:shapes="_x0000_i1251">, (1.27)
где
<img width=«118» height=«95» src=«ref-1_888420261-869.coolpic» v:shapes="_x0000_i1252"> (1.28)
Если <img width=«58» height=«23» src=«ref-1_888421130-314.coolpic» v:shapes="_x0000_i1253">, то заполняем нулями строку <img width=«12» height=«14» src=«ref-1_888421444-87.coolpic» v:shapes="_x0000_i1254">, начиная с (<img width=«14» height=«14» src=«ref-1_888421531-91.coolpic» v:shapes="_x0000_i1255"> +1) – го элемента. В противном случае заполняем нулями столбец <img width=«12» height=«14» src=«ref-1_888421622-85.coolpic» v:shapes="_x0000_i1256">, начиная с элемента (<img width=«12» height=«14» src=«ref-1_888421444-87.coolpic» v:shapes="_x0000_i1257"> +1). Если <img width=«58» height=«23» src=«ref-1_888421794-312.coolpic» v:shapes="_x0000_i1258">, то заполняем нулями остаток строки <img width=«12» height=«14» src=«ref-1_888421444-87.coolpic» v:shapes="_x0000_i1259"> и столбца <img width=«14» height=«14» src=«ref-1_888421531-91.coolpic» v:shapes="_x0000_i1260">. Далее вычисляем <img width=«228» height=«26» src=«ref-1_888422284-569.coolpic» v:shapes="_x0000_i1261">. На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.
    продолжение
--PAGE_BREAK--Метод минимального элемента
Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С=<img width=«26» height=«26» src=«ref-1_888422853-135.coolpic» v:shapes="_x0000_i1262">. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.

Формальное описание алгоритма.Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0.

Пусть элементом с минимальным порядковым номером оказался <img width=«95» height=«23» src=«ref-1_888422988-427.coolpic» v:shapes="_x0000_i1263">. Возможные три случая: а) если <img width=«40» height=«23» src=«ref-1_888423415-133.coolpic» v:shapes="_x0000_i1264">, то оставшуюся часть <img width=«9» height=«14» src=«ref-1_888423548-78.coolpic» v:shapes="_x0000_i1265">-й строки заполняем нулями; б) если <img width=«40» height=«23» src=«ref-1_888423626-266.coolpic» v:shapes="_x0000_i1266">, то оставшуюся часть <img width=«12» height=«17» src=«ref-1_888423892-86.coolpic» v:shapes="_x0000_i1267">-го столбца заполняем нулями; в) если <img width=«40» height=«23» src=«ref-1_888423978-263.coolpic» v:shapes="_x0000_i1268">, то оставшуюся часть <img width=«9» height=«14» src=«ref-1_888423548-78.coolpic» v:shapes="_x0000_i1269">-й строки и <img width=«12» height=«17» src=«ref-1_888423892-86.coolpic» v:shapes="_x0000_i1270">-го столбца заполняем нулями.

Дале этот процесс повторяют с незаполненной частью матрицы Х1.

Пример 1. Найти начальный базисный план методом минимального элемента для Табл. 3. следующей задачи.
Таблица. 3.


Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 3.4).

Соответствующее значение целевой функции равно
<img width=«150» height=«35» src=«ref-1_888424405-715.coolpic» v:shapes="_x0000_i1271"> 3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92
Таблица 4


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

Рассмотрим два случая.

1. Вырожденный план является начальным Х0. Тогда выбирают некоторые нулевые элементы матрицы Х0в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется <img width=«97» height=«20» src=«ref-1_888425934-325.coolpic» v:shapes="_x0000_i1278">. Далее данные элементы заменяют на <img width=«31» height=«16» src=«ref-1_888426259-236.coolpic» v:shapes="_x0000_i1279"> (где <img width=«13» height=«15» src=«ref-1_888426495-211.coolpic» v:shapes="_x0000_i1280"> – произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Хk вместо<img width=«13» height=«15» src=«ref-1_888426495-211.coolpic» v:shapes="_x0000_i1281"> пишут нули.

2. Вырожденный план получается при построении плана Хk+1 на базе Хk, если цепочка в плане Хk содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Хk+1 полагают равным нулю только один из этих элементов, а остальные заменяют на <img width=«13» height=«15» src=«ref-1_888426495-211.coolpic» v:shapes="_x0000_i1282">, и далее решают задачу как невырожденную. Если на k-м шаге <img width=«43» height=«22» src=«ref-1_888427128-265.coolpic» v:shapes="_x0000_i1283">, то при переходе от Хk к Хk+1 значение целевой функции не изменяется, а в базис вводится элемент <img width=«17» height=«23» src=«ref-1_888427393-225.coolpic» v:shapes="_x0000_i1284">, для которого перевозка станет равной <img width=«13» height=«15» src=«ref-1_888426495-211.coolpic» v:shapes="_x0000_i1285">.

Пример 2.Решим Т-задачу со следующими условиями (см. Табл.6)

Проверим условие баланса <img width=«81» height=«36» src=«ref-1_888427829-502.coolpic» v:shapes="_x0000_i1286">

Предварительный этап. Методом минимального элемента строим начальный базисный план Х0(Табл. 5)
Таблица 5

<img width=«138» height=«102» src=«ref-1_888428331-898.coolpic» v:shapes="_x0000_i1287">
Так как m + n – 1 = 6; k = 4, то план х0– вырожденный; l = m+ n -1 – k = 2.

Два нулевых элемента Х0делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов <img width=«21» height=«21» src=«ref-1_888429229-303.coolpic» v:shapes="_x0000_i1288">, <img width=«21» height=«21» src=«ref-1_888429532-364.coolpic» v:shapes="_x0000_i1289"> и положим их равными .

Схема перевозок для плана Х0показана на рис. 6.
<img width=«440» height=«114» src=«ref-1_888429896-2607.coolpic» v:shapes="_x0000_i1290">



Рис. 6.
Для вычисления предварительных потенциалов выберем начальный пункт А1 и допустим, что <img width=«48» height=«22» src=«ref-1_888432702-280.coolpic» v:shapes="_x0000_i1292">. Потенциалы всех остальных пунктов вычисляем по формулам
<img width=«90» height=«26» src=«ref-1_888432982-350.coolpic» v:shapes="_x0000_i1293">, <img width=«90» height=«26» src=«ref-1_888433332-355.coolpic» v:shapes="_x0000_i1294">


Для проверки оптимальности плана х0строим матрицу С1, элементы которой вычисляем по соотношению
<img width=«131» height=«31» src=«ref-1_888433687-671.coolpic» v:shapes="_x0000_i1295">

<img width=«96» height=«52» src=«ref-1_888434358-536.coolpic» v:shapes="_x0000_i1296">
Так как в матрице С1 элемент С23 = – 3 < 0, то план Х0– неоптимальный.
Первая итерация. Второй этап.



<img width=«95» height=«17» src=«ref-1_888437479-319.coolpic» v:shapes="_x0000_i1308">
В результате построения Х1 в базис вводим<img width=«41» height=«19» src=«ref-1_888437798-354.coolpic» v:shapes="_x0000_i1309">. План Х1 является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например <img width=«17» height=«17» src=«ref-1_888438152-218.coolpic» v:shapes="_x0000_i1310">, в плане Х1 заменяем на .
Вторая итерация. Первый этап



<img width=«65» height=«19» src=«ref-1_888440398-396.coolpic» v:shapes="_x0000_i1320">
Второй этап.



Третья итерация. Первый этап.



Так как в матрице С3 нет отрицательных элементов, план Х2 – оптимальный.
    продолжение
--PAGE_BREAK--