Реферат: Решение транспортных задач

--PAGE_BREAK--В оставшейся части матрицы С минимальная стоимость <shape id="_x0000_i1089" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image116.wmz» o:><img width=«141» height=«29» src=«dopb197510.zip» v:shapes="_x0000_i1089">. Запишем в клетку таблицы (3,2) перевозку <shape id="_x0000_i1090" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image118.wmz» o:><img width=«313» height=«25» src=«dopb197511.zip» v:shapes="_x0000_i1090"> Исключаем из рассмотрения второго потребителя, а из матрицы С второй столбец. Вычисляем <shape id="_x0000_i1091" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image120.wmz» o:><img width=«239» height=«33» src=«dopb197512.zip» v:shapes="_x0000_i1091">
В оставшейся части матрицы С наименьшая стоимость <shape id="_x0000_i1092" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image122.wmz» o:><img width=«147» height=«29» src=«dopb197513.zip» v:shapes="_x0000_i1092"> Запишем в клетку таблицы (3,3) перевозку <shape id="_x0000_i1093" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image124.wmz» o:><img width=«289» height=«33» src=«dopb197514.zip» v:shapes="_x0000_i1093">Исключаем из рассмотрения третьего поставщика, а из матрицы С третью строку. Определяем <shape id="_x0000_i1094" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image126.wmz» o:><img width=«221» height=«33» src=«dopb197515.zip» v:shapes="_x0000_i1094">.
В матрице С остался единственный элемент <shape id="_x0000_i1095" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image128.wmz» o:><img width=«61» height=«25» src=«dopb197516.zip» v:shapes="_x0000_i1095">. Записываем в клетку таблицы (2,3) перевозку <shape id="_x0000_i1096" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image130.wmz» o:><img width=«71» height=«25» src=«dopb197517.zip» v:shapes="_x0000_i1096">.
Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно N=m+n-1=3+4-1=6. Применяя метод вычеркивания, проверяем линейную независимость векторов условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице Х:
<img width=«2» height=«62» src=«dopb197518.zip» v:shapes="_x0000_s1028"><img width=«2» height=«62» src=«dopb197519.zip» v:shapes="_x0000_s1029"><shape id="_x0000_i1097" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image134.wmz» o:><img width=«169» height=«84» src=«dopb197520.zip» v:shapes="_x0000_i1097">
 1 2 5 6
Решение является «вычеркиваемым» и, следовательно, опорным.
Переход от опорного решения к другому. В транспортной задаче переход от оного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок(осуществляется сдвиг по циклу). Перевозка «загружается» в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.
Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Такой цикл называется означенным.
<imagedata src=«41190.files/image136.png» o: croptop=«2181f» cropbottom=«47422f» cropleft=«1894f» cropright=«43798f»><img width=«251» height=«142» src=«dopb197521.zip» v:shapes="_x0000_i1098">
Сдвигом по циклу на величину <shape id="_x0000_i1099" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image138.wmz» o:><img width=«16» height=«20» src=«dopb197522.zip» v:shapes="_x0000_i1099"> называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», и уменьшение объемов перевозок на ту же величину <shape id="_x0000_i1100" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image138.wmz» o:><img width=«16» height=«20» src=«dopb197522.zip» v:shapes="_x0000_i1100"> во всех не четных клетках, отмеченных знаком «-».
1.2.3  МЕТОД ПОТЕНЦИАЛОВ
Широко распространенным методом решения транспортных задач является метод потенциалов.
Если допустимое решение <shape id="_x0000_i1101" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image140.wmz» o:><img width=«76» height=«29» src=«dopb197495.zip» v:shapes="_x0000_i1101">, i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков <shape id="_x0000_i1102" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image141.wmz» o:><img width=«27» height=«25» src=«dopb197523.zip» v:shapes="_x0000_i1102"> i=1,2,…,m и потребителей <shape id="_x0000_i1103" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image143.wmz» o:><img width=«31» height=«29» src=«dopb197524.zip» v:shapes="_x0000_i1103"> j=1,2,…,n, удовлетворяющее следующим образом:
<shape id="_x0000_i1104" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image145.wmz» o:><img width=«277» height=«63» src=«dopb197525.zip» v:shapes="_x0000_i1104">
Группа равенств (2.1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных <shape id="_x0000_i1105" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image141.wmz» o:><img width=«27» height=«25» src=«dopb197523.zip» v:shapes="_x0000_i1105"> i=1,2,…,m и <shape id="_x0000_i1106" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image143.wmz» o:><img width=«31» height=«29» src=«dopb197524.zip» v:shapes="_x0000_i1106"> j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.
Группа неравенств (2.2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:
<shape id="_x0000_i1107" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image147.wmz» o:><img width=«273» height=«29» src=«dopb197526.zip» v:shapes="_x0000_i1107"> (2.3)
Числа <shape id="_x0000_i1108" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image149.wmz» o:><img width=«28» height=«29» src=«dopb197527.zip» v:shapes="_x0000_i1108"> называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.
Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.
Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k) таблицы, соответствующую <shape id="_x0000_i1109" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image151.wmz» o:><img width=«121» height=«29» src=«dopb197528.zip» v:shapes="_x0000_i1109">. Если <shape id="_x0000_i1110" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image153.wmz» o:><img width=«55» height=«25» src=«dopb197529.zip» v:shapes="_x0000_i1110">, то решение оптимальное. Если же <shape id="_x0000_i1111" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image155.wmz» o:><img width=«63» height=«25» src=«dopb197530.zip» v:shapes="_x0000_i1111">, то для соответствующей клетки (l,k) строят цикл и улучшаю решение, перераспределяют груз
<shape id="_x0000_i1112" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image138.wmz» o:><img width=«16» height=«20» src=«dopb197522.zip» v:shapes="_x0000_i1112"><shape id="_x0000_i1113" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image157.wmz» o:><img width=«85» height=«43» src=«dopb197531.zip» v:shapes="_x0000_i1113"> по этому циклу.
Алгоритм решения транспортных задач методом потенциалов:
1.                Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.
2.                Построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания).
3.                Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений:
<shape id="_x0000_i1114" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image159.wmz» o:><img width=«205» height=«29» src=«dopb197532.zip» v:shapes="_x0000_i1114">
которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам:
<shape id="_x0000_i1115" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image161.wmz» o:><img width=«215» height=«29» src=«dopb197533.zip» v:shapes="_x0000_i1115">
если известен потенциал <shape id="_x0000_i1116" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image163.wmz» o:><img width=«23» height=«29» src=«dopb197534.zip» v:shapes="_x0000_i1116">, и
<shape id="_x0000_i1117" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image165.wmz» o:><img width=«209» height=«29» src=«dopb197535.zip» v:shapes="_x0000_i1117">
если известен потенциал <shape id="_x0000_i1118" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image167.wmz» o:><img width=«31» height=«25» src=«dopb197536.zip» v:shapes="_x0000_i1118">
4.                Проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам
<shape id="_x0000_i1119" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image169.wmz» o:><img width=«148» height=«29» src=«dopb197537.zip» v:shapes="_x0000_i1119">
и те из них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток <shape id="_x0000_i1120" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image171.wmz» o:><img width=«59» height=«29» src=«dopb197538.zip» v:shapes="_x0000_i1120">, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.
5. Перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка
<shape id="_x0000_i1121" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image173.wmz» o:><img width=«124» height=«29» src=«dopb197539.zip» v:shapes="_x0000_i1121">
Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину <shape id="_x0000_i1122" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image138.wmz» o:><img width=«16» height=«20» src=«dopb197522.zip» v:shapes="_x0000_i1122"><shape id="_x0000_i1123" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image157.wmz» o:><img width=«85» height=«43» src=«dopb197531.zip» v:shapes="_x0000_i1123">. Клетка со знаком «-», в которой достигается <shape id="_x0000_i1124" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image175.wmz» o:><img width=«71» height=«43» src=«dopb197540.zip» v:shapes="_x0000_i1124"> остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным <shape id="_x0000_i1125" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image177.wmz» o:><img width=«72» height=«20» src=«dopb197541.zip» v:shapes="_x0000_i1125">.
Далее перейти к пункту 3 данного алгоритма.
1.2.4  МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используется запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули <shape id="_x0000_i1126" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image179.wmz» o:><img width=«39» height=«33» src=«dopb197542.zip» v:shapes="_x0000_i1126">, остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
Пример 3:
Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6
Таблица 6
                <shape id="_x0000_i1127" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image181.wmz» o:><img width=«27» height=«29» src=«dopb197543.zip» v:shapes="_x0000_i1127"> <shape id="_x0000_i1128" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image183.wmz» o:><img width=«23» height=«25» src=«dopb197544.zip» v:shapes="_x0000_i1128">
В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
А2
20
А3
30
А4
40
А5
50
Решение:
Распределяем запасы первого поставщика. Так как его запасы <shape id="_x0000_i1129" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image185.wmz» o:><img width=«59» height=«25» src=«dopb197545.zip» v:shapes="_x0000_i1129"> меньше запросов первого потребителя <shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image187.wmz» o:><img width=«59» height=«25» src=«dopb197546.zip» v:shapes="_x0000_i1130">, то в клетку (1,1) записываем перевозку <shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image189.wmz» o:><img width=«68» height=«25» src=«dopb197547.zip» v:shapes="_x0000_i1131"> и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя <shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image191.wmz» o:><img width=«132» height=«33» src=«dopb197548.zip» v:shapes="_x0000_i1132">.
Распределяем запасы второго поставщика. Так как его запасы <shape id="_x0000_i1133" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image193.wmz» o:><img width=«65» height=«25» src=«dopb197549.zip» v:shapes="_x0000_i1133">, меньше запросов первого потребителя <shape id="_x0000_i1134" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image195.wmz» o:><img width=«60» height=«25» src=«dopb197550.zip» v:shapes="_x0000_i1134">, то записываем в клетку (2,1) перевозку <shape id="_x0000_i1135" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image197.wmz» o:><img width=«13» height=«25» src=«dopb197551.zip» v:shapes="_x0000_i1135"><shape id="_x0000_i1136" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image199.wmz» o:><img width=«72» height=«25» src=«dopb197552.zip» v:shapes="_x0000_i1136"> и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя <shape id="_x0000_i1137" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image201.wmz» o:><img width=«135» height=«33» src=«dopb197553.zip» v:shapes="_x0000_i1137">.
Распределяем запасы третьего поставщика <shape id="_x0000_i1138" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image203.wmz» o:><img width=«63» height=«25» src=«dopb197554.zip» v:shapes="_x0000_i1138">. Так как его запасы больше запросов первого потребителя <shape id="_x0000_i1139" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image205.wmz» o:><img width=«60» height=«25» src=«dopb197555.zip» v:shapes="_x0000_i1139">, то записываем в клетку (3,1) перевозку <shape id="_x0000_i1140" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image207.wmz» o:><img width=«72» height=«25» src=«dopb197556.zip» v:shapes="_x0000_i1140"> и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика <shape id="_x0000_i1141" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image209.wmz» o:><img width=«137» height=«33» src=«dopb197557.zip» v:shapes="_x0000_i1141">.
Распределяем запасы третьего поставщика <shape id="_x0000_i1142" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image211.wmz» o:><img width=«61» height=«25» src=«dopb197558.zip» v:shapes="_x0000_i1142">. Так как его запасы меньше запросов второго потребителя <shape id="_x0000_i1143" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image213.wmz» o:><img width=«63» height=«25» src=«dopb197559.zip» v:shapes="_x0000_i1143">, то в клетку (3,2) записываем перевозку <shape id="_x0000_i1144" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image215.wmz» o:><img width=«71» height=«25» src=«dopb197560.zip» v:shapes="_x0000_i1144"> и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя <shape id="_x0000_i1145" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image217.wmz» o:><img width=«136» height=«33» src=«dopb197561.zip» v:shapes="_x0000_i1145">.
Распределяем запасы четвертого поставщика <shape id="_x0000_i1146" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image219.wmz» o:><img width=«65» height=«25» src=«dopb197562.zip» v:shapes="_x0000_i1146">. Так как его запасы больше запросов второго потребителя <shape id="_x0000_i1147" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image221.wmz» o:><img width=«63» height=«25» src=«dopb197563.zip» v:shapes="_x0000_i1147">, то записываем в клетку (4,2) перевозку <shape id="_x0000_i1148" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image223.wmz» o:><img width=«73» height=«25» src=«dopb197564.zip» v:shapes="_x0000_i1148"> и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика <shape id="_x0000_i1149" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image225.wmz» o:><img width=«137» height=«33» src=«dopb197565.zip» v:shapes="_x0000_i1149">.
Распределяем запасы четвертого поставщика <shape id="_x0000_i1150" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image227.wmz» o:><img width=«63» height=«25» src=«dopb197566.zip» v:shapes="_x0000_i1150">. Так как его запасы меньше запросов третьего потребителя <shape id="_x0000_i1151" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image229.wmz» o:><img width=«61» height=«25» src=«dopb197567.zip» v:shapes="_x0000_i1151">, то в клетку (4,3) записываем перевозку <shape id="_x0000_i1152" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image231.wmz» o:><img width=«71» height=«25» src=«dopb197568.zip» v:shapes="_x0000_i1152"> и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя <shape id="_x0000_i1153" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image233.wmz» o:><img width=«135» height=«33» src=«dopb197569.zip» v:shapes="_x0000_i1153">.
Распределяем запасы пятого поставщика. Так как его запасы <shape id="_x0000_i1154" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image235.wmz» o:><img width=«63» height=«25» src=«dopb197570.zip» v:shapes="_x0000_i1154"> больше запросов третьего потребителя <shape id="_x0000_i1155" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image237.wmz» o:><img width=«63» height=«25» src=«dopb197571.zip» v:shapes="_x0000_i1155">, то в клетку (5,3) записываем перевозку <shape id="_x0000_i1156" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image239.wmz» o:><img width=«72» height=«25» src=«dopb197572.zip» v:shapes="_x0000_i1156"> и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика<shape id="_x0000_i1157" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image241.wmz» o:><img width=«137» height=«33» src=«dopb197573.zip» v:shapes="_x0000_i1157">.
Распределяем запасы пятого поставщика. Так как его запасы <shape id="_x0000_i1158" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image243.wmz» o:><img width=«63» height=«25» src=«dopb197574.zip» v:shapes="_x0000_i1158"> больше запросов четвертого потребителя <shape id="_x0000_i1159" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image245.wmz» o:><img width=«63» height=«25» src=«dopb197575.zip» v:shapes="_x0000_i1159">, то в клетку (5,4) записываем перевозку <shape id="_x0000_i1160" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image247.wmz» o:><img width=«73» height=«25» src=«dopb197576.zip» v:shapes="_x0000_i1160"> и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика<shape id="_x0000_i1161" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image249.wmz» o:><img width=«136» height=«33» src=«dopb197577.zip» v:shapes="_x0000_i1161">.
Распределяем запасы пятого поставщика. Так как его запасы <shape id="_x0000_i1162" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image251.wmz» o:><img width=«61» height=«25» src=«dopb197578.zip» v:shapes="_x0000_i1162"> равны запросам пятого потребителя <shape id="_x0000_i1163" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image253.wmz» o:><img width=«60» height=«25» src=«dopb197579.zip» v:shapes="_x0000_i1163">, то в клетку (5,5) записываем перевозку <shape id="_x0000_i1164" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image255.wmz» o:><img width=«71» height=«25» src=«dopb197580.zip» v:shapes="_x0000_i1164"> и исключаем из рассмотрения пятого поставщика и пятого потребителя.
Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.
Результаты построения опорного решения приведены в таблице 7.
                <shape id="_x0000_i1165" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image181.wmz» o:><img width=«27» height=«29» src=«dopb197543.zip» v:shapes="_x0000_i1165"> <shape id="_x0000_i1166" type="#_x0000_t75" o:ole=""><imagedata src=«41190.files/image183.wmz» o:><img width=«23» height=«25» src=«dopb197544.zip» v:shapes="_x0000_i1166">
В1
50
В2
40
В3
30
В4
20
В5
10
А1
10
10
—
—
—
—
А2
20
20
—
—
—
—
А3
30
20
10
—
—
—
А4
40
—
30
10
—
—
А5
50
—
—
20
20
10

1.3 БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)
<shapetype id="_x0000_t177" coordsize=«21600,21600» o:spt=«177» path=«m,l21600,r,17255l10800,21600,,17255xe»><path gradientshapeok=«t» o:connecttype=«rect» textboxrect=«0,0,21600,17255»><shapetype id="_x0000_t111" coordsize=«21600,21600» o:spt=«111» path=«m4321,l21600,,17204,21600,,21600xe»><path gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«12961,0;10800,0;2161,10800;8602,21600;10800,21600;19402,10800» textboxrect=«4321,0,17204,21600»><shapetype id="_x0000_t110" coordsize=«21600,21600» o:spt=«110» path=«m10800,l,10800,10800,21600,21600,10800xe»><path gradientshapeok=«t» o:connecttype=«rect» textboxrect=«5400,5400,16200,16200»><img width=«479» height=«917» src=«dopb197581.zip» v:shapes="_x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066">  

          нет нет
 
                                              да

<shapetype id="_x0000_t112" coordsize=«21600,21600» o:spt=«112» path=«m,l,21600r21600,l21600,xem2610,nfl2610,21600em18990,nfl18990,21600e»><path o:extrusionok=«f» gradientshapeok=«t» o:connecttype=«rect» textboxrect=«2610,0,18990,21600»><shapetype id="_x0000_t85" coordsize=«21600,21600» o:spt=«85» adj=«1800» path=«m21600,qx0@0l0@1qy21600,21600e» filled=«f»><path arrowok=«t» gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«21600,0;0,10800;21600,21600» textboxrect=«6326,@2,21600,@3»><img width=«509» height=«709» src=«dopb197582.zip» v:shapes="_x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095 _x0000_s1096 _x0000_s1097 _x0000_s1098"> 

                                                                                         Метод
                                                                                         северо-
                                                                                         — западного
                                                                                         угла
                                                                                         метод
                                                                                         потенциалов

2. ФОРМЫ ВХОДНОЙ ИНФОРМАЦИИ
Входные данные вводятся с клавиатуры
·                      Запасы i-го поставщика
·                      запросы j-го потребителя
В данном примере
·                         запасы поставщиков(10; 20; 30; 40; 50)
·                         запросы потребителей(50; 40; 30; 20; 10)
    продолжение
--PAGE_BREAK--