|
|
Задача 1 2 задача 2 7 задача 3 10 Ответы на контрольные вопросы 20 задача 1
План
поставок
|
Б1
|
9 [10] -
|
15
|
10
|
1 +
|
10
|
|
Б2
|
3 [5] +
|
8 [10] -
|
3 [15]
|
2
|
30
|
|
Б3
|
6
|
2 [0] +
|
5
|
8 [19] -
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Новый опорный план
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9 [0]
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [15]
|
8
|
3 [15]
|
2
|
30
|
|
Б3
|
6
|
2 [10]
|
5
|
8 [9]
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 3; 9 + u2 = 3; u2 = -6
u2 + v3 = 3; -6 + v3 = 3; v3 = 9
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u3 + v4 = 8; 1 + u3 = 8; u3 = 7
u3 + v2 = 2; 7 + v2 = 2; v2 = -5
u4 + v4 = 0; 1 + u4 = 0; u4 = -1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1=9
|
v2=-5
|
v3=9
|
v4=1
|
|
|
u1=0
|
9 [10]
|
15
|
10
|
1 [10]
|
|
|
u2=-6
|
3 [15]
|
8
|
3 [15]
|
2
|
|
|
u3=7
|
6
|
2 [10]
|
5
|
8 [9]
|
|
|
u4=1
|
0
|
0
|
0
|
0 [6]
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9 [0] -
|
15
|
10
|
1 [10] +
|
10
|
|
Б2
|
3 [15] +
|
8
|
3 [15] -
|
2
|
30
|
|
Б3
|
6
|
2 [10]
|
5 +
|
8 [9] -
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Новый опорный план
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [15]
|
8
|
3 [15]
|
2
|
30
|
|
Б3
|
6
|
2 [10]
|
5 [0]
|
8 [9]
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u3 + v4 = 8; 1 + u3 = 8; u3 = 7
u3 + v2 = 2; 7 + v2 = 2; v2 = -5
u3 + v3 = 5; 7 + v3 = 5; v3 = -2
u2 + v3 = 3; -2 + u2 = 3; u2 = 5
u2 + v1 = 3; 5 + v1 = 3; v1 = -2
u4 + v4 = 0; 1 + u4 = 0; u4 = -1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1=-2
|
v2=-5
|
v3=-2
|
v4=1
|
|
|
u1=0
|
9
|
15
|
10
|
1 [10]
|
|
|
u2=5
|
3 [15]
|
8
|
3 [15]
|
2
|
|
|
u3=7
|
6
|
2 [10]
|
5 [0]
|
8 [9]
|
|
|
u4=-1
|
0
|
0
|
0
|
0 [6]
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [15]
|
8
|
3 [15] -
|
2 +
|
30
|
|
Б3
|
6
|
2 [10]
|
5 [0] +
|
8 [9] -
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Новый опорный план
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [15]
|
8
|
3 [6]
|
2 [9]
|
30
|
|
Б3
|
6
|
2 [10]
|
5 [9]
|
8
|
19
|
|
Б4
|
0
|
0
|
0
|
0 [6]
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u2 + v4 = 2; 1 + u2 = 2; u2 = 1
u2 + v1 = 3; 1 + v1 = 3; v1 = 2
u2 + v3 = 3; 1 + v3 = 3; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 2; 3 + v2 = 2; v2 = -1
u4 + v4 = 0; 1 + u4 = 0; u4 = -1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1=2
|
v2=-1
|
v3=2
|
v4=1
|
|
|
u1=0
|
9
|
15
|
10
|
1 [10]
|
|
|
u2=1
|
3 [15]
|
8
|
3 [6]
|
2 [9]
|
|
|
u3=3
|
6
|
2 [10]
|
5 [9]
|
8 [9]
|
|
|
u4=-1
|
0
|
0
|
0
|
0 [6]
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [15] -
|
8
|
3 [6]
|
2 [9] +
|
30
|
|
Б3
|
6
|
2 [10]
|
5 [9]
|
8
|
19
|
|
Б4
|
0 +
|
0
|
0
|
0 [6] -
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Новый опорный план
|
|
|
|
|
|
|
|
|
Потребители/Базы
|
П1
|
П2
|
П3
|
П4
|
План
поставок
|
|
Б1
|
9
|
15
|
10
|
1 [10]
|
10
|
|
Б2
|
3 [9]
|
8
|
3 [6]
|
2 [15]
|
30
|
|
Б3
|
6
|
2 [10]
|
5 [9]
|
8
|
19
|
|
Б4
|
0 [6]
|
0
|
0
|
0
|
6
|
|
Заказы
|
15
|
10
|
15
|
25
|
|
|
|
|
|
|
|
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
u2 + v4 = 2; 1 + u2 = 2; u2 = 1
u2 + v1 = 3; 1 + v1 = 3; v1 = 2
u4 + v1 = 0; 2 + u4 = 0; u4 = -2
u2 + v3 = 3; 1 + v3 = 3; v3 = 2
u3 + v3 = 5; 2 + u3 = 5; u3 = 3
u3 + v2 = 2; 3 + v2 = 2; v2 = -1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1=2
|
v2=-1
|
v3=2
|
v4=1
|
|
|
u1=0
|
9
|
15
|
10
|
1 [10]
|
|
|
u2=1
|
3 [9]
|
8
|
3 [6]
|
2 [15]
|
|
|
u3=3
|
6
|
2 [10]
|
5 [9]
|
8
|
|
|
u4=-2
|
0 [6]
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
План является оптимальным, так как ui+vj <=cij
|
|
|
|
Подсчитаем целевую функцию
|
|
Целевая функция: 3*9+0*6+2*10+3*6+5*9+1*10+2*15=
|
|
|
|
150
|
|
|
|
Удостоверимся в правильности решения задачи путём использования пакета Excel «Поиск Решения».
Видно, что результат совпал. Таким образом, задача решена верно.
Проанализируем опорный план:
Из 1-го склада необходимо груз направить в 1-й магазин (70 ед.), в 3-й магазин (30 ед.)
Из 2-го склада необходимо груз направить в 2-й магазин (80 ед.), в 3-й магазин (10 ед.)
Из 3-го склада необходимо груз направить в 3-й магазин (20 ед.), в 4-й магазин (80 ед.)
Ответы на контрольные вопросы:
1. Что такое транспортная задача?
2. Что такое целевая функция и система ограничений?
3. Какие методы линейного программирования для решения транспортной задачи вы знаете?
4. В чем суть метода минимального тарифа?
Вопрос 1) Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача, определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом.
Вопрос 2) Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи.
Ограничения-равенства выражают зависимость между, проектными параметрами, которая должна учитываться при нахождении решения. Эти ограничения отражают законы природы, наличие ресурсов т. п.
Вопрос 3) Метод северно-западного угла, метод минимального тарифа (стоимости), метод потенциалов. Эти методы использовались при решении задачи № 3.
Вопрос 4) В отличие от метода северно-западного угла, в методе минимального элемента выбор пунктов отправления и пунктов назначения производится ориентируясь на тарифы перевозок, т.е. в каждом шаге нужно выбрать клетку с минимальным тарифом перевозок. Если таких клеток несколько, то выбирают одну из них. Надо отметить, что при данном методе определения заполняемой клетки, стоимость перевозок как правило бывает меньше, чем при методе северо-западного угла. Поэтому целесообразно начальный опорный план найти методом минимального элемента. |
|
|
Скачать 215.16 Kb.