85722 (574897), страница 2
Текст из файла (страница 2)
f1 = 175 * 5 + 175 * 15 + 40 * 10 + 160 * 6 + 200 * 4 + 10 * 20 + 240 * 10 = 8260.
Проверим найденное решение транспортной задачи на оптимальность Найденное исходное решение проверяется на оптимальность методом потенциалов по следующему критерию: если решение транспортной задачи является оптимальным, то ему соответствует система m+n ( 5 + 3 = 8 ) действительных чисел ![]()
и ![]()
, удовлетворяющих условиям ![]()
для занятых клеток и ![]()
– для свободных клеток.
– для свободных клеток. Числа ![]()
и ![]()
называются потенциалами. В распределительную таблицу добавляют столбец ![]()
и строку ![]()
.
и 
и строку Потенциалы 
и 
находят из равенства 
, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например 
, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал , то 
; если известен потенциал , то 
.
Обозначим 
. Эту оценку называют оценкой свободных клеток. Если 
, то опорное решение является оптимальным. Если хотя бы одна из оценок 
, то решение не является оптимальным и его можно улучшить, перейдя от одного решения к другому.
Проверим найденное решение на оптимальность, добавив в распределительную таблицу, приведенную ниже, столбец 
и строку 
.
Полагая , запишем это значение в последнем столбце
таблицы.
| ai | 1 | 2 | 3 | 4 | 5 | ||
| 175 | 225 | 240 | 160 | 200 | i | ||
|
1 | 350 | 5 175 | 15 175 | 18 | 16 | 8 | 0 |
|
2 |
400 | 6 | 10 40 | 15 | 6 160 | 4 200 | -5 |
| 3 |
250 | 25 | 20 10 | 10 240 | 15 | 18 | 0 |
| i | 5 | 15 | 10 | 11 | 9 | ||
biДля клетки (1,1) :
1 +
1 = 5,
1 = 0,
1 = 5
Для клетки (1,2) :
1 +
2 = 15,
1 = 0,
2 = 15
Для клетки (2,2) :
2 +
2 = 10,
2 = -5,
2 = 15
Для клетки (2,4) :
2 +
= 6,
2 = -5,
4 = 11
Для клетки (2,5) :
2 +
= 4,
2 = -5,
5 = 9
Для клетки (3,3) :
+
= 10,
3 = 0,
3 = 10
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Δ13 =
1 +
3 – с 13 = 0 + 10 – 18 = - 8
0
Δ14 =
1 +
– с 14 = 0 + 11 – 16 = - 5
0
Δ15 =
1 +
– с 15 = 0 + 9 – 8 = 1
0
Δ21 =
+
– с 21 = -5 + 5 – 6 = -6
0
Δ23 =
+
– с 23 = -5 + 10 – 15 = -10
0
Δ31 =
+
– с 31 = 0 + 5 – 25 = -20
0
Δ34 =
+
– с 34 = 0 + 11 – 15 = -4
0
Δ35 =
+
– с 35 = 0 + 9 – 18 = -9
0
Получили одну оценку Δ15 = 1
0 следовательно, исходное решение не является оптимальным и его можно улучшить.
Переход от одного решения транспортной задачи к другому.
Наличие положительной оценки свободной клетки ( ) при проверке решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток – свободной.
Для свободной клетки Δ15 = 1
0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое решение. Это решение проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное решение.
Х2 =
Стоимость перевозки при исходном решении составляет
f2 = 175 * 5 + 215 * 10 + 10 * 20 + 240 * 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.
Проверим полученное решение на оптимальность. Для этого запишем его в распределительную таблицу, приведенную ниже, найдем потенциалы занятых и оценки свободных клеток.
| ai | 1 | 2 | 3 | 4 | 5 | ||
| 175 | 225 | 240 | 160 | 200 | i | ||
| 1 | 350 | 5 175 | 15 | 18 | 16 | 8 175 | 0 |
| 2 | 400 | 6 | 10 215 | 15 | 6 160 | 4 25 | -4 |
| 3 | 250 | 25 | 20 10 | 10 240 | 15 | 18 | 0 |
| i | 5 | 14 | 10 | 10 | 8 | ||
Для клетки (1,1) :
1 +
1 = 5,
1 = 0,
1 = 5
Для клетки (1,5) :
1 +
5 = 8,
1 = 0,
5 = 8
Для клетки (2,5) :
2 +
= 4,
= -4,
= 8
Для клетки (2,4) :
2 +
= 6,
2 = -4,
4 = 10
Для клетки (2,2) :
2 +
= 10,
2 = -4,
= 14
Для клетки (3,3) :
+
= 10,
3 = 0,
3 = 10
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Δ12 =
1 +
– с 12 = 0 + 14 – 15 = - 1
0
Δ13 =
1 +
– с 13 = 0 + 10 – 18 = - 8
0
Δ14 =
1 +
– с 14 = 0 + 10 – 16 = - 6
0
Δ21 =
+
– с 21 = -4 + 5 – 6 = - 5
0
Δ23 =
+
– с 23 = - 4 + 10 – 15 = - 9
0
Δ31 =
+
– с 31 = 0 + 5 – 25 = - 20
0
Δ34 =
+
– с 34 = 0 + 10 – 15 = - 5
0
Δ35 =
+
– с 35 = 0 + 8 – 18 = - 10
0
Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак,
Х орт =
Стоимость транспортных расходов равна
F min = 175 * 5 + 215 * 10 + 10 * 20 + 240 * 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.
По сравнению с исходным решением, транспортные расходы уменьшились на 175 усл.ед. (8260 – 8085 = 175).
Задачи 41–50. Составить экономико-математическую модель. Найти решение задачи линейного программирования при помощи средств Excel на ПК.
48. В суточном рационе кормления крупного рогатого скота должно быть не менее 20 кормовых единиц, не менее 2000 г белков и не менее 100 г кальция. Для кормления используют сено, силос, корнеплоды и концентраты. Содержание питательных веществ в 1 кг каждого вида корма, а также его себестоимость представлены в таблице. Составить кормовой рацион минимальной стоимости.
| Содержание питательных веществ в 1 кг корма | Корм | |||
| Сено | Силос | Корнеплоды | Концентрат | |
| Кормовая единица | 0,5 | 0,2 | 6 | 0,8 |
| Белки, г | 40 | 10 | 12 | 200 |
| Кальций, г | 5 | 4 | 3 | 1 |
Себестоимость 1 кг корма, ден. ед. | 2 | 1 | 2 | 4 |
Решение
Обозначим через
-
х1 – количество сена,
-
х2 - количество силоса,
-
х3 - количество корнеплодов,
-
х4 - количество концентрата.
Ограничения можно выразить соотношением:
ограничения по кормовой единице-
0,5 * х1 + 0,2 * х2 + 6 * х3 + 0,8 х4 ≥ 20. (1)
ограничения по белкам –
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
