Материал: Оптимизационные задачи в экономике и алгоритмы решения некоторых задач линейного программирования
Поскольку в клетке (A4, B3) псевдостоимость
превышает стоимость, транспортный план не оптимален. Построим цикл пересчета
для этой клетки:
Таблица 19
|
Базы |
Магазины |
Запас |
|||||||
|
|
B1 |
B2 |
B3 |
A4 |
|
||||
|
A1 |
|
7 |
|
3 |
|
4 |
|
2 |
15 |
|
|
|
|
|
|
|
|
15 |
|
|
|
A2 |
|
6 |
|
1 |
|
4 |
|
6 |
31 |
|
|
3+a |
|
|
|
28-a |
|
|
|
|
|
A3 |
|
6 |
|
9 |
|
5 |
|
3 |
25 |
|
|
20 |
|
|
|
|
|
5 |
|
|
|
A4 |
|
10 |
|
4 |
|
7 |
|
9 |
22 |
|
|
5-a |
|
17 |
|
+a |
|
|
|
|
|
Спрос |
28 |
17 |
28 |
20 |
|
||||
Используя данные таблицы 9, найдем цену цикла:
g43 = c43 - c43* = 7 - 8 = - 1.
Определим величину перевозки по новому маршруту:
а=min(28, 5)=5.
Таким образом, клетка (A4, B3) становится базисной,
а клетка (A4, В1) - свободной. Выпишем новый план перевозок:
Таблица 20
|
Базы |
Магазины |
Запас |
|||||||||||||
|
|
B1 |
B2 |
B3 |
A4 |
|
||||||||||
|
A1 |
|
7 |
|
3 |
|
4 |
|
2 |
15 |
||||||
|
|
|
|
|
|
|
|
15 |
|
|
||||||
|
A2 |
|
6 |
|
1 |
|
4 |
|
6 |
31 |
||||||
|
|
8 |
|
|
|
23 |
|
|
|
|
||||||
|
A3 |
|
6 |
|
9 |
|
5 |
|
3 |
25 |
||||||
|
|
20 |
|
|
|
|
|
5 |
|
|
||||||
|
A4 |
|
10 |
|
4 |
|
7 |
|
9 |
22 |
|
5 |
|
|
|
|
|
Спрос |
28 |
17 |
28 |
20 |
|
||||||||||
Вычислим стоимость полученного плана:
¢¢¢= E¢¢
+ a´g43
= 413 - 5=408.
Проверим оптимальность нового опорного плана.
Поскольку наибольшее число базисных клеток (две), например, в первом столбце
таблицы, положим его потенциал равным нулю, последовательно определим
потенциалы остальных строк и столбцов, найдем псевдостоимости клеток:
Таблица 21
|
Потенциалы баз |
Потенциалы магазинов |
Запас |
||||||||
|
|
b1=0 |
b2=-5 |
b3=-2 |
b4=-3 |
|
|||||
|
a1=5 |
5 |
7 |
0 |
3 |
3 |
4 |
|
2 |
15 |
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
a2=6 |
|
6 |
1 |
1 |
|
4 |
3 |
6 |
31 |
|
|
|
8 |
|
|
|
23 |
|
|
|
|
|
|
a3=6 |
|
6 |
1 |
9 |
4 |
5 |
|
3 |
25 |
|
|
|
20 |
|
|
|
|
|
5 |
|
|
|
|
a4=9 |
9 |
10 |
|
4 |
|
7 |
6 |
9 |
22 |
|
|
|
|
|
17 |
|
5 |
|
|
|
|
|
|
Спрос |
28 |
17 |
28 |
20 |
|
|||||
Поскольку во всех свободных клетках
псевдостоимость не превышают стоимости, рассматриваемый план
является оптимальным. Стоимость плана x (минимальные транспортные издержки) равна 408.
Задания для контрольной работы
В контрольную работу по математическому программированию входят две задачи.
Номер выполняемого варианта совпадает с последней цифрой студенческой зачетной книжки. Если эта цифра 0, выполняется 10 вариант.
Задача планирования товарооборота
При продаже товаров А и В используется три вида ресурсов: R1, R2, R3.
Сведения о количестве ресурсов,
необходимых для продаж и единицы каждого товара, обеспеченности торгового
предприятия этими ресурсами и ценах, по которым товары продаются, приведены в
следующей таблице:
|
|
Товары |
|
|
|
Ресурсы |
A |
B |
Запас ресурсов |
|
R1 |
a1 |
b1 |
c1 |
|
R2 |
a2 |
b2 |
c2 |
|
R3 |
a3 |
b3 |
c3 |
|
Цена товара |
p1 |
p2 |
|
Постройте математическую модель задачи
максимизации товарооборота. Полученную задачу математического программирования
решите геометрически, симплекс-методом.
|
Номер варианта |
Технология продажи товаров |
Запас ресурсов |
Цены товаров |
|
|
|
(a1, a2, a3) |
(b1, b2, b3) |
(c1, c2, c3) |
(p1, p2) |
|
1 |
2 4 2 |
1 5 4 |
120 280 200 |
3 4 |
|
2 |
1 6 0 |
2 2 3 |
30 60 42 |
3 4 |
|
3 |
1 4 1 |
2 2 0 |
80 140 30 |
3 2 |
|
4 |
3 5 2 |
2 2 6 |
42 60 84 |
8 7 |
|
5 |
1 2 0 |
2 1 1 |
70 80 30 |
9 6 |
|
6 |
1 3 1 |
2 2 4 |
12 24 20 |
3 4 |
|
7 |
1 5 4 |
6 2 2 |
620 600 500 |
11 5 |
|
8 |
3 1 3 |
2 6 4 |
600 720 720 |
11 9 |
|
9 |
5 2 3 |
2 6 2 |
600 960 390 |
11 9 |
|
10 |
1 1 5 |
1 0 2 |
210 100 600 |
10 5 |
Транспортная задача
Решите транспортную задачу, условия которой
представлены ее матрицей:
|
Номер варианта |
Матрица транспортной задачи |
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
