Метод оптимальных решений

 

 

В левой колонке и верхней  строке таблицы записаны соответственно номера поставщиков и потребителей. В правой колонке и нижней строке записаны, соответственно, предложения  каждого поставщика и спрос каждого  потребителя. В правом верхнем углу клетки, стоящей на пересечении i -й строки и j -го столбца, стоит тариф С_ij на перевозку от i -го поставщика j -му потребителю ( ; ).

Решение транспортной задачи записывают в клетки транспортной таблицы: на пересечении i-й строки j-го столбца записыва-ря значение х_ij.

Решение транспортной задачи, как и решение ОЗЛП, состоит  двух этапов:

1 этап. Нахождение начального  плана перевозок (х_ij),  ; , удовлетворяющего ограничениям (4.9) — (4.12);

2 этап. Улучшение начального  плана перевозок и получение  оптимального плана перевозок  (х_ij),  ; ;,доставляющего минимум функции (4.8).

Заметим, что общее число  неизвестных в транспортной задаче равно n*n. Уравнения (4.9), (4.10) не являются линейно-независимыми, так как их правые части связаны условием (4.11). Число линейно-независимых уравнений в ограничениях транспортной задачи равно, следовательно, не т+п, ат+п -1. Таким образом, число неизвестных больше числа связывающих их уравнений так же, как и в основной задаче линейного программирования.

Систему уравнений (4.9), (4.10) можно разрешить относительно т+п -1 базисных переменных. Остальные тп-(т+п-1) переменных являются свободными. Каждое решение транспортной задачи находят следующим образом: свободные тп-(т+п-1) переменные полагаются равными нулю, а базисные т+п-1 переменные находят из системы ограничений (4.9) – (4.10). Полученное решение проверяют на оптимальность. Если решение неоптимально, то осуществляют переход к новому решению путем изменения списка базисных переменных. Эти действия повторяют до тех пор, пока не будет получено оптимальное решение, доставляющее минимум целевой функции (4.8).

Контрольные вопросы

1. В чем заключается  особенность?

2. Можно ли решить транспортную  задачу симплекс методом?

3. Что такое сбалансированная  ТЗ?

4. Что такое не сбалансированная  ТЗ? 

 

4.3. Определение  начального плана транспортировок.  Методы "северо-западного" угла, минимального элемента,  Фогеля

Рассмотрим три метода нахождения начального решения транспортной задачи: метод "северо-западного" угла, метод минимального элемента и метод Фогеля.

Метод "северо-западного" угла

Шаг 1. Составляют транспортную таблицу.

Шаг 2. Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос:  Если а₁ < b₂, то х₁₁ = a₁ и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х₂₁ = 
= min(a₂,b₁-a₁). Если b₁-a₁ <a₂ то х₂₁ = b₁-a₁. Спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечении второй строки и второго столбца, переходят к заполнению следующей третьей клетки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем n-м столбце и последней m-й строке.

Пример 4.2

Определить начальное  решение по методу "северо-западного" угла для транспортной задачи из примера 4.1.

Решение.

Транспортная таблица  имеет следующий вид (табл. 4.2):

Таблица 4.2

№	1	2	3	4	Предложение
1	120           7	40        8	1	2	160
2	4	10         5	130     9	8	140
3	9	2	60        3	110    6	170
Спрос	120	50	190	110

 

 

В первую клетку помещают: х₁₁ = min( 160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 – 120=40 усл. ед. Двигаемся по первой строке вправо х₂₁ =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х₂₂ = min(140,50 – 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х₂₃ = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x₃₃ = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х₃₄ = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений x_ij,  , равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.

Начальный план перевозок  имеет вид

Стоимость перевозок по этому  плану составляет

S₁= 120*7+40*8+10*5+130*9+60*3+110*6=3220.

Метод "северо-западного" угла — наиболее простой метод  нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.

Метод минимального элемента

Шаг 1. Составляют транспортную таблицу.

Шаг 2. Выбирают клетку таблицы, которой соответствует минимальное значение тарифа, и переходят на шаг 3.

Шаг 3. В выбранную клетку аналогично методу "северо-западного" угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку; если спрос удовлетворен, вычеркивают соответствующий столбец.

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

Пример 4.3

Определить начальное  решение по методу минимального элемента для транспортной задачи из примера 4.1. Решение записано в табл. 4.3.

Таблица 4.3

№	1	2	3	4	Предложение
1	7	8	160        1	2	160
2	120          4	5	9	20         8	140
3	9	50          2	30     3	90       6	170
Спрос	120	50	190	110

 

 

Минимальный тариф с₁₃ = 1, x₁₃ = min(160,190) = 160. Первую строку вычеркивают. Минимальный тариф для оставшихся клеток c₃₂ = 2, x₃₂ =min(170,50) = 50. Второй столбец вычеркивают.

Для оставшихся клеток минимальный  тариф:

с₃₃ = 3 , х₃₃ = min(170 – 50,190 -160) = 30. Третий столбец вычеркивают.

Для оставшихся клеток минимальный  тариф:

c₂₁ ⁼ 4, х₂₁ = min(140,120) = 120. Первый столбец вычеркивают.

Для оставшихся клеток минимальный  тариф:

с₃₄ = 6, х₃₄ = min(170 – 50 – 30,110) = 90. Для одной оставшейся клетки

х₂₄ = min(140 -120,110 – 90) = 20.

План перевозок, полученный по методу минимального элемента, имеет  вид

Стоимость перевозок по этому  плану составляет

S₁ =160*1+120*4+20*8+50*2+30*З+90*6=1530.

Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу "северо-западного" угла.

Метод Фогеля

Шаг 1. Составляют транспортную таблицу. 

Шаг 3. Для каждой строки и каждого столбца транспортной

таблицы определяют разность между наименьшим тарифом и ближайшим  к нему значением. Переход к шагу 3.

Шаг 3. В строке или в столбце, которым соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. Переход к шагу 4.

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

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

В методе Фогеля используются штрафы, взимаемые за неудачей выбор  маршрута. Рассчитанные на шаге 2 разности между двумя уровнями затрат на перевозку  являются штрафами за неверно выбранный  маршрут перевозки.

Пример 4.4

Определим начальное решение  по методу Фогеля для транспортной задачи из примера 4.1 (табл.4.4). 

 

Решение.

Разности по строкам будем  записывать в правой части табл. 4.4, разности по столбцам — внизу  табл.4.4. Максимальную разность будем  отмечать кружком. Наименьший тариф  в первой строке равен 1. Ближайший  к нему равен 3. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее  к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1.

Таблица 4.4 

 

№	1	2	3	4	Предложение	Разность по столбцам
1	1	8	1 50	2 120	160	1	5	-	-
2	1 120	5 20	9	8	140	1	1	1	1
3	9	2 30	3 140	6	170	1	1	1	7
Спрос	120	50	190	110
Разность по строкам	3	3	3	4
	3	3	3	-
	5	3	6	-
	5	3	-	-

 

 

В первом столбце наименьший тариф c₂₁= 4. Ближайшее значение с₁₁ = 7, с₁₁ – c₂₁ = 7 – 4 = 3. Во втором столбце наименьшее значение c₃₂ = 3. Ближайшее значение с₂₂ = 5, с₂₂ – c₃₂ = 5 – 2 = 3.

Третий столбец: с₁₃ = 1, с₃₃ = 3 , с₃₃ – с₁₃ = 3 -1 = 3.

Четвертый столбец: с₁₄= 2 , с₃₄ = 6 , с₃₄ – с₁₄ = 6 – 2 = 4 .

Максимальная из всех разностей 4 находится в четвертом столбце.  
В этом столбце клетка с наименьшим тарифом с₁₄ = 2 находится в первой строке. В эту клетку помещаем максимально возможное значение: х₁₄ =min(110,160) = 110. Четвертый потребитель полностью удовлетворил свой спрос, и четвертый столбец вычеркиваем.

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

Первая строка: минимальный  тариф с₁₃ = 1. Ближайшее значение  
с₁₁ =7, с₁₁ – с₁₃ =7-1 = 6.

Вторая строка: минимальный  тариф c₂₁= 4. Ближайшее значение  
с₂₂ = 5. с₂₂-с₂₁ = 5 – 4 = 1.

Третья строка: с₃₂ = 2, с₃₃ = 3 , с₃₃ – с₃₂ = 3 – 2 = 1.

Первый столбец: минимальный  тариф c₂₁ = 4. Ближайшее значение с₁₁ =7,

с₁₁ – c₂₁ =7-4 = 3 .

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂ = 5 – 2 = 3.

Третий столбец: с₁₃ = 1. с₃₃ ⁼ 3, с₃₃ — с₁₃ =3 -1 = 3.

Максимальная разность равна 6 и стоит в первой строке. Минимальный  тариф в первой строке с₁₃ = 1. В эту клетку помещаем х₁₃ = min(160 -110,190) = 50.  

Вычеркиваем первую строку.

Повторяем все действия без  учета первой строки и четвертого столбца.

Вторая строка: с₂₁ = 4 , с₂₂ = 5, с₂₂ – c₂₁ = 5 – 4 = 1.

Третья строка: с₃₂ = 2 , с₃₃ = 3 , с₃₃ – с₃₂ = 3 – 2 = 1.

Первый столбец: c₂₁ = 4 , с₃₁ = 9, с₃₁ – c₂₁ = 9 – 4 = 5.

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂= 5 – 2 = 3.

Третий столбец: с₃₃ = 3 , с₂₃ = 9 , с₂₃ – с₃₃ = 9 – 3 = 6.

Максимальная разность равна 6 и стоит в третьем столбце. Минимальный из оставшихся тарифов  в этом столбце с₃₃ = 3, х₃₃ = 
= min(170, 90 – 50) = 140. Спрос третьего потребителя удовлетворен, третий столбец вычеркиваем.

Вновь составляем разности для невычеркнутых строк и  столбцов.

Вторая строка: с₂₁ = 4 , с₂₂ = 5, с₂₂ – с₂₁=5 – 4 = 1.