|
|
Построенному опорному решению отвечают затраты:
Z1 = 90*2+220*1+100*8+90*6+170*10+140*1+90*2 =3760
Проверим полученный план на оптимальность. Для этого i-ой строке и j –му столбцу ставим в соответствие числа Ui и Vj (потенциалы). Для каждой базисной переменной Xij потенциалы должны удовлетворять условию Ui+Vj=Cij. Получаем систему:
U1+V3=2
U1+V5=1
U2+V2=8
U2+V3=6
U2+V4=10
U3+V1=1
U3+V2=2
Так как система состоит из 7 уравнений, а неизвестных 8, то, чтобы найти численное решение этой системы, одно из неизвестных зададим произвольно, тогда остальные переменные найдутся из системы однозначно.
Пусть U2=0, тогда V2=8
V3=6
V4=10
U1=2-V3=2-6 = - 4
U3=2-V2=2-8 = - 6
V1=1-U3= 1-(- 6)=7
V5=1-U1= 1-(- 4)=5
Теперь для небазисных переменных (свободных) рассмотрим оценки:
Sij=Cij-(Ui+Vj)
S11=5- (- 4+7) = 2
S12=3-(- 4+8) = - 1
S14=4-(- 4+10) = -2
S21=3-(0 +7) = - 4
S25=5-(0+5) = 0
S33=3-(- 6+6) = 3
S34=5-(- 6+10) = 1
S35=4-(- 6+5) = 5
В силу критерия оптимальности ( все оценки Sij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введём переменную Х21 (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочерёдно по часовой стрелке знаки "+" и "-", начиная с (2,1), которой присваиваем знак "+". Выбираем наименьшее значение из клеток со знаком "-" (min ( 140, 100 ) = 100 ) и перераспределяем продукцию вдоль контура, прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значения в клетках со знаком "-". В результате приходим к таблице5.2.
Таблица 5.2 - Построение опорного плана
Ai
B1
B2
B3
B4
B5
Ui
A1
5
3
90 2
4
220 1
-4
A2
*100 + 3
8
90 6
170 - 10
5
0
A3
40 - 1
190 2
3
* + 5
4
-2
Vj
3
4
6
10
5
Полученному решению отвечают затраты:
Z2 = 90*2 + 220*1 +100*3 + 90*6 +170*10 + 40*1+190*2 = 3360
Проверяем полученный план на оптимальность и получаем, что S34 = - 3 < 0, значит решение не оптимальное и строим в таблице 2 новый цикл пересчёта для клетки (3,4). Так как min (220,90,40) = 40 = Xij, то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком "-". В результате получаем таблицу5.3.
Таблица 5.3 - Нахождение оптимального плана
Ai
B1
B2
B3
B4
B5
Ui
A1
5
3
2
+ 90 4
220 - 1
- 6
A2
140 3
8
180 6
- 40 10
* + 5
0
A3
1
190 2
3
40 5
4
- 5
Vj
3
7
6
10
7
Z4= 90*4 + 220*1 + 40*3 + 180*6 + 40*10 + 190*2 + 40*5 = 3060
Среди оценок свободных клеток имеем S25 = - 2 < 0 , следовательно, полученный план перевозок не является оптимальным и для его получения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 5.4.
Таблица 5. 4 - Новый опорный план
Ai
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35
При использовании материалов активная ссылка на источник обязательна.