Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Забайкальский государственный университет»
Факультет дополнительного профессионального образования
Кафедра экономики и бухгалтерского учета
Контрольная работа
По предмету: «Методы оптимальных решений»
Вариант 1
Выполнил: студент гр. ЭКБ- 12-1 Лескова А.С.
Проверил: Мурзина Н.В.
Чита
2014
Задача 1.
Заданы таблица межотраслевых потоков и таблица конечных продуктов. Постройте межотраслевой баланс в отчетном периоде и, увеличив конечный продукт на 10 процентов, постройте межотраслевой баланс в плановом периоде.
|
Таблицы межотраслевых потоков 1 2 3 4 5 1 46,05 3,52 17,61 4,26 6,59 2 4,26 35,56 0,86 2,86 0,58 3 0 0 0 0 0 4 0,53 24,26 1,02 16,15 0 5 15,26 4,53 0,5 4,89 0,58 |
Таблица конечных продуктов 1 35,33 66,54 32,14 20,56 2,23 |
Решение.
1. Построим межотраслевой баланс в отчетном периоде и занесем в таблицу:
|
Отрасли |
1 |
2 |
3 |
4 |
5 |
Итого |
Конечный продукт |
Валовой продукт |
|
1 |
46,05 |
3,52 |
17,61 |
4,26 |
6,59 |
78,03 |
35,33 |
113,36 |
|
2 |
4,26 |
35,56 |
0,86 |
2,86 |
0,58 |
44,12 |
66,54 |
110,66 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
32,14 |
32,14 |
|
4 |
0,53 |
24,26 |
1,02 |
16,15 |
0 |
41,96 |
20,56 |
62,52 |
|
5 |
15,26 |
4,53 |
0,5 |
4,89 |
0,58 |
25,76 |
2,23 |
27,99 |
|
Итого |
66,1 |
67,87 |
19,99 |
28,16 |
7,75 |
189,87 |
156,8 |
346,67 |
|
Чистая продукция |
47,26 |
42,79 |
12,15 |
34,36 |
20,24 |
156,8 |
||
|
Всего |
113,36 |
110,66 |
32,14 |
62,52 |
27,99 |
346,67 |
2. Построим межотраслевой баланс в плановом периоде.
Найдем матрицу А прямых затрат, элементы которой рассчитаем по формуле :
Она имеет неотрицательные значения и удовлетворяет критерию продуктивности:
Поэтому для любого вектора конечного продукта можно найти необходимый объем валового выпуска по формуле:
.
Матрица .
Обратная к ней матрица имеет вид:
.
Посчитаем величину конечного продукта в плановом периоде, увеличив его на 10 %:
.
Определим величину валовой продукции в плановом периоде:
=.
Посчитаем межотраслевые потоки в плановом периоде по формуле
и построим межотраслевой баланс в плановом периоде
|
Отрасли |
1 |
2 |
3 |
4 |
5 |
Итого |
Конечный продукт |
Валовой продукт |
|
1 |
50,66 |
3,87 |
19,37 |
4,69 |
7,25 |
85,83 |
38,86 |
124,70 |
|
2 |
4,69 |
39,12 |
0,95 |
3,15 |
0,64 |
48,53 |
73,19 |
121,73 |
|
3 |
0,00 |
0,00 |
0,00 |
0,00 |
0,00 |
0,00 |
35,35 |
35,35 |
|
4 |
0,58 |
26,69 |
1,12 |
17,77 |
0,00 |
46,16 |
22,62 |
68,77 |
|
5 |
16,79 |
4,98 |
0,55 |
5,38 |
0,64 |
28,34 |
2,45 |
30,79 |
|
Итого |
72,71 |
74,66 |
21,99 |
30,98 |
8,53 |
208,86 |
172,48 |
381,34 |
|
Чистая продукция |
51,99 |
47,07 |
13,37 |
37,80 |
22,26 |
172,48 |
||
|
Всего |
124,70 |
121,73 |
35,35 |
68,77 |
30,79 |
381,34 |
Задача 2.
Построить на плоскости область решений линейных неравенств и геометрически найти максимальное и минимальное значения целевой функции в этой области.
Решение.
Определим сначала многоугольник решений, для чего систему ограничений-неравенств запишем в виде уравнений и пронумеруем их:
Построим область допустимых значений: на координатной плоскости нанесем прямые, соответствующие неравенствам системы ограничений, и отметим соответствующие полуплоскости.
Прямая (1) – х2 = 2 + 2х1 – проходит через точки:
|
х1 |
0 |
–1 |
|
х2 |
2 |
0 |
Прямая (2) – х2 = –1+ 1/3 х1 – проходит через точки:
|
х1 |
0 |
3 |
|
х2 |
–1 |
0 |
Прямая (3) – х2 = 8 – 4/3 х1 – проходит через точки:
|
х1 |
0 |
6 |
|
х2 |
8 |
0 |
Построим область допустимых значений – треугольник ABC.
Координаты вектор-градиента равны коэффициентам целевой функции:
.
Проведём через область ABCD произвольную линию уровня перпендикулярно направлению градиента – прямая, линия уровня.
Поскольку задача решается на максимум, перемещаем линию уровня в направлении возрастания целевой функции, т.е. в направлении градиента.
Предельное положение – линия (4). Следовательно, точка В является оптимальным решением, обеспечивающим максимальное значение целевой функции.
Если задачу решать на минимум, перемещаем линию уровня в направлении убывания целевой функции, т.е. в направлении антиградиента.
Предельное положение – линия (5). Следовательно, точка А является оптимальным решением, обеспечивающим минимальное значение целевой функции.
Определим координаты точки В как пересечение прямых (2) и (3):
Следовательно, максимальное значение целевая функция достигает в точке и равно .
Определим координаты точки А как пересечение прямых (2) и оси Ох1:
Следовательно, минимальное значение целевая функция достигает в точке и равно .
Задача3.
Решить симплексным методом задачи:
Решение.
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений
Введем искусственные переменные x:
Для постановки задачи на максимум целевую функцию запишем так:
Z(X) = x1 + 4x2 + x3 – Mx6 – Mx7 → max
Из уравнений выражаем искусственные переменные и подставим в целевую функцию:
x6 = 4 + x1 – 2x2 – x3
x7 = 6 – 2x1 – 3x2 – x3+x5
Z(X) = x1 + 4x2 + x3 – M(4 + x1 – 2x2 – x3) – M(6 – 2x1 – 3x2 – x3 + x5) → max
Z(X) = (1 + M)x1 + (4 + 5M)x2 + (1 + 2M)x3 + (– M)x5 + (– 10M) → max
Решим систему уравнений относительно базисных переменных: x6, x4, x7.
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,9,0,4,6)
|
азис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x6 |
4 |
– 1 |
2 |
1 |
0 |
0 |
1 |
0 |
|
x4 |
9 |
3 |
1 |
2 |
1 |
0 |
0 |
0 |
|
x7 |
6 |
2 |
3 |
1 |
0 |
– 1 |
0 |
1 |
|
Z(X0) |
– 10M |
– 1 – M |
– 4 – 5M |
– 1 – 2M |
0 |
M |
0 |
0 |
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее: min (4 : 2 , 9 : 1 , 6 : 3 ) = 2
Следовательно, 1-ая строка является ведущей.
Получаем новую симплекс – таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x2 |
2 |
– 0.5 |
1 |
0.5 |
0 |
0 |
0.5 |
0 |
|
x4 |
7 |
3.5 |
0 |
1.5 |
1 |
0 |
– 0.5 |
0 |
|
x7 |
0 |
3.5 |
0 |
– 0.5 |
0 |
– 1 |
– 1.5 |
1 |
|
Z(X1) |
8 |
– 3 – 3.5M |
0 |
1 + M |
0 |
M |
2 + 2.5M |
0 |
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min ( – , 7 : 3.5 , 0 : 3.5 ) = 0
Следовательно, 3-ая строка является ведущей.
Получаем новую симплекс – таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
min |
|
x2 |
2 |
0 |
1 |
3/7 |
0 |
– 1/7 |
2/7 |
1/7 |
– |
|
x4 |
7 |
0 |
0 |
2 |
1 |
1 |
1 |
– 1 |
7 |
|
x1 |
0 |
1 |
0 |
– 1/7 |
0 |
– 2/7 |
– 3/7 |
2/7 |
– |
|
Z(X3) |
8 |
0 |
0 |
4/7 |
0 |
– 6/7 |
5/7 + M |
6/7 + M |
0 |
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai5
и из них выберем наименьшее:
min ( – , 7 : 1 , – ) = 7
Следовательно, 2-ая строка является ведущей.
Получаем новую симплекс- таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x2 |
3 |
0 |
1 |
5/7 |
1/7 |
0 |
3/7 |
0 |
|
x5 |
7 |
0 |
0 |
2 |
1 |
1 |
1 |
– 1 |
|
x1 |
2 |
1 |
0 |
3/7 |
2/7 |
0 |
– 1/7 |
0 |
|
Z(X3) |
14 |
0 |
0 |
22/7 |
6/7 |
0 |
14/7 + M |
M |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Так как в оптимальном решении отсутствуют искусственные переменные (равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так: x2 = 3, x1 = 2.
Тогда Zmax = 4*3 + 1*2 = 14.
Задача 4.
Решить методом потенциалов транспортные задачи:
|
1 |
2 |
3 |
4 |
5 |
Всего |
|
|
1 |
1 |
5 |
7 |
9 |
3 |
10 |
|
2 |
4 |
6 |
4 |
7 |
13 |
20 |
|
3 |
1 |
5 |
3 |
4 |
9 |
10 |
|
4 |
2 |
4 |
2 |
10 |
3 |
30 |
|
5 |
3 |
2 |
5 |
6 |
4 |
10 |
|
всего |
10 |
10 |
25 |
25 |
30 |
Решение.
Проверим равенство запасов и потребностей:
; .
Равенство не выполняется (), следовательно, транспортная задача является открытой. Сведём её к закрытой модели путем введения фиктивного поставщика. Положим его запас равным дефициту ресурса (100 – 80 = 20), а тарифы на перевозки - равными 0.
Построим новую транспортную таблицу и определим начальное распределение методом северо-западного угла:
|
10 |
10 |
25 |
25 |
30 |
||||||
|
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
||||||||||
|
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
10 |
10 |
|||||||||
|
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
||||||||||
|
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
5 |
25 |
|||||||||
|
10 |
3 |
2 |
5 |
6 |
10 |
4 |
||||
|
20 |
0 |
0 |
0 |
0 |
20 |
0 |
||||
При этом стоимость перевозок составит:
Проверяем количество заполненных клеток – 8, а должно быть Следовательно, опорный план является вырожденным.
Строим новый план методом минимальной стоимости, порядок заполнения клеток указан.
|
vj |
1 |
5 |
7 |
2 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
(1) |
0 |
0 |
||||||||
|
5 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
15 |
(6) |
5 |
(7) |
||||||||
|
2 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
(5) |
||||||||||
|
-5 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
25 |
(3) |
5 |
(4) |
||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
(2) |
||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
(8) |
При этом стоимость перевозок составит:
Проверяем количество заполненных клеток – 8, а должно быть Следовательно, опорный план является вырожденным. Для получения невырожденного плана принудительно добавляем нуль (0) в клетку (1, 2) и (1, 3).
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v2 = 5
u1 + v3 = 7
u2 + v4 = 7
u2 + v5 = 13
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 5, v3 = 7, u4 = -5, v5 = 8, u2 = 5, v4 = 2, u3 = 2, u5 = -3, u6 = -8
Найдём оценки свободных клеток :
S14 = 9 – (0 + 2) = 7
S15 = 3 – (0 + 8) = -5
S21 = 4 – (5 + 1) = -2
S22 = 6 – (5 + 5) = -4
S23 = 4 – (5 + 7) = -8
S31 = 1 – (2 + 1) = -2
S32 = 5 – (2 + 5) = -2
S33 = 3 – (2 + 7) = -6
S41 = 2 – (-5 + 1) = 6
S42 = 4 – (-5 + 5) = 4
S44 = 10 – (-5 + 2) = 13
S51 = 3 – (-3 + 1) = 5
S53 = 5 – (-3 + 7) = 1
S54 = 6 – (-3 + 2) = 7
S55 = 4 – (-3 + 8) = -1
S61 = 0 – (-8 + 1) = 7
S62 = 0 – (-8 + 5) = 3
S63 = 0 – (-8 + 7) = 1
S64 = 0 – (-8 + 2) = 6
S65 = 0 – (-8 + 8) = 0
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (2; 3) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
5 |
7 |
2 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
0 |
|||||||||
|
5 |
20 |
4 |
6 |
+ |
4 |
7 |
– |
13 |
|||
|
15 |
5 |
||||||||||
|
2 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
-5 |
30 |
2 |
4 |
– |
2 |
10 |
+ |
3 |
|||
|
25 |
5 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (25; 5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
5 |
7 |
9 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
0 |
|||||||||
|
-2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
5 |
15 |
||||||||||
|
1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
-5 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
При этом стоимость перевозок составит:
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v2 = 5
u1 + v3 = 7
u2 + v3 = 4
u2 + v4 = 7
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 5, v3 = 7, u4 = -5, v5 = 8, u2 = -2, v4 = 9, u3 = 1, u5 = -3, u6 = -8
Найдём оценки свободных клеток :
S14 = 9 – (0 + 9) = 0
S15 = 3 – (0 + 8) = -5
S21 = 4 – (-2 + 1) = 5
S22 = 6 – (-2 + 5) = 3
S25 = 13 – (-2 + 8) = 7
S31 = 1 – (1 + 1) = -1
S32 = 5 – (1 + 5) = -1
S33 = 3 – (1 + 7) = -5
S41 = 2 – (-5 + 1) = 6
S42 = 4 – (-5 + 5) = 4
S44 = 10 – (-5 + 9) = 6
S51 = 3 – (-3 + 1) = 5
S53 = 5 – (-3 + 7) = 1
S54 = 6 – (-3 + 9) = 0
S55 = 4 – (-3 + 8) = -1
S61 = 0 – (-8 + 1) = 7
S62 = 0 – (-8 + 5) = 3
S63 = 0 – (-8 + 7) = 1
S64 = 0 – (-8 + 9) = 1
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является. Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (3; 3) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
5 |
7 |
9 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
0 |
|||||||||
|
-2 |
20 |
4 |
6 |
– |
4 |
+ |
7 |
13 |
|||
|
5 |
15 |
||||||||||
|
1 |
10 |
1 |
5 |
+ |
3 |
– |
4 |
9 |
|||
|
10 |
|||||||||||
|
-5 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (10; 5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
5 |
7 |
8 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
0 |
|||||||||
|
-1 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
-4 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
5 |
5 |
||||||||||
|
-5 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
При этом стоимость перевозок составит:
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v2 = 5
u1 + v3 = 7
u2 + v4 = 7
u3 + v3 = 3
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 5, v3 = 7, u4 = -5, v5 = 8, u2 = -1, v4 = 8, u3 = -4, u5 = -3, u6 = -8
Найдём оценки свободных клеток :
S14 = 9 – (0 + 8) = 1
S15 = 3 – (0 + 8) = -5
S21 = 4 – (-1 + 1) = 4
S22 = 6 – (-1 + 5) = 2
S23 = 4 – (-1 + 7) = -2
S25 = 13 – (-1 + 8) = 6
S31 = 1 – (-4 + 1) = 4
S32 = 5 – (-4 + 5) = 6
S41 = 2 – (-5 + 1) = 6
S42 = 4 – (-5 + 5) = 4
S44 = 10 – (-5 + 8) = 7
S51 = 3 – (-3 + 1) = 5
S53 = 5 – (-3 + 7) = 1
S54 = 6 – (-3 + 8) = 1
S55 = 4 – (-3 + 8) = -1
S61 = 0 – (-8 + 1) = 7
S62 = 0 – (-8 + 5) = 3
S63 = 0 – (-8 + 7) = 1
S64 = 0 – (-8 + 8) = 0
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (1; 5) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
5 |
7 |
8 |
8 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
– |
7 |
9 |
+ |
3 |
|||
|
10 |
0 |
0 |
|||||||||
|
-1 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
-4 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
5 |
5 |
||||||||||
|
-5 |
30 |
2 |
4 |
+ |
2 |
10 |
– |
3 |
|||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-8 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (0; 10) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
5 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
0 |
|||||||||
|
4 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
5 |
5 |
||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
При этом стоимость перевозок составит:
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v2 = 5
u1 + v5 = 3
u2 + v4 = 7
u3 + v3 = 3
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 5, v3 = 2, u4 = 0, v5 = 3, u2 = 4, v4 = 3, u3 = 1, u5 = -3, u6 = -3
Найдём оценки свободных клеток :
S13 = 7 – (0 + 2) = 5
S14 = 9 – (0 + 3) = 6
S21 = 4 – (4 + 1) = -1
S22 = 6 – (4 + 5) = -3
S23 = 4 – (4 + 2) = -2
S25 = 13 – (4 + 3) = 6
S31 = 1 – (1 + 1) = -1
S32 = 5 – (1 + 5) = -1
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 5) = -1
S44 = 10 – (0 + 3) = 7
S51 = 3 – (-3 + 1) = 5
S53 = 5 – (-3 + 2) = 6
S54 = 6 – (-3 + 3) = 6
S55 = 4 – (-3 + 3) = 4
S61 = 0 – (-3 + 1) = 2
S62 = 0 – (-3 + 5) = -2
S63 = 0 – (-3 + 2) = 1
S64 = 0 – (-3 + 3) = 0
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (2; 2) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
5 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
– |
5 |
7 |
9 |
+ |
3 |
|||
|
10 |
0 |
0 |
|||||||||
|
4 |
20 |
4 |
+ |
6 |
4 |
– |
7 |
13 |
|||
|
20 |
|||||||||||
|
1 |
10 |
1 |
5 |
– |
3 |
+ |
4 |
9 |
|||
|
5 |
5 |
||||||||||
|
0 |
30 |
2 |
4 |
+ |
2 |
10 |
– |
3 |
|||
|
20 |
10 |
||||||||||
|
-3 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (0; 5; 20; 10) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
4 |
4 |
5 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
0 |
20 |
||||||||||
|
-1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
5 |
5 |
||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v5 = 3
u2 + v2 = 6
u2 + v4 = 7
u3 + v3 = 3
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 4, v3 = 4, u4 = 0, v5 = 3, u2 = 2, v4 = 5, u3 = -1, u5 = 2, u6 = -3
Найдём оценки свободных клеток :
S12 = 5 – (0 + 4) = 1
S13 = 7 – (0 + 4) =3
S14 = 9 – (0 + 3) = 6
S21 = 4 – (2 + 1) = 1
S23 = 4 – (2 + 4) = -2
S25 = 13 – (2 + 3) = 8
S31 = 1 – (-1 + 1) = 1
S32 = 5 – (-1 + 4) = 2
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 4) = 0
S44 = 10 – (0 + 3) = 7
S51 = 3 – (2 + 1) = 0
S53 = 5 – (2 + 4) = -1
S54 = 6 – (2 + 3) = 1
S55 = 4 – (2 + 3) = -1
S61 = 0 – (-3 + 1) = 2
S62 = 0 – (-3 + 4) = -1
S63 = 0 – (-3 + 4) = 1
S64 = 0 – (-3 + 3) = 0
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (2; 3) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
4 |
4 |
5 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
+ |
4 |
– |
7 |
13 |
|||
|
0 |
20 |
||||||||||
|
-1 |
10 |
1 |
5 |
– |
3 |
+ |
4 |
9 |
|||
|
5 |
5 |
||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (5; 20) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
4 |
2 |
5 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
0 |
5 |
15 |
|||||||||
|
-1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
20 |
10 |
||||||||||
|
-2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
20 |
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v5 = 3
u2 + v2 = 6
u2 + v3 = 4
u2 + v4 = 7
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 4, v3 = 2, u4 = 0, v5 = 3, u2 = 2, v4 = 5, u3 = -1, u5 = -2, u6 = -3
Найдём оценки свободных клеток :
S12 = 5 – (0 + 4) = 1
S13 = 7 – (0 + 2) =5
S14 = 9 – (0 + 5) = 4
S21 = 4 – (2 + 1) = 1
S25 = 13 – (2 + 3) = 8
S31 = 1 – (-1 + 1) = 1
S32 = 5 – (-1 + 4) = 2
S33 = 3 – (-1 + 2) = 2
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 4) = 0
S44 = 10 – (0 + 5) = 5
S51 = 3 – (-2 + 1) = 4
S53 = 5 – (-2 + 2) = 5
S54 = 6 – (-2 + 5) = 3
S55 = 4 – (-2 + 3) = 3
S61 = 0 – (-3 + 1) = 2
S62 = 0 – (-3 + 4) = -1
S63 = 0 – (-3 + 2) = 1
S64 = 0 – (-3 + 5) = -2
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (6; 4) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
4 |
2 |
5 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
+ |
4 |
– |
7 |
13 |
|||
|
0 |
5 |
15 |
|||||||||
|
-1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
– |
2 |
10 |
+ |
3 |
|||
|
20 |
10 |
||||||||||
|
-2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
+ |
0 |
– |
0 |
|||
|
20 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (20; 20; 15) = 15. Перераспределяем 0 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
4 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
0 |
20 |
||||||||||
|
1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
5 |
25 |
||||||||||
|
-2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
15 |
5 |
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v5 = 3
u2 + v2 = 6
u2 + v3 = 4
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v4 = 0
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 4, v3 = 2, u4 = 0, v5 = 3, u2 = 2, v4 = 3, u3 = 1, u5 = -2, u6 = -3
Найдём оценки свободных клеток :
S12 = 5 – (0 + 4) = 1
S13 = 7 – (0 + 2) =5
S14 = 9 – (0 + 4) = 5
S21 = 4 – (2 + 1) = 1
S24 = 7 – (2 + 4) = 1
S25 = 13 – (2 + 3) = 8
S31 = 1 – (1 + 1) = -1
S32 = 5 – (1 + 4) = 0
S33 = 3 – (1 + 2) = 0
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 4) = 0
S44 = 10 – (0 + 4) = 6
S51 = 3 – (-2 + 1) = 4
S53 = 5 – (-2 + 2) = 5
S54 = 6 – (-2 + 4) = 4
S55 = 4 – (-2 + 3) = 3
S61 = 0 – (-3 + 1) = 2
S62 = 0 – (-3 + 4) = -1
S63 = 0 – (-3 + 2) = 1
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (6; 2) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
4 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
– |
6 |
+ |
4 |
7 |
13 |
|||
|
0 |
20 |
||||||||||
|
1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
– |
2 |
10 |
+ |
3 |
|||
|
5 |
25 |
||||||||||
|
-2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
+ |
0 |
0 |
0 |
– |
0 |
|||
|
15 |
5 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (0; 5; 5) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
3 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
1 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
5 |
25 |
||||||||||
|
1 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
0 |
15 |
5 |
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v5 = 3
u2 + v3 = 4
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v2 = 0
u6 + v4 = 0
u6 + v5 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 3, v3 = 2, u4 = 0, v5 = 3, u2 = 2, v4 = 3, u3 = 1, u5 = 1, u6 = -3
Найдём оценки свободных клеток :
S12 = 5 – (0 + 3) = 2
S13 = 7 – (0 + 2) =5
S14 = 9 – (0 + 3) = 6
S21 = 4 – (2 + 1) = 1
S22 = 6 – (2 + 3) = 1
S24 = 7 – (2 + 3) = 2
S25 = 13 – (2 + 3) = 8
S31 = 1 – (1 + 1) = -1
S32 = 5 – (1 + 3) = 2
S33 = 3 – (1 + 2) = 0
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 3) = 1
S44 = 10 – (0 + 3) = 7
S51 = 3 – (1 + 1) = 1
S53 = 5 – (1 + 2) = 3
S54 = 6 – (1 + 3) = 4
S55 = 4 – (1 + 3) = 0
S61 = 0 – (-3 + 1) = 2
S63 = 0 – (-3 + 2) = 1
Поскольку среди оценок свободных клеток есть отрицательные, то найденный план оптимальным не является.
Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой – клетка (3; 1) – и строим цикл, первая вершина которого находится в выбранной клетке, а остальные – в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «–», начиная со свободной клетки.
|
vj |
1 |
3 |
2 |
3 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
– |
1 |
5 |
7 |
9 |
+ |
3 |
|||
|
10 |
0 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
1 |
10 |
+ |
1 |
5 |
3 |
– |
4 |
9 |
|||
|
10 |
|||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
5 |
25 |
||||||||||
|
1 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-3 |
20 |
0 |
0 |
0 |
+ |
0 |
– |
0 |
|||
|
0 |
15 |
5 |
Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «–»): min (10; 10; 5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:
|
vj |
1 |
4 |
2 |
4 |
3 |
||||||
|
ui |
10 |
10 |
25 |
25 |
30 |
||||||
|
0 |
10 |
1 |
5 |
7 |
9 |
3 |
|||||
|
5 |
5 |
||||||||||
|
2 |
20 |
4 |
6 |
4 |
7 |
13 |
|||||
|
20 |
|||||||||||
|
0 |
10 |
1 |
5 |
3 |
4 |
9 |
|||||
|
5 |
5 |
||||||||||
|
0 |
30 |
2 |
4 |
2 |
10 |
3 |
|||||
|
5 |
25 |
||||||||||
|
-2 |
10 |
3 |
2 |
5 |
6 |
4 |
|||||
|
10 |
|||||||||||
|
-4 |
20 |
0 |
0 |
0 |
0 |
0 |
|||||
|
0 |
20 |
Определим потенциалы и оценки свободных клеток:
u1 + v1 = 1
u1 + v5 = 3
u2 + v3 = 4
u3 + v1 = 1
u3 + v4 = 4
u4 + v3 = 2
u4 + v5 = 3
u5 + v2 = 2
u6 + v2 = 0
u6 + v4 = 0
Пусть u1 = 0, тогда
v1 = 1, v2 = 4, v3 = 2, u4 = 0, v5 = 3, u2 = 2, v4 = 4, u3 = 0, u5 = -2, u6 = -4
Найдём оценки свободных клеток :
S12 = 5 – (0 + 2) = 3
S14 = 9 – (0 + 4) = 5
S21 = 4 – (2 + 1) = 1
S22 = 6 – (2 + 2) = 2
S24 = 7 – (2 + 4) = 1
S25 = 13 – (2 + 3) = 8
S31 = 1 – (0 + 1) = 0
S32 = 5 – (0 + 2) = 3
S33 = 3 – (0 + 2) = 1
S41 = 2 – (0 + 1) = 1
S42 = 4 – (0 + 2) = 2
S44 = 10 – (0 + 4) = 6
S51 = 3 – (-2 + 1) = 4
S53 = 5 – (-2 + 2) = 5
S54 = 6 – (-2 + 4) = 4
S55 = 4 – (-2 + 3) = 3
S61 = 0 – (-4 + 1) = 3
S63 = 0 – (-4 + 2) = 2
S65 = 0 – (-4 + 3) = 1
Поскольку все оценки неотрицательны, найденный план является оптимальным. Однако оптимальное решение не единственно, поскольку среди оценок свободных клеток есть нулевые.
Список использованных источников
PAGE \* MERGEFORMAT1