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

--PAGE_BREAK--неизвестных являются свободными. В базис­ном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем <shape id="_x0000_i1138" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image157.wmz» o:><img width=«59» height=«19» src=«dopb17322.zip» v:shapes="_x0000_i1138"> заполненных и <shape id="_x0000_i1139" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image153.wmz» o:><img width=«47» height=«21» src=«dopb17335.zip» v:shapes="_x0000_i1139">·<shape id="_x0000_i1140" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image155.wmz» o:><img width=«43» height=«21» src=«dopb17336.zip» v:shapes="_x0000_i1140">  пустых клеток.
             Для контроля надо проверять, равна ли сумма чисел в заполнен­ных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].
Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвест­ных вписываются в соответствующую клетку, и эта клетка считается заполненной.
Замечание 2. Под величинами <shape id="_x0000_i1141" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image158.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1141">, очевидно, не обязательно под­разумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, <shape id="_x0000_i1142" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image159.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1142"> выражены в тоннах, а <shape id="_x0000_i1143" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image160.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1143"> в километрах, то величина <shape id="_x0000_i1144" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image161.wmz» o:><img width=«15» height=«19» src=«dopb17337.zip» v:shapes="_x0000_i1144">, определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
3. Методы составления начального опорного плана.
Как и в общем случае, решение транспортной задачи начинается с отыскания первого опорного плана (исходного базиса). Мы рас­смотрим два наиболее распространенных метода построения такого базиса. Суть обоих этих методов состоит в том, что базисный план составляется последова­тельно, в несколько шагов (точнее, <shape id="_x0000_i1145" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image150.wmz» o:><img width=«59» height=«19» src=«dopb17322.zip» v:shapes="_x0000_i1145"> шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо пол­ностью удовлетворяется один из заказчиков (тот, в столбце кото­рого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).
§  В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соот­ветственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
§  Во втором случае исключается строка, содержащая заполняемую клетку, и счи­тается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потреб­ности заказчика, в столбце которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив <shape id="_x0000_i1146" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image163.wmz» o:><img width=«61» height=«19» src=«dopb17338.zip» v:shapes="_x0000_i1146"> раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потреб­ность последнего заказчика. В результате, совершив <shape id="_x0000_i1147" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image165.wmz» o:><img width=«59» height=«19» src=«dopb17322.zip» v:shapes="_x0000_i1147"> шагов, мы и получим искомый опорный план.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется рав­ной запасу груза на очередной базе. Тогда после заполнения оче­редной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная “потребность” в количестве нуля единиц груза, которая и удовле­творяется на одном из следующих шагов. Этот нуль (“запас” или “потребностью” – безразлично) надо записать в очередную заполняе­мую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.
Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.
      1.Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) остав­шейся части таблицы. При таком методе заполнение таблицы начи­нается с клетки неизвестного <shape id="_x0000_i1148" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image119.wmz» o:><img width=«21» height=«23» src=«dopb17282.zip» v:shapes="_x0000_i1148"> и заканчивается в клетке неизвест­ного <shape id="_x0000_i1149" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image166.wmz» o:><img width=«25» height=«24» src=«dopb17339.zip» v:shapes="_x0000_i1149">, т. е. идет как бы по диагонали таблицы перевозок.
Пример.
Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным <shape id="_x0000_i1158" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image119.wmz» o:><img width=«21» height=«23» src=«dopb17282.zip» v:shapes="_x0000_i1158">. Первая база <shape id="_x0000_i1159" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image037.wmz» o:><img width=«19» height=«23» src=«dopb17281.zip» v:shapes="_x0000_i1159"> может полностью удовле­творить потребность первого заказчика <shape id="_x0000_i1160" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image176.wmz» o:><img width=«19» height=«23» src=«dopb17278.zip» v:shapes="_x0000_i1160"> <shape id="_x0000_i1161" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image177.wmz» o:><img width=«173» height=«23» src=«dopb17344.zip» v:shapes="_x0000_i1161">. Полагая <shape id="_x0000_i1162" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image179.wmz» o:><img width=«61» height=«23» src=«dopb17345.zip» v:shapes="_x0000_i1162">, вписываем это значение в клетку <shape id="_x0000_i1163" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image181.wmz» o:><img width=«21» height=«23» src=«dopb17282.zip» v:shapes="_x0000_i1163"> и исключаем из рассмотрения первый столбец. На базе <shape id="_x0000_i1164" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image182.wmz» o:><img width=«19» height=«23» src=«dopb17281.zip» v:shapes="_x0000_i1164"> остается измененный запас <shape id="_x0000_i1165" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image183.wmz» o:><img width=«52» height=«19» src=«dopb17346.zip» v:shapes="_x0000_i1165">. В оставшейся новой таблице с тремя строками <shape id="_x0000_i1166" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image185.wmz» o:><img width=«63» height=«24» src=«dopb17347.zip» v:shapes="_x0000_i1166"> и четырьмя столбцами <shape id="_x0000_i1167" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image187.wmz» o:><img width=«87» height=«24» src=«dopb17348.zip» v:shapes="_x0000_i1167">; северо-западным углом будет клетка для неизвестного <shape id="_x0000_i1168" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image189.wmz» o:><img width=«21» height=«23» src=«dopb17283.zip» v:shapes="_x0000_i1168">. Первая база с запасом <shape id="_x0000_i1169" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image190.wmz» o:><img width=«59» height=«23» src=«dopb17349.zip» v:shapes="_x0000_i1169">может полностью удовлетворить потребность второго заказчика <shape id="_x0000_i1170" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image192.wmz» o:><img width=«20» height=«23» src=«dopb17279.zip» v:shapes="_x0000_i1170"> <shape id="_x0000_i1171" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image193.wmz» o:><img width=«179» height=«23» src=«dopb17350.zip» v:shapes="_x0000_i1171">. Полагаем <shape id="_x0000_i1172" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image195.wmz» o:><img width=«61» height=«23» src=«dopb17351.zip» v:shapes="_x0000_i1172">, вписываем это значе­ние в клетку <shape id="_x0000_i1173" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image197.wmz» o:><img width=«21» height=«23» src=«dopb17283.zip» v:shapes="_x0000_i1173"> и исключаем из рассмотрения второй столбец. На базе <shape id="_x0000_i1174" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image198.wmz» o:><img width=«19» height=«23» src=«dopb17281.zip» v:shapes="_x0000_i1174"> остается новый остаток (запас) <shape id="_x0000_i1175" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image199.wmz» o:><img width=«56» height=«23» src=«dopb17352.zip» v:shapes="_x0000_i1175">. В оставшейся новой таблице с тремя строками <shape id="_x0000_i1176" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image185.wmz» o:><img width=«63» height=«24» src=«dopb17347.zip» v:shapes="_x0000_i1176"> и тремя столбцами <shape id="_x0000_i1177" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image201.wmz» o:><img width=«64» height=«24» src=«dopb17353.zip» v:shapes="_x0000_i1177"> северо-западным углом будет клетка для неизвестного <shape id="_x0000_i1178" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image203.wmz» o:><img width=«21» height=«24» src=«dopb17354.zip» v:shapes="_x0000_i1178">. Теперь третий заказчик <shape id="_x0000_i1179" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image205.wmz» o:><img width=«20» height=«24» src=«dopb17340.zip» v:shapes="_x0000_i1179"> может принять весь запас с базы <shape id="_x0000_i1180" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image206.wmz» o:><img width=«19» height=«23» src=«dopb17281.zip» v:shapes="_x0000_i1180"> <shape id="_x0000_i1181" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image207.wmz» o:><img width=«179» height=«24» src=«dopb17355.zip» v:shapes="_x0000_i1181">. Полагаем <shape id="_x0000_i1182" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image209.wmz» o:><img width=«55» height=«24» src=«dopb17356.zip» v:shapes="_x0000_i1182">, вписываем это значение в клетку <shape id="_x0000_i1183" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image211.wmz» o:><img width=«21» height=«24» src=«dopb17354.zip» v:shapes="_x0000_i1183"> и исключаем из рассмотрения первую строку. У заказ­чика из <shape id="_x0000_i1184" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image168.wmz» o:><img width=«20» height=«24» src=«dopb17340.zip» v:shapes="_x0000_i1184"> осталась еще не удовлетворенной потребность <shape id="_x0000_i1185" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image212.wmz» o:><img width=«52» height=«24» src=«dopb17357.zip» v:shapes="_x0000_i1185">.
Теперь переходим к заполнению клетки для неизвестного <shape id="_x0000_i1186" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image214.wmz» o:><img width=«23» height=«24» src=«dopb17358.zip» v:shapes="_x0000_i1186"> и т.д.
Через шесть шагов у нас останется одна база <shape id="_x0000_i1187" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image216.wmz» o:><img width=«20» height=«24» src=«dopb17343.zip» v:shapes="_x0000_i1187"> с запасом груза (остатком от предыдущего шага) <shape id="_x0000_i1188" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image217.wmz» o:><img width=«61» height=«24» src=«dopb17359.zip» v:shapes="_x0000_i1188">и один пункт <shape id="_x0000_i1189" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image219.wmz» o:><img width=«20» height=«24» src=«dopb17342.zip» v:shapes="_x0000_i1189"> с потреб­ностью<shape id="_x0000_i1190" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image220.wmz» o:><img width=«59» height=«24» src=«dopb17360.zip» v:shapes="_x0000_i1190">. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив <shape id="_x0000_i1191" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image222.wmz» o:><img width=«64» height=«24» src=«dopb17361.zip» v:shapes="_x0000_i1191">. План составлен. Базис образован неизвестными <shape id="_x0000_i1192" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image224.wmz» o:><img width=«176» height=«24» src=«dopb17362.zip» v:shapes="_x0000_i1192">. Правиль­ность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.
Общий объем перевозок в тонно-километрах для этого плана составит <shape id="_x0000_i1193" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image226.wmz» o:><img width=«467» height=«23» src=«dopb17363.zip» v:shapes="_x0000_i1193">.
        2.Метод наименьшей стоимости. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.
Пример.
В данном случае заполнение таблицы начинается с клетки для неизвест­ного <shape id="_x0000_i1202" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image228.wmz» o:><img width=«23» height=«24» src=«dopb17364.zip» v:shapes="_x0000_i1202">, для которого мы имеем значение <shape id="_x0000_i1203" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image230.wmz» o:><img width=«53» height=«24» src=«dopb17365.zip» v:shapes="_x0000_i1203">, наименьше из всех значений <shape id="_x0000_i1204" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image232.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1204">. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе <shape id="_x0000_i1205" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image233.wmz» o:><img width=«20» height=«24» src=«dopb17343.zip» v:shapes="_x0000_i1205"> и вто­рому заказчику <shape id="_x0000_i1206" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image234.wmz» o:><img width=«20» height=«23» src=«dopb17279.zip» v:shapes="_x0000_i1206">. Третья база <shape id="_x0000_i1207" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image235.wmz» o:><img width=«20» height=«24» src=«dopb17343.zip» v:shapes="_x0000_i1207"> может полностью удовлетворить потребность второго заказчика <shape id="_x0000_i1208" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image236.wmz» o:><img width=«20» height=«23» src=«dopb17279.zip» v:shapes="_x0000_i1208"> <shape id="_x0000_i1209" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image237.wmz» o:><img width=«180» height=«24» src=«dopb17366.zip» v:shapes="_x0000_i1209">. Пола­гая <shape id="_x0000_i1210" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image239.wmz» o:><img width=«63» height=«24» src=«dopb17367.zip» v:shapes="_x0000_i1210">, вписываем это значение в клетку <shape id="_x0000_i1211" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image241.wmz» o:><img width=«23» height=«24» src=«dopb17364.zip» v:shapes="_x0000_i1211"> и исключаем из рассмотрения второй столбец. На базе <shape id="_x0000_i1212" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image242.wmz» o:><img width=«20» height=«24» src=«dopb17343.zip» v:shapes="_x0000_i1212"> остается изменённый запас <shape id="_x0000_i1213" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image243.wmz» o:><img width=«59» height=«24» src=«dopb17368.zip» v:shapes="_x0000_i1213">. В оставшейся новой таблице с тремя строками <shape id="_x0000_i1214" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image185.wmz» o:><img width=«63» height=«24» src=«dopb17347.zip» v:shapes="_x0000_i1214"> и четырьмя столбцами <shape id="_x0000_i1215" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image245.wmz» o:><img width=«84» height=«24» src=«dopb17369.zip» v:shapes="_x0000_i1215"> клеткой с наименьшим значе­нием <shape id="_x0000_i1216" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image247.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1216"> клетка, где<shape id="_x0000_i1217" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image248.wmz» o:><img width=«52» height=«24» src=«dopb17370.zip» v:shapes="_x0000_i1217">. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В резуль­тате оказываются заполненными (в приведенной последовательности) следующие клетки:
<shape id="_x0000_i1218" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image250.wmz» o:><img width=«431» height=«24» src=«dopb17371.zip» v:shapes="_x0000_i1218">.
На пятом шаге клеток с наименьшими значениями <shape id="_x0000_i1219" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image252.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1219"> оказалось две <shape id="_x0000_i1220" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image253.wmz» o:><img width=«97» height=«24» src=«dopb17372.zip» v:shapes="_x0000_i1220">. Мы заполнили клетку для <shape id="_x0000_i1221" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image255.wmz» o:><img width=«21» height=«24» src=«dopb17373.zip» v:shapes="_x0000_i1221">, положив <shape id="_x0000_i1222" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image257.wmz» o:><img width=«61» height=«24» src=«dopb17374.zip» v:shapes="_x0000_i1222">. Можно было выбрать для заполнения другую клетку, положив <shape id="_x0000_i1223" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image259.wmz» o:><img width=«61» height=«23» src=«dopb17345.zip» v:shapes="_x0000_i1223">, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит <shape id="_x0000_i1224" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image260.wmz» o:><img width=«493» height=«23» src=«dopb17375.zip» v:shapes="_x0000_i1224">.
Замечание. В диагональном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами (что и имеет место в нашем примере), хотя это и не обязательно.
    Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.
4.Понятие потенциала и цикла.
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы.
Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:
1.      Одно из неизвестных последовательности свободное, а все остальные – базисные.
2.      Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.
3.      Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.
4.      Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.
Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.
Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные — в базисных клетках.
Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно.
Так, например, в таблице перевозок, составленной по диагональному методу при решения задачи из предыдущего пункта, неизвестному <shape id="_x0000_i1225" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image262.wmz» o:><img width=«23» height=«23» src=«dopb17287.zip» v:shapes="_x0000_i1225"> соответствует цикл <shape id="_x0000_i1226" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image263.wmz» o:><img width=«120» height=«24» src=«dopb17376.zip» v:shapes="_x0000_i1226"> и т.д.
Пусть теперь мы имеем некоторую свободную клетку с соответствующим ей циклом. Если мы изменим значение свободного неизвестного, увеличив его на некоторое число <shape id="_x0000_i1227" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image265.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1227">, то, переходя последовательно от одной вершины цикла к другой, мы должны будем в силу неизменности сумм по строкам и по столбцам поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число<shape id="_x0000_i1228" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image267.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1228">. Например, в указанном выше цикле для свободного неизвестного <shape id="_x0000_i1229" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image268.wmz» o:><img width=«23» height=«23» src=«dopb17287.zip» v:shapes="_x0000_i1229"> получим:
старые значения: <shape id="_x0000_i1230" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image269.wmz» o:><img width=«273» height=«24» src=«dopb17378.zip» v:shapes="_x0000_i1230">;
новые значения: <shape id="_x0000_i1231" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image271.wmz» o:><img width=«349» height=«24» src=«dopb17379.zip» v:shapes="_x0000_i1231">
Очевидно, если снабдить вершины цикла поочередно знаками “+” и “–“, приписав вершине в свободной клетке знак “+”, то можно сказать, что в вершинах со знаком “+” число <shape id="_x0000_i1232" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image265.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1232"> прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком “–“   это число <shape id="_x0000_i1233" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image265.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1233"> вычитается из прежнего значения неизвестного, находящегося в этой вершине.
Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.
Если в качестве <shape id="_x0000_i1234" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image265.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1234"> выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком “–“, то, по крайней мере, одно из прежних базисных неизвестных примет значение нуль, и мы можем перевести его в число свободных неизвестных, сделав вместо него базисным то неизвестное, которое было свободным.
Так, например, в рассмотренном выше цикле имеем отрицательные вершины <shape id="_x0000_i1235" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image273.wmz» o:><img width=«23» height=«24» src=«dopb17358.zip» v:shapes="_x0000_i1235"> и <shape id="_x0000_i1236" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image274.wmz» o:><img width=«21» height=«23» src=«dopb17282.zip» v:shapes="_x0000_i1236">; следовательно, выбрав   <shape id="_x0000_i1237" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image275.wmz» o:><img width=«140» height=«23» src=«dopb17380.zip» v:shapes="_x0000_i1237">, мы получаем:
старые значения: <shape id="_x0000_i1238" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image269.wmz» o:><img width=«273» height=«24» src=«dopb17378.zip» v:shapes="_x0000_i1238">;
новые значения: <shape id="_x0000_i1239" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image277.wmz» o:><img width=«277» height=«24» src=«dopb17381.zip» v:shapes="_x0000_i1239">
т. е. вместо прежнего базисного решения получаем новое базисное решение:
Выбор в качестве х минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.
Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.
Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таб­лицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.
Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каж­дое из них остается либо в группе базисных, либо в группе свобод­ных неизвестных, как и до пересчета.
Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.
Пусть <shape id="_x0000_i1248" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image279.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1248"> – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом <shape id="_x0000_i1249" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image281.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1249">. Если вершине цикла, находящейся в <shape id="_x0000_i1250" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image282.wmz» o:><img width=«32» height=«17» src=«dopb17383.zip» v:shapes="_x0000_i1250"> строке и <shape id="_x0000_i1251" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image284.wmz» o:><img width=«39» height=«20» src=«dopb17384.zip» v:shapes="_x0000_i1251"> столбце таблицы перевозок, приписан знак “+”, то значение неизвестного <shape id="_x0000_i1252" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image286.wmz» o:><img width=«19» height=«25» src=«dopb17385.zip» v:shapes="_x0000_i1252">, находящегося в этой вершине, увеличивается на <shape id="_x0000_i1253" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image288.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1253">, что в свою очередь вызывает увеличение затрат на <shape id="_x0000_i1254" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image289.wmz» o:><img width=«27» height=«25» src=«dopb17386.zip» v:shapes="_x0000_i1254">. где <shape id="_x0000_i1255" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image291.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1255"> – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного <shape id="_x0000_i1256" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image292.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1256"> уменьшается на <shape id="_x0000_i1257" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image293.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1257">, что вызывает уменьшение затрат на <shape id="_x0000_i1258" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image294.wmz» o:><img width=«27» height=«25» src=«dopb17386.zip» v:shapes="_x0000_i1258">.
    продолжение
--PAGE_BREAK--Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность <shape id="_x0000_i1259" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image295.wmz» o:><img width=«25» height=«25» src=«dopb17387.zip» v:shapes="_x0000_i1259"> назовем алгебраической суммой тарифов для данного свободного неизвестного <shape id="_x0000_i1260" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image279.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1260">. Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).
Теперь, очевидно, мы можем, заключить, что в целом при пере­счете но циклу, соответствующему свободному неизвестному <shape id="_x0000_i1261" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image279.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1261"> общий объем затрат на перевозки изменится на произведение алгеб­раической суммы тарифов на <shape id="_x0000_i1262" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image281.wmz» o:><img width=«13» height=«15» src=«dopb17377.zip» v:shapes="_x0000_i1262">, т. е. на величину <shape id="_x0000_i1263" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image297.wmz» o:><img width=«35» height=«25» src=«dopb17388.zip» v:shapes="_x0000_i1263">. Следовательно, если алгебраическая сумма тарифов для некоторого свобод­ного неизвестного <shape id="_x0000_i1264" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image299.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1264"> отрицательна <shape id="_x0000_i1265" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image300.wmz» o:><img width=«61» height=«25» src=«dopb17389.zip» v:shapes="_x0000_i1265">, то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна <shape id="_x0000_i1266" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image302.wmz» o:><img width=«61» height=«25» src=«dopb17390.zip» v:shapes="_x0000_i1266">, то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю <shape id="_x0000_i1267" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image304.wmz» o:><img width=«61» height=«25» src=«dopb17391.zip» v:shapes="_x0000_i1267">, то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).
Так, например, для цикла <shape id="_x0000_i1268" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image263.wmz» o:><img width=«120» height=«24» src=«dopb17376.zip» v:shapes="_x0000_i1268"> в рассмотренной задаче алгебраическая сумма тарифов
<shape id="_x0000_i1269" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image306.wmz» o:><img width=«336» height=«24» src=«dopb17392.zip» v:shapes="_x0000_i1269">.
Значит, пересчет по этому циклу снижает расходы. И действитель­но, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет
<shape id="_x0000_i1270" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image308.wmz» o:><img width=«468» height=«23» src=«dopb17393.zip» v:shapes="_x0000_i1270">
тогда как по исходному плану он составил <shape id="_x0000_i1271" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image310.wmz» o:><img width=«75» height=«23» src=«dopb17394.zip» v:shapes="_x0000_i1271">. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в дан­ном случае равна –15, а пересчет по циклу осуществляется с помощью числа <shape id="_x0000_i1272" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image312.wmz» o:><img width=«44» height=«19» src=«dopb17395.zip» v:shapes="_x0000_i1272"> (изменение затрат равно <shape id="_x0000_i1273" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image314.wmz» o:><img width=«109» height=«19» src=«dopb17396.zip» v:shapes="_x0000_i1273">).
Вычисление алгебраической суммы тарифов для каждого из сво­бодных неизвестных можно производить без построения соответ­ствующего цикла, пользуясь, так называемыми, потенциалами. При­пишем каждой базе <shape id="_x0000_i1274" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image316.wmz» o:><img width=«19» height=«24» src=«dopb17300.zip» v:shapes="_x0000_i1274">, некоторое число <shape id="_x0000_i1275" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image317.wmz» o:><img width=«16» height=«24» src=«dopb17397.zip» v:shapes="_x0000_i1275"> и каждому потребителю <shape id="_x0000_i1276" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image319.wmz» o:><img width=«20» height=«25» src=«dopb17301.zip» v:shapes="_x0000_i1276"> некоторое число <shape id="_x0000_i1277" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image320.wmz» o:><img width=«17» height=«25» src=«dopb17398.zip» v:shapes="_x0000_i1277">:
<shape id="_x0000_i1278" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image322.wmz» o:><img width=«287» height=«25» src=«dopb17399.zip» v:shapes="_x0000_i1278">,
так что
<shape id="_x0000_s1043" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1279" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image324.wmz» o:><img width=«79» height=«25» src=«dopb17400.zip» v:shapes="_x0000_i1279">,
где <shape id="_x0000_i1280" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image326.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1280"> – тарифы, соответствующие клеткам, заполненным базис­ными неизвестными. Эти числа <shape id="_x0000_i1281" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image317.wmz» o:><img width=«16» height=«24» src=«dopb17397.zip» v:shapes="_x0000_i1281"> и <shape id="_x0000_i1282" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image320.wmz» o:><img width=«17» height=«25» src=«dopb17398.zip» v:shapes="_x0000_i1282"> называются потенциалами соответствующих баз и потребителей.
Зная потенциалы, легко вычислить алгебраическую сумму тари­фов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному <shape id="_x0000_i1283" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image279.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1283">, заменить тарифы базисных клеток их выражениями через потенциалы по формулам (4.1), то, в силу чередования знаков при вершинах цикла, все потенциалы,  кроме  <shape id="_x0000_i1284" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image327.wmz» o:><img width=«20» height=«25» src=«dopb17401.zip» v:shapes="_x0000_i1284"> и <shape id="_x0000_i1285" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image329.wmz» o:><img width=«17» height=«25» src=«dopb17402.zip» v:shapes="_x0000_i1285"> сократятся, и мы получим:
<shape id="_x0000_i1286" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image331.wmz» o:><img width=«137» height=«25» src=«dopb17403.zip» v:shapes="_x0000_i1286">.
Так, например, для цикла <shape id="_x0000_i1287" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image263.wmz» o:><img width=«120» height=«24» src=«dopb17376.zip» v:shapes="_x0000_i1287"> в рассмотренной выше задаче имеем
<shape id="_x0000_i1288" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image333.wmz» o:><img width=«507» height=«24» src=«dopb17404.zip» v:shapes="_x0000_i1288">.
            Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного <shape id="_x0000_i1289" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image335.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1289"> свободная, то сумму потенциалов
<shape id="_x0000_s1044" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1290" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image336.wmz» o:><img width=«91» height=«25» src=«dopb17405.zip» v:shapes="_x0000_i1290">
называют косвенным тарифом этой клетки. Следовательно, алгеб­раическая сумма тарифов для свободной клетки <shape id="_x0000_i1291" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image338.wmz» o:><img width=«24» height=«25» src=«dopb17382.zip» v:shapes="_x0000_i1291"> равна разности ее настоящего (“истинного”) и косвенного тарифов:
<shape id="_x0000_s1045" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1292" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image339.wmz» o:><img width=«99» height=«25» src=«dopb17406.zip» v:shapes="_x0000_i1292">
Из (4.3) следует, что если косвенный тариф для данной свобод­ной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрица­тельна; если же косвенный тариф меньше истинного, то алгебраи­ческая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю.
Потенциалы можно найти из системы равенств (4.1), рассматри­вая их как систему <shape id="_x0000_i1293" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image150.wmz» o:><img width=«59» height=«19» src=«dopb17322.zip» v:shapes="_x0000_i1293"> уравнений с <shape id="_x0000_i1294" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image341.wmz» o:><img width=«39» height=«16» src=«dopb17305.zip» v:shapes="_x0000_i1294"> неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив, например, <shape id="_x0000_i1295" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image342.wmz» o:><img width=«44» height=«23» src=«dopb17407.zip» v:shapes="_x0000_i1295">; тогда остальные потенциалы легко опре­деляются из уравнений(4.1).
Например, для плана, полученного по диагональному методу в рассмотренной выше задаче, имеем
<shape id="_x0000_i1296" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image344.wmz» o:><img width=«91» height=«171» src=«dopb17408.zip» v:shapes="_x0000_i1296">
Система содержит семь уравнений с восемью неизвестными. Выбирая произвольно значение <shape id="_x0000_i1297" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image346.wmz» o:><img width=«19» height=«23» src=«dopb17409.zip» v:shapes="_x0000_i1297">, находим последовательно из пер­вых трех уравнений значения <shape id="_x0000_i1298" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image348.wmz» o:><img width=«77» height=«23» src=«dopb17410.zip» v:shapes="_x0000_i1298">, <shape id="_x0000_i1299" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image350.wmz» o:><img width=«79» height=«23» src=«dopb17411.zip» v:shapes="_x0000_i1299">, <shape id="_x0000_i1300" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image352.wmz» o:><img width=«76» height=«24» src=«dopb17412.zip» v:shapes="_x0000_i1300">, затем из четвертого уравнения – <shape id="_x0000_i1301" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image354.wmz» o:><img width=«80» height=«24» src=«dopb17413.zip» v:shapes="_x0000_i1301">, из пятого уравнения – <shape id="_x0000_i1302" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image356.wmz» o:><img width=«80» height=«23» src=«dopb17414.zip» v:shapes="_x0000_i1302">, из шестого уравнения <shape id="_x0000_i1303" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image358.wmz» o:><img width=«77» height=«24» src=«dopb17415.zip» v:shapes="_x0000_i1303"> и, наконец, из седь­мого уравнения – <shape id="_x0000_i1304" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image360.wmz» o:><img width=«80» height=«24» src=«dopb17416.zip» v:shapes="_x0000_i1304">.
Положив, например, <shape id="_x0000_i1305" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image362.wmz» o:><img width=«44» height=«23» src=«dopb17407.zip» v:shapes="_x0000_i1305">, получаем значения потенциалов:
<shape id="_x0000_i1306" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image363.wmz» o:><img width=«61» height=«72» src=«dopb17417.zip» v:shapes="_x0000_i1306">         <shape id="_x0000_i1307" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image365.wmz» o:><img width=«52» height=«120» src=«dopb17418.zip» v:shapes="_x0000_i1307">
Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами:
<shape id="_x0000_i1308" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image367.wmz» o:><img width=«153» height=«96» src=«dopb17419.zip» v:shapes="_x0000_i1308"><shape id="_x0000_i1309" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image369.wmz» o:><img width=«156» height=«96» src=«dopb17420.zip» v:shapes="_x0000_i1309">
Для клеток с неизвестными <shape id="_x0000_i1310" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image371.wmz» o:><img width=«23» height=«23» src=«dopb17287.zip» v:shapes="_x0000_i1310"> и <shape id="_x0000_i1311" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image372.wmz» o:><img width=«23» height=«24» src=«dopb17364.zip» v:shapes="_x0000_i1311"> косвенные тарифы больше истинных. Следовательно, для них мы будемиметь отрицательные алгебраические суммы тарифов:
<shape id="_x0000_i1312" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image373.wmz» o:><img width=«193» height=«48» src=«dopb17421.zip» v:shapes="_x0000_i1312">
Значение <shape id="_x0000_i1313" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image375.wmz» o:><img width=«65» height=«23» src=«dopb17422.zip» v:shapes="_x0000_i1313"> мы уже имели раньше, вычисляя алгебраиче­скую сумму тарифов для этой клетки непосредственно по циклу.
Замечание 1. Подсчитывая косвенные тарифы как суммы соответ­ствующих потенциалов, полезно не пропускать и клетки с базисны­ми неизвестными (заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу; последнее может служить проверкой правильности найденных значении потенциалов.
Замечание 2. Можно показать, что если сумму всех затрат по данному плану перевозок выразить через свободные неизвестные [для этого надо исключить базисные неизвестные из выражения для S, см. формулу (2.4)], то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.
5.     Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения.
Из сказанного в предыдущем пункте вытекает следующий кри­терий оптимальности базисного решения транспортной задачи: если для некоторого базисного плана перевозок алгебраические суммы тарифов по циклам для всех свободных клеток неотрицательны, то этот план оптимальный.
Отсюда вытекает способ отыскания оптимального решения транспортной задачи, состоящий в том, что, имея некоторое базис­ное решение, вычисляют алгебраические суммы тарифов для всех свободных клеток. Если критерий оптимальности выполнен, то дан­ное решение является оптимальным; если же имеются клетки с отрицательными алгебраическими суммами тарифов, то переходят к новому базису, производя пересчет по циклу, соответствующему одной из таких клеток. Полученное таким образом новое базисное решение будет лучше исходного – затраты на его реализацию будут меньшими. Для нового решения также проверяют выполнимость критерия оптимальности и в случае необходимости снова совершают пересчет по циклу для одной из клеток с отрицательной алгебраиче­ской суммой тарифов и т. д.
Через конечное число шагов приходят к искомому оптимальному базисному решению.
В случае если алгебраические суммы тарифов для всех свобод­ных клеток положительны, мы имеем единственное оптимальное решение; если же алгебраические суммы тарифов для всех свобод­ных клеток неотрицательны, но среди них имеются алгебраические суммы тарифов, равные нулю, то оптимальное решение не единствен­ное: при пересчете по циклу для клетки с нулевой алгебраической суммой тарифов мы получим оптимальное же решение, но от­личное от исходного (затраты по обоим планам будут одина­ковыми).
В зависимости от методов подсчета алгебраических сумм тари­фов для свободных клеток различают два метода отыскания опти­мальногорешения транспортной задачи:
1.      Распределительный метод. При этомметоде для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.
2.      Метод потенциалов. При этом методе предварительно находят потенциалы баз и потребителей, а затем вычисляют для каждой пустой клетки алгебраическую сумму тарифов с помощью потен­циалов.
Преимущества метода потенциалов по сравнению с распредели­тельным методом состоят в том, что отпадает необходимость построения циклов для каждой из пустых клеток и упрощается вычисление алгебраических сумм тарифов. Цикл строится только один – тот, по которому производится пересчет.
Применяя метод потенциалов, можно говорить не о знаке алгебраических сумм тарифов, а о сравнении косвенных тарифов с истинными. Требование неотрицательности алгебраических сумм тарифов заменяется условием, что косвенные тарифы не превосхо­дят истинных.
 Следует иметь в виду, что потенциалы (так же как и циклы) для каждого нового базисного плана определяются заново.
Выше рассматривалась закрытая модель  транспортной  задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель)  баланс  транспортной  задачи  может  нарушаться  в  2-ух  направлениях:
            1. Сумма  запасов  в  пунктах  отправления  превышает  сумму  поданных  заявок (транспортная  задача  с  избытком  запасов):
               å аi > å bj  ( где i=1,...,m; j=1,...,n );
   2. Сумма  поданных  заявок  превышает  наличные  запасы (транспортная  задача  с  избытком  заявок):
                        å аi < å bj  ( где i=1,...,m; j=1,...,n );
Рассмотрим  последовательно  эти  два  случая:
Транспортная  задача   с  избытком  запасов.
Сведем  её  к  ранее  рассмотренной  транспортной  задаче  с  правильным  балансом.  Для  этого, сверх  имеющихся  n  пунктов  назначения  В1, B2,…, Bn,  введём  ещё   один, фиктивный, пункт  назначения   Bn+1, которому   припишем  фиктивную  заявку, равную  избытку  запасов  над  заявками 
               bn+1 = å аi — å bj   ( где i=1,...,m; j=1,...,n ),
а  стоимость  перевозок  из  всех  пунктов  отправления  в  фиктивный  пункт  назначения  bn+1  будем  считать  равной  нулю. Введением  фиктивного  пункта  назначения  Bn+1  с  его  заявкой  bn+1  мы  сравняли  баланс транспортной задачи, и теперь ее можно решать, как обычную  транспортную  задачу  с  правильным  балансом.
Транспортная  задача  с  избытком  заявок.
Эту задачу можно свести к обычной транспортной задаче с правильным  балансом,  если  ввести  фиктивный пункт отправления Am+1 с  запасом am+1 равным недостающему запасу, и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равной  нулю.  
6.     Задача, двойственная к транспортной.
           Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления <shape id="_x0000_i1314" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image377.wmz» o:><img width=«19» height=«24» src=«dopb17300.zip» v:shapes="_x0000_i1314"> и назначения <shape id="_x0000_i1315" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image378.wmz» o:><img width=«20» height=«25» src=«dopb17301.zip» v:shapes="_x0000_i1315"> отвечает определенное огра­ничение
<shape id="_x0000_s1046" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1316" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image379.wmz» o:><img width=«173» height=«96» src=«dopb17423.zip» v:shapes="_x0000_i1316">
В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойствен­ной задаче. Тем самым устанавливается соответствие между всеми пунктами <shape id="_x0000_i1317" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image377.wmz» o:><img width=«19» height=«24» src=«dopb17300.zip» v:shapes="_x0000_i1317"> и <shape id="_x0000_i1318" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image378.wmz» o:><img width=«20» height=«25» src=«dopb17301.zip» v:shapes="_x0000_i1318"> и всеми неиз­вестными двойственной задачи.
Обозначим неизвестную в двойственной задаче, отвечаю­щую пункту отправления <shape id="_x0000_i1319" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image381.wmz» o:><img width=«19» height=«24» src=«dopb17300.zip» v:shapes="_x0000_i1319">, через <shape id="_x0000_i1320" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image382.wmz» o:><img width=«87» height=«24» src=«dopb17424.zip» v:shapes="_x0000_i1320">, а пункту назначения <shape id="_x0000_i1321" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image384.wmz» o:><img width=«20» height=«25» src=«dopb17301.zip» v:shapes="_x0000_i1321"> – через <shape id="_x0000_i1322" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image385.wmz» o:><img width=«72» height=«25» src=«dopb17425.zip» v:shapes="_x0000_i1322">.
Каждому неизвестному в транспортной задаче соответ­ствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное <shape id="_x0000_i1323" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image387.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1323"> входит ровно в два ограничения системы (6.1): одно из них отвечает пункту <shape id="_x0000_i1324" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image388.wmz» o:><img width=«19» height=«24» src=«dopb17300.zip» v:shapes="_x0000_i1324">, а другое – пункту <shape id="_x0000_i1325" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image389.wmz» o:><img width=«20» height=«25» src=«dopb17301.zip» v:shapes="_x0000_i1325">. В обоих этих уравнениях коэффициент при <shape id="_x0000_i1326" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image390.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1326"> равен 1. Поэтому соответствующее <shape id="_x0000_i1327" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image391.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1327"> ограничение в двой­ственной задаче имеет вид
<shape id="_x0000_s1047" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">   

<shape id="_x0000_i1328" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image392.wmz» o:><img width=«79» height=«25» src=«dopb17426.zip» v:shapes="_x0000_i1328"> <shape id="_x0000_i1329" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image394.wmz» o:><img width=«140» height=«21» src=«dopb17427.zip» v:shapes="_x0000_i1329">.
Правая часть неравенства (6.2) равна  <shape id="_x0000_i1330" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image158.wmz» o:><img width=«17» height=«25» src=«dopb17324.zip» v:shapes="_x0000_i1330">, потому что именно с этим коэффициентом неизвестная <shape id="_x0000_i1331" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image396.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1331"> входит в миними­зируемую формулу (2.4).
Оптимизируемая форма двойственной задачи имеет вид <shape id="_x0000_s1048" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1332" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image397.wmz» o:><img width=«145» height=«47» src=«dopb17428.zip» v:shapes="_x0000_i1332">
        Таким образом, задача двойственная к транспортной форму­лируется следующим образом. При ограничениях (6.2) макси­мизировать формулу (6.3). Подчеркнем, что знак значений неиз­вестных <shape id="_x0000_i1333" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image399.wmz» o:><img width=«87» height=«24» src=«dopb17424.zip» v:shapes="_x0000_i1333"> и  <shape id="_x0000_i1334" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image385.wmz» o:><img width=«72» height=«25» src=«dopb17425.zip» v:shapes="_x0000_i1334"> может быть произвольным.
          Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базис­ные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным <shape id="_x0000_i1335" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image400.wmz» o:><img width=«21» height=«24» src=«dopb17429.zip» v:shapes="_x0000_i1335"> заменить точными равенствами.
В итоге приходим к соотношению:
<shape id="_x0000_s1049" type="#_x0000_t202" o:allowincell=«f» filled=«f» stroked=«f» strokeweight=".5pt">  <shape id="_x0000_i1336" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image402.wmz» o:><img width=«79» height=«25» src=«dopb17426.zip» v:shapes="_x0000_i1336"> (для всех свободных неизвестных <shape id="_x0000_i1337" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«3945.files/image387.wmz» o:><img width=«19» height=«25» src=«dopb17299.zip» v:shapes="_x0000_i1337">)
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточ­ным условием оптимальности.
7.Пример решения транспортной задачи.
         В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.
<line id="_x0000_s1050" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1050"> Магазины
Склад
B1
(b1=40)
B2
(b2=50)
B3
(b3=15)
B4
(b4=75)
B5
(b5=40)
А1 (а1=50)
1,0
2,0
3,0
2,5
3,5
А2(а2=20)
0,4
3,0
1,0
2,0
3,0
А3(а3=75)
0,7
1,0
1,0
0,8
1,5
А4(а4=80)
1,2
2,0
2,0
1,5
2,5
В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу:
<line id="_x0000_s1051" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1051"> Магазины
Склад
B1
(b1=40)
B2
(b2=50)
B3
(b3=15)
B4
(b4=75)
B5
(b5=40)
B6
(b6=5)
А1 (а1=50)
1,0
2,0
3,0
2,5
3,5
0
А2(а2=20)
0,4
3,0
1,0
2,0
3,0
0
А3(а3=75)
0,7
1,0
1,0
0,8
1,5
0
А4(а4=80)
1,2
2,0
2,0
1,5
2,5
0
Математическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj.  Тогда
<shapetype id="_x0000_t185" coordsize=«21600,21600» o:spt=«185» adj=«3600» path=«m@0,nfqx0@0l0@2qy@0,21600em@1,nfqx21600@0l21600@2qy@1,21600em@0,nsqx0@0l0@2qy@0,21600l@1,21600qx21600@2l21600@0qy@1,xe» filled=«f»><path o:extrusionok=«f» gradientshapeok=«t» limo=«10800,10800» o:connecttype=«custom» o:connectlocs="@8,0;0,@9;@8,@7;@6,@9" textboxrect="@3,@3,@4,@5"><shape id="_x0000_s1052" type="#_x0000_t185" o:allowincell=«f»><img width=«150» height=«65» src=«dopb17431.zip» v:shapes="_x0000_s1052">             x11 x12 x13 x14 x15 x16
             x21 x22 x23 x24 x25 x26
       X =   x31 x32 x33 x34 x35 x36  — матрица перевозок.
             x41 x42 x43 x44 x45 x46
min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45)                (1)
<shapetype id="_x0000_t87" coordsize=«21600,21600» o:spt=«87» adj=«1800,10800» path=«m21600,qx10800@0l10800@2qy0@11,10800@3l10800@1qy21600,21600e» filled=«f»><path arrowok=«t» o:connecttype=«custom» o:connectlocs=«21600,0;0,10800;21600,21600» textboxrect=«13963,@4,21600,@5»><shape id="_x0000_s1053" type="#_x0000_t87" o:allowincell=«f»><img width=«17» height=«162» src=«dopb17432.zip» v:shapes="_x0000_s1053">x11+x12+x13+x14+x15+x16=50
x21+x22+x23+x24+x25+x26=20
x31+x32+x33+x34+x35+x36=75
x41+x42+x43+x44+x45+x46=80
x11+x21+x31+x41=40               (2)
x12+x22+x32+x42=50
x13+x23+x33+x43=15
x14+x24+x34+x44=75
x15+x25+x35+x45=40
x16+x26+x36+x46=5
xij≥0  (i=1,2,3,4; j=1,2,3,4,5,6 )    (3)
Двойственная ЗЛП:
max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6)               (1*)
<rect id="_x0000_s1054" o:allowincell=«f» filled=«f» stroked=«f»><rect id="_x0000_s1056" o:allowincell=«f» filled=«f» stroked=«f»><rect id="_x0000_s1055" o:allowincell=«f» filled=«f» stroked=«f»><img width=«284» height=«113» src=«dopb17433.zip» v:shapes="_x0000_s1054 _x0000_s1056 _x0000_s1055">     продолжение
--PAGE_BREAK-- 

<shape id="_x0000_s1057" type="#_x0000_t87" o:allowincell=«f»><img width=«17» height=«88» src=«dopb17434.zip» v:shapes="_x0000_s1057">u1+v1≤1               
u1+v2≤2                               
u1+v3≤3                                                       (2*)
u1+v4≤2,5
u1+v5≤3,5
u1+v6≤0              
ui,vj – произвольные (i=1,2,3,4; j=1,2,3,4,5,6 )                                                  (3*)
Будем искать первоначальный план по методу наименьшей стоимости:
1) x21=20и 2-ую строку исключаем.2) x31=20и 1-ый столбец исключаем.
3) x34=55и 3-ю строку исключаем.4) x44=20и 4-ый столбец исключаем.
5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0. 6) x43=150 и 3-ий столбец исключаем.7) x45=40 и 5-ый столбец исключаем.x46=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.
<line id="_x0000_s1058" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1058"> Магазины
Склад
B1
(b1=40)
B2
(b2=50)
B3
(b3=15)
B4
(b4=75)
B5
(b5=40)
B6
(b6=5)
А1 (а1=50)
<line id="_x0000_s1059" from=«30.6pt,4pt» to=«30.6pt,103pt» o:allowincell=«f»><img width=«2» height=«134» src=«dopb17435.zip» v:shapes="_x0000_s1059">1,0
<line id="_x0000_s1060" from=«3.6pt,-.55pt» to=«390.6pt,-.55pt» o:allowincell=«f»><img width=«518» height=«2» src=«dopb17436.zip» v:shapes="_x0000_s1060">
<line id="_x0000_s1061" from=«24.8pt,4pt» to=«24.8pt,103pt» o:allowincell=«f»><img width=«2» height=«134» src=«dopb17437.zip» v:shapes="_x0000_s1061"><rect id="_x0000_s1062" o:allowincell=«f»>  2,0
<line id="_x0000_s1063" from=«27.95pt,4pt» to=«27.95pt,103pt» o:allowincell=«f»><img width=«2» height=«134» src=«dopb17437.zip» v:shapes="_x0000_s1063">3,0
<line id="_x0000_s1064" from=«31.3pt,4.45pt» to=«31.3pt,103.45pt» o:allowincell=«f»><img width=«2» height=«134» src=«dopb17438.zip» v:shapes="_x0000_s1064">2,5
<line id="_x0000_s1065" from=«28.25pt,.45pt» to=«28.25pt,99.45pt» o:allowincell=«f»><img width=«2» height=«134» src=«dopb17438.zip» v:shapes="_x0000_s1065">3,5
0
А2(а2=20)
<line id="_x0000_s1066" from=«3.6pt,12.35pt» to=«390.6pt,12.35pt» o:allowincell=«f»><img width=«518» height=«2» src=«dopb17436.zip» v:shapes="_x0000_s1066">0,4
<rect id="_x0000_s1067" o:allowincell=«f»> 
3,0
1,0
2,0
3,0
0
А3(а3=75)
<line id="_x0000_s1068" from=«3.6pt,11.65pt» to=«390.6pt,11.65pt» o:allowincell=«f»><img width=«518» height=«2» src=«dopb17439.zip» v:shapes="_x0000_s1068">0,7
<rect id="_x0000_s1069" o:allowincell=«f»> 
<rect id="_x0000_s1070" o:allowincell=«f»>  1,0
1,0
<rect id="_x0000_s1071" o:allowincell=«f»>  0,8
1,5
0
А4(а4=80)
1,2
2,0
<rect id="_x0000_s1072" o:allowincell=«f»>  2,0
<rect id="_x0000_s1073" o:allowincell=«f»>  1,5
<rect id="_x0000_s1074" o:allowincell=«f»>  2,5
<rect id="_x0000_s1075" o:allowincell=«f»>  0
Стоимость 1-ого плана:
 D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.
Будем улучшать этот план методом потенциалов: ui — потенциал Аi ,vj — потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положим u1=0, тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:
 Магазины
Склад
B1
(b1=40)
v1=1,7
B2
(b2=50)
v2=2
B3
(b3=15)
v3=2,3
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
А1 (а1=50)
U1=0
1,0
2,0
3,0
2,5
3,5
0
А2(а2=20)
U2=-1,3
0,4
3,0
1,0
2,0
3,0
0
<rect id="_x0000_s1096" o:allowincell=«f»>  А3(а3=75)
U3=-1
<oval id="_x0000_s1097" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1097"><rect id="_x0000_s1098" o:allowincell=«f»>  0,7
<line id="_x0000_s1099" from=«48.6pt,6.75pt» to=«102.6pt,6.75pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«75» height=«2» src=«dopb17441.zip» v:shapes="_x0000_s1099"><rect id="_x0000_s1100" o:allowincell=«f»> 
<oval id="_x0000_s1101" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1101"><rect id="_x0000_s1102" o:allowincell=«f»>  <rect id="_x0000_s1103" o:allowincell=«f»>  1,0
<rect id="_x0000_s1104" o:allowincell=«f»>  1,0
<rect id="_x0000_s1105" o:allowincell=«f»>  <rect id="_x0000_s1106" o:allowincell=«f»>  0,8
<rect id="_x0000_s1107" o:allowincell=«f»>  1,5
0
<rect id="_x0000_s1108" o:allowincell=«f»>  А4(а4=80)
U4=-0,3
<rect id="_x0000_s1109" o:allowincell=«f»>  1,2
<rect id="_x0000_s1110" o:allowincell=«f»>  2,0
<rect id="_x0000_s1111" o:allowincell=«f»>  <rect id="_x0000_s1112" o:allowincell=«f»>  2,0
<rect id="_x0000_s1113" o:allowincell=«f»>  <rect id="_x0000_s1114" o:allowincell=«f»>  1,5
<rect id="_x0000_s1115" o:allowincell=«f»>  <rect id="_x0000_s1116" o:allowincell=«f»>  2,5
<rect id="_x0000_s1117" o:allowincell=«f»>  0
В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0, u1+v6-c16 =0,3>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0,
u4+v1-c41 =0,2>0.  =>  По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1В1, сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу:
<line id="_x0000_s1118" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1118"> Магазины
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=2,3
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
<rect id="_x0000_s1119" o:allowincell=«f»>  А1 (а1=50)
U1=0
<oval id="_x0000_s1120" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1120"><line id="_x0000_s1121" from=«30.55pt,3.7pt» to=«30.55pt,48.55pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«3» height=«63» src=«dopb17443.zip» v:shapes="_x0000_s1121"><line id="_x0000_s1122" from=«30.55pt,3.7pt» to=«111.55pt,3.7pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«111» height=«3» src=«dopb17444.zip» v:shapes="_x0000_s1122"><rect id="_x0000_s1123" o:allowincell=«f»>  1,0
<rect id="_x0000_s1124" o:allowincell=«f»> 
<oval id="_x0000_s1125" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1125"><line id="_x0000_s1126" from=«43.3pt,3.7pt» to=«43.3pt,66.55pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«3» height=«87» src=«dopb17445.zip» v:shapes="_x0000_s1126"><rect id="_x0000_s1127" o:allowincell=«f»>  <rect id="_x0000_s1128" o:allowincell=«f»>  2,0
<rect id="_x0000_s1129" o:allowincell=«f»>  3,0
<rect id="_x0000_s1130" o:allowincell=«f»>  2,5
<rect id="_x0000_s1131" o:allowincell=«f»>  3,5
0
<rect id="_x0000_s1132" o:allowincell=«f»>  А2(а2=20)
U2=-0,6
<oval id="_x0000_s1133" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1133"><rect id="_x0000_s1134" o:allowincell=«f»>  <rect id="_x0000_s1135" o:allowincell=«f»>  0,4
<line id="_x0000_s1136" from=«30.55pt,7.35pt» to=«165.6pt,7.35pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«183» height=«3» src=«dopb17446.zip» v:shapes="_x0000_s1136">
<rect id="_x0000_s1137" o:allowincell=«f»>  3,0
<oval id="_x0000_s1138" o:allowincell=«f»><img width=«25» height=«23» src=«dopb17447.zip» alt=«Овал: +» v:shapes="_x0000_s1138"><line id="_x0000_s1139" from=«27.95pt,20.9pt» to=«27.95pt,65.9pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«3» height=«63» src=«dopb17448.zip» v:shapes="_x0000_s1139"><rect id="_x0000_s1140" o:allowincell=«f»>  1,0
<rect id="_x0000_s1141" o:allowincell=«f»>  2,0
<rect id="_x0000_s1142" o:allowincell=«f»>  3,0
0
<rect id="_x0000_s1143" o:allowincell=«f»>  А3(а3=75)
U3=-1
<rect id="_x0000_s1144" o:allowincell=«f»>  0,7
<oval id="_x0000_s1145" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1145"><line id="_x0000_s1146" from=«43.3pt,11.2pt» to=«178.65pt,11.2pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«184» height=«3» src=«dopb17449.zip» v:shapes="_x0000_s1146"><rect id="_x0000_s1147" o:allowincell=«f»>  <rect id="_x0000_s1148" o:allowincell=«f»>  1,0
<rect id="_x0000_s1149" o:allowincell=«f»>  1,0
<oval id="_x0000_s1150" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1150"><line id="_x0000_s1151" from=«40.5pt,11.2pt» to=«40.5pt,38.2pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«2» height=«39» src=«dopb17450.zip» v:shapes="_x0000_s1151"><rect id="_x0000_s1152" o:allowincell=«f»>  <rect id="_x0000_s1153" o:allowincell=«f»>  0,8
<rect id="_x0000_s1154" o:allowincell=«f»>  1,5
0
<rect id="_x0000_s1155" o:allowincell=«f»>  А4(а4=80)
U4=-0,3
<rect id="_x0000_s1156" o:allowincell=«f»>  1,2
<rect id="_x0000_s1157" o:allowincell=«f»>  2,0
<oval id="_x0000_s1158" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1158"><line id="_x0000_s1159" from=«27.95pt,10.5pt» to=«108.95pt,10.5pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«111» height=«2» src=«dopb17451.zip» v:shapes="_x0000_s1159"><rect id="_x0000_s1160" o:allowincell=«f»>  <rect id="_x0000_s1161" o:allowincell=«f»>  2,0
<oval id="_x0000_s1162" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1162"><rect id="_x0000_s1163" o:allowincell=«f»>  <rect id="_x0000_s1164" o:allowincell=«f»>  1,5
<rect id="_x0000_s1165" o:allowincell=«f»>  <rect id="_x0000_s1166" o:allowincell=«f»>  2,5
<rect id="_x0000_s1167" o:allowincell=«f»>  0
Стоимость 2-ого плана:
D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.
Имеем:u1+v6-c16 =0,3>0, u2+v3-c23 =0,7>0,  u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А2В3, сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u2+v3=1, u4+v4=1,5, u4+v5=2,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=1,6, v5=2,8, v6=0,3.    Составим таблицу:
<line id="_x0000_s1168" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1168"> Магазины
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=1,6
B4
(b4=75)
v4=1,8
B5
(b5=40)
v5=2,8
B6
(b6=5)
v6=0,3
<rect id="_x0000_s1169" o:allowincell=«f»>  А1 (а1=50)
U1=0
<rect id="_x0000_s1170" o:allowincell=«f»>  1,0
<rect id="_x0000_s1171" o:allowincell=«f»> 
<rect id="_x0000_s1172" o:allowincell=«f»>  <rect id="_x0000_s1173" o:allowincell=«f»>  2,0
<rect id="_x0000_s1174" o:allowincell=«f»>  3,0
<rect id="_x0000_s1175" o:allowincell=«f»>  2,5
<rect id="_x0000_s1176" o:allowincell=«f»>  3,5
0
<rect id="_x0000_s1177" o:allowincell=«f»>  А2(а2=20)
U2=-0,6
<rect id="_x0000_s1178" o:allowincell=«f»>  <rect id="_x0000_s1179" o:allowincell=«f»>  0,4
<rect id="_x0000_s1180" o:allowincell=«f»>  3,0
<rect id="_x0000_s1181" o:allowincell=«f»>  <rect id="_x0000_s1182" o:allowincell=«f»>  1,0
<rect id="_x0000_s1183" o:allowincell=«f»>  2,0
<rect id="_x0000_s1184" o:allowincell=«f»>  3,0
0
<rect id="_x0000_s1185" o:allowincell=«f»>  А3(а3=75)
U3=-1
<rect id="_x0000_s1186" o:allowincell=«f»>  0,7
<rect id="_x0000_s1187" o:allowincell=«f»>  <rect id="_x0000_s1188" o:allowincell=«f»>  1,0
<rect id="_x0000_s1189" o:allowincell=«f»>  1,0
<oval id="_x0000_s1190" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1190"><line id="_x0000_s1191" from=«13.1pt,20.05pt» to=«13.1pt,47.05pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«3» height=«39» src=«dopb17452.zip» v:shapes="_x0000_s1191"><line id="_x0000_s1192" from=«13.3pt,20.2pt» to=«121.3pt,20.2pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«147» height=«3» src=«dopb17453.zip» v:shapes="_x0000_s1192"><rect id="_x0000_s1193" o:allowincell=«f»>  <rect id="_x0000_s1194" o:allowincell=«f»>  0,8
<oval id="_x0000_s1195" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1195"><line id="_x0000_s1196" from=«52.3pt,20.2pt» to=«52.3pt,47.2pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«3» height=«39» src=«dopb17454.zip» v:shapes="_x0000_s1196"><rect id="_x0000_s1197" o:allowincell=«f»>  1,5
0
<rect id="_x0000_s1198" o:allowincell=«f»>  А4(а4=80)
U4=-0,3
<rect id="_x0000_s1199" o:allowincell=«f»>  1,2
<rect id="_x0000_s1200" o:allowincell=«f»>  2,0
<rect id="_x0000_s1201" o:allowincell=«f»>  2,0
<oval id="_x0000_s1202" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17442.zip» alt=«Овал: +» v:shapes="_x0000_s1202"><line id="_x0000_s1203" from=«13.1pt,19.35pt» to=«121.1pt,19.35pt» o:allowincell=«f» strokeweight=«1.5pt»><img width=«147» height=«3» src=«dopb17455.zip» v:shapes="_x0000_s1203"><rect id="_x0000_s1204" o:allowincell=«f»>  <rect id="_x0000_s1205" o:allowincell=«f»>  1,5
<oval id="_x0000_s1206" o:allowincell=«f»><img width=«25» height=«24» src=«dopb17440.zip» alt=«Овал: -» v:shapes="_x0000_s1206"><rect id="_x0000_s1207" o:allowincell=«f»>  <rect id="_x0000_s1208" o:allowincell=«f»>  2,5
<rect id="_x0000_s1209" o:allowincell=«f»>  0
Стоимость 3-его плана:
 D3=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.
Имеем:u1+v6-c16 =0,3>0,u3+v5-c35 =0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А3В5, сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А4В5 нулевую перевозку. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u4+v5=2,5, u2+v3=1, u4+v4=1,5, u3+v5=1,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,5, u3=-1,u4=0, v3=1,6, v5=2,5, v6=0. Составим таблицу:
<line id="_x0000_s1210" from="-5.7pt,1.4pt" to=«74.4pt,40.4pt» o:allowincell=«f»><img width=«109» height=«54» src=«dopb17430.zip» v:shapes="_x0000_s1210"> Магазины
Склад
B1
(b1=40)
v1=1
B2
(b2=50)
v2=2
B3
(b3=15)
v3=1,6
B4
(b4=75)
v4=1,5
B5
(b5=40)
v5=2,5
B6
(b6=5)
v6=0
<rect id="_x0000_s1211" o:allowincell=«f»>    продолжение
--PAGE_BREAK--