Автор работы: Пользователь скрыл имя, 21 Ноября 2013 в 15:56, контрольная работа
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=3.
Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=3
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
Искомый элемент равен 3
Для этого элемента запасы равны 60, потребности
10. Поскольку минимальным является 10, то
вычитаем его.
x23 = min(60,10) = 10.
4 |
10 |
x |
7 |
30 |
8 |
6 |
3 |
5 |
60 - 10 = 50 |
x |
x |
x |
2 |
0 |
40 |
20 |
10 - 10 = 0 |
20 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 30, потребности
40. Поскольку минимальным является 30, то
вычитаем его.
x11 = min(30,40) = 30.
4 |
x |
x |
x |
30 - 30 = 0 |
8 |
6 |
3 |
5 |
50 |
x |
x |
x |
2 |
0 |
40 - 30 = 10 |
20 |
0 |
20 |
0 |
Искомый элемент равен 5
Для этого элемента запасы равны 50, потребности
20. Поскольку минимальным является 20, то
вычитаем его.
x24 = min(50,20) = 20.
4 |
x |
x |
x |
0 |
8 |
6 |
3 |
5 |
50 - 20 = 30 |
x |
x |
x |
2 |
0 |
10 |
20 |
0 |
20 - 20 = 0 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 30, потребности
20. Поскольку минимальным является 20, то
вычитаем его.
x22 = min(30,20) = 20.
4 |
x |
x |
x |
0 |
8 |
6 |
3 |
5 |
30 - 20 = 10 |
x |
x |
x |
2 |
0 |
10 |
20 - 20 = 0 |
0 |
0 |
0 |
Искомый элемент равен 8
Для этого элемента запасы равны 10, потребности
10. Поскольку минимальным является 10, то
вычитаем его.
x21 = min(10,10) = 10.
4 |
x |
x |
x |
0 |
8 |
6 |
3 |
5 |
10 - 10 = 0 |
x |
x |
x |
2 |
0 |
10 - 10 = 0 |
0 |
0 |
0 |
0 |
1 |
2 |
3 |
4 |
Запасы | |
1 |
4[30] |
10 |
11 |
7 |
30 |
2 |
8[10] |
6[20] |
3[10] |
5[20] |
60 |
3 |
9 |
12 |
1 |
2[10] |
10 |
Потребности |
40 |
20 |
10 |
30 |
В результате получен первый опорный
план, который является допустимым,
так как все грузы из баз
вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
2. Подсчитаем число занятых клеток таблицы,
их 6, а должно быть m + n - 1 = 6. Следовательно,
опорный план является невырожденным.
Значение целевой функции для этого опорного
плана равно:
F(x) = 4*30 + 8*10 + 6*20 + 3*10 + 5*20 + 2*10 = 470
Этап II. Улучшение
опорного плана.
Проверим оптимальность опорного плана.
Найдем предварительные
потенциалы ui, vi. по занятым
клеткам таблицы, в которых ui + vi
= cij, полагая, что u1 = 0.
u1 + v1 = 4; 0 + v1 = 4; v1
= 4
u2 + v1 = 8; 4 + u2 = 8; u2
= 4
u2 + v2 = 6; 4 + v2 = 6; v2
= 2
u2 + v3 = 3; 4 + v3 = 3; v3
= -1
u2 + v4 = 5; 4 + v4 = 5; v4
= 1
u3 + v4 = 2; 1 + u3 = 2; u3
= 1
v1=4 |
v2=2 |
v3=-1 |
v4=1 | |
u1=0 |
4[30] |
10 |
11 |
7 |
u2=4 |
8[10] |
6[20] |
3[10] |
5[20] |
u3=1 |
9 |
12 |
1 |
2[10] |
Опорный план является оптимальным, так
все оценки свободных клеток удовлетворяют
условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 4*30 + 8*10 + 6*20 + 3*10 + 5*20 + 2*10 = 470
Анализ оптимального
плана.
Из 1-го склада необходимо весь груз направить
в 1-й магазин
Из 2-го склада необходимо груз направить
в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин
(10), в 4-й магазин (20)
Из 3-го склада необходимо весь груз направить
в 4-й магазин
Информация о работе Решение задач линейного программирования