Математика, контрольная работа, 3 семестр 1 вариант
.doc
Занесем рассчитанные потенциалы в таблицу. Подсчитаем оценки свободных клеток, полагая, что для них :
Первый опорный план является не оптимальным, так как , поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки -
Для клетки А2В4 построим цикл перераспределения груза. Для этого в перспективную клетку А2В4 поставим знак +, а в остальных вершинах многоугольника чередующиеся знаки -, +, - :
Затем из чисел , стоящих в минусовых клетках, выбираем наименьшее, т.е. . Прибавляем 115 к объемам грузов, стоящих в плюсовых клетках и вычитаем 115 из , стоящих в минусовых клетках. В результате получим новый опорный план II.
|
В1 |
В2 |
В3 |
В4 |
Потенциалы |
||||||
|
|||||||||||
А1 |
|
3 |
|
16 |
|
17 |
|
2 |
|||
125 |
|
|
85 |
||||||||
А2 |
|
21 |
|
19 |
|
15 |
|
2 |
|||
|
75 |
|
115 |
||||||||
А3 |
|
11 |
|
13 |
|
4 |
|
3 |
|||
255 |
|
125 |
|
||||||||
А4 |
|
0 |
|
0 |
|
0 |
|
0 |
|||
10 |
|
|
|
||||||||
Потенциалы |
|
Определяем значение целевой функции:
Число занятых клеток в II плане 7, следовательно, план невырожденный.
Проверяем оптимальность плана методом потенциалов, для этого находим потенциалы по занятым клеткам, полагая
Затем рассчитаем оценки свободных клеток:
План не оптимальный, так как .
Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем А3В4, в которую записываем +, затем строим цикл перераспределения:
125
255 |
+ -
- + |
85
А3В4 |
→ |
210
170 |
|
А1В4
85 |
|
В1 |
В2 |
В3 |
В4 |
Потенциалы |
||||||
|
|||||||||||
А1 |
|
3 |
|
16 |
|
17 |
|
2 |
|||
210 |
|
|
|
||||||||
А2 |
|
21 |
|
19 |
|
15 |
|
2 |
|||
|
75 |
|
125 |
||||||||
А3 |
|
11 |
|
13 |
11 |
4 |
|
3 |
|||
170 |
|
125 |
85 |
||||||||
А4 |
|
0 |
|
0 |
|
0 |
|
0 |
|||
10 |
|
|
|
||||||||
Потенциалы |
|
Число занятых клеток 7, а должно быть , следовательно, план III невырожденный.
Вычислим значение целевой функции:
Проверяем оптимальность плана III методом потенциалов. Находим потенциалы по занятым клеткам:
Проверим оценку свободных клеток:
План не оптимальный. .
Проводим улучшение плана III путем перераспределения груза. В качестве перспективной клетки для загрузки выбираем А3В2, в которую записываем +, затем строим цикл перераспределения:
75
А3В2 |
- +
+ - |
115
85 |
→ |
А2В2
75 |
|
190
10 |
Определяем груз перераспределения , после проведения операции перераспределения получаем план IV.
|
В1 |
В2 |
В3 |
В4 |
Потенциалы |
||||||
|
|||||||||||
А1 |
|
3 |
|
16 |
|
17 |
|
2 |
|||
210 |
|
|
|
||||||||
А2 |
|
21 |
|
19 |
|
15 |
|
2 |
|||
|
|
|
190 |
||||||||
А3 |
|
11 |
|
13 |
11 |
4 |
|
3 |
|||
170 |
75 |
125 |
10 |
||||||||
А4 |
|
0 |
|
0 |
|
0 |
|
0 |
|||
10 |
|
|
|
||||||||
Потенциалы |
|
Вычислим значение целевой функции:
Проверяем оптимальность плана методом потенциалов. Находим потенциалы по занятым клеткам:
Проверим оценку свободных клеток:
Поскольку все оценки больше или равны нулю, то план оптимален.
Анализ плана. Из первой базы необходимо весь груз направить в первый магазин, из второй базы направить в четвертый магазин, а груз с третьей базы следует вывозить в первый, второй, третий и четвертый магазины в количестве 170, 75, 125 и 10 ед. соответственно. При этом плане потребность второго магазина В2 остается неудовлетворительной в размере 10 ед. Общая стоимость доставки груза потребителям будет минимальной и составлять 4385 тыс. руб.