Сбалансированная транспортная модель
Из представленной модели видно, что суммарный объём производства в исходных пунктах 
не должен быть меньше суммарного спроса в пунктах назначения 
.
Если суммарный объём производства равен суммарному спросу ( = ), то модель называется сбалансированной транспортной моделью. Она отличается от вышеприведённой модели лишь тем, что все ограничения превращаются в равенства, т.е.
В реальных условиях не всегда объём производства равен спросу или превосходит его. Однако транспортную модель всегда можно сбалансировать. Так, например, если спрос превышает объём производства, можно ввести дополнительный фиктивный исходный пункт с производительностью недостающего объёма продукции. Поскольку на самом деле такого исходного пункта не существует, никакие перевозки не осуществляются, и соответствующая стоимость перевозки единицы продукции равна нулю.
Сбалансированную траспортную задачу удобно задавать в виде таблицы:
| Пункты отправления | Пункты назначения | 
| ||||
 
| 
| 
| … | 
| ||
|
|
|
| … |
| 
|
|
|
|
| … |
| 
|
| … | … | … | … | … | … | |
|
|
|
| … |
| 
|
| 
| 
| 
| … | 
|
  
|
- количество продукции, производимой в пункте 
;
- количество продукции, потребляемой в пункте 
;
- количество продукции, перевозимой из пункта в пункт ;
- стоимость перевозимой единицы продукции из пункта в пункт .
Математическая запись сбалансированной ТЗ:
- условие сбалансированности
Задача 2. В ПО химчистки три цеха 
выполняют заказы, поступающие с трех приёмных пунктов 
. Мощность цехов и пропускная способность приёмных пунктов ( в 
) составляют: пропускная способность приёмного пункта 
; производственная мощность цеха 
. Расстояние от каждого приёмного пункта до каждого цеха в 
. Требуется так организовать перевозку заказов с приёмных пунктов в цехи ПО, чтобы пропускная способность приёмных пунктов, прикреплённых к каждому цеху, в сумме не превышала бы мощности самого цеха; цехи полностью обеспечивали бы химчистку вещей для каждого приёмного пункта, и чтобы при этом общий объём перевозок в тонно-километрах был минимальным.
1. Математическая запись ТЗ:
а) Выбор неизвестных: - объём перевозки груза из 
в 
( 
.
б) Целевая функция 
.
в) Система ограничений: 
= 90
Табличная запись ТЗ:
|
|
|
| |
|
|
|
|
| |
|
|
|
|
| |
|
|
|
| |
|
| 90 
|
2 Решение транспортной задачи:
а) Составление опорного плана (метод наименьшей стоимости).
Из требования = следует, что одно уравнение оказывается зависимым, т.е. транспортная модель содержит только 
независимых уравнений. Таким образом начальное базовое допустимое решение должно иметь базисную переменную. Для получения этого решения используют метод наименьшей стоимости, правило северо-западного угла и другие. По методу наименьшей стоимости сначала берут первый пункт производства продукции 
и в первую очередь удовлетворяют потребность в продукции те пункты назначения, у которых затраты на перевозку единицы продукции 
будут меньшими по сравнению с остальными, затем переходят к 
и т.д.
|
|
|
| |||||||
|
|
|
|
| |||||||
|
|
|
|
| |||||||
|
| ||||||||||
|
| 90
|
Вычислим значение целевой функции при таких допустимых значениях
б) Проверка плана на оптимальность ( метод потенциалов ).
Для проверки опорного плана на оптимальность используют так называемый «метод потенциалов», по которому строке и столбцу транспортной таблицы ставится в соответствие числа 
и 
. Для каждой базисной переменной текущего решения потенциалы и должны удовлетворять уравнению 
. Эти уравнения приводят к системе, состоящей из уравнений, в которых фигурируют 
неизвестных. Значения потенциалов можно определить из этой системы, придавая одному из них произвольное значение ( обычно полагают 
). Как только решение получено, оценки для небазисных переменных 
определяются в соответствии с соотношением 
. Если в результате получатся отрицательные значения, то план считается не оптимальным, и его надо перестроить путем перераспределения продукции.
Таким образом, для проверки опорного плана на оптимальность нужно проверить выполнение следующих двух правил:
1. 
,
2. .
В нашем случае
1. 
2. 
в) Улучшение опорного плана
После этого для включения в базис выбирается небазисная переменная, имеющая самую большую по модулю отрицательную оценку. В нашем случае это переменная , для которой второе условие не выполняется. Для этой переменной строят многоугольник по указанной схеме, вершинам которого приписывают чередующиеся знаки, начиная со знака (+) для вводимой в базис переменной. Затем в вершинах со знаком (-) отыскивают наименьшую продукцию, которую и перемещают по вершинам многоугольника согласно знакам.
- +
+ -
Этот цикл повторяется до тех пор, пока не будет выполняться второе условие для всех небазисных переменных.
Покажем оформление цикла на практике:
Первый цикл Второй цикл
|
|
|
|
| |||||
|
|
 10
| ||||||||
|
|
|
| -1 | ||||||
|
|
|
| |||||||
|
| 90
| ||||||||
|
|
15
13 
|
|
|
|
| |||||
|
|
|
| |||||||
|
| -6 | ||||||||
|
|
 15
|
| -2 | ||||||
|
| 90
| ||||||||
|
|
10
: 1 В1 В2 В3 А1В2: -4 В1 В2 В3
0 А1В3: -5
3 А2В1: 5
-5 А1 А2 А3 А2В2: 3 А1 А2 А3
Третий цикл Четвертый цикл
|
|
|
|
|
| |||||
|
|
|
| |||||||
|
| -1 | ||||||||
|
|
|
| -2 | ||||||
|
| 90
| ||||||||
|
|
3
22|
|
|
|
|
| |
|
| |||||
|
| -1 | ||||
|
| |||||
|
| 90
| ||||
|
|
А1В2: -4 В1 В2 В3 А1В1: 4
А2В1: 0 А2В1: 4
А2В2: -2 А2В2: 2
А3В3: 5 А1 А2 А3 А3В3: 1
