Автор работы: Пользователь скрыл имя, 08 Апреля 2014 в 00:38, контрольная работа
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.
Транспортная задача линейного программирования 3
Задача материальный запас 18
Задача склад 19
Задача транспорт 20
Задача распределение 21
5*5 + 3*20 + 4*25 + 5*10 + 2*15 + 1*25 + 5*20 + 4*35 + 7*30 = 740
Шаг 3. Определяем оценку для каждой свободной клетки.
(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,2; 1,1; 2,1; 2,2; ).
Оценка свободной клетки равна Δ12 = (4) - (5) + (4) - (5) = -2.
(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3; 1,6; 4,6; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ13 = (6) - (3) + (7) - (4) + (5) - (2) = 9.
(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,4; 1,6; 4,6; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ14 = (8) - (3) + (7) - (4) + (5) - (1) = 12.
(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5; 1,6; 4,6; 4,5; ).
Оценка свободной клетки равна Δ15 = (9) - (3) + (7) - (4) = 9.
(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,3; 2,1; 1,1; 1,6; 4,6; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ23 = (8) - (4) + (5) - (3) + (7) - (4) + (5) - (2) = 12.
(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,4; 2,1; 1,1; 1,6; 4,6; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ24 = (3) - (4) + (5) - (3) + (7) - (4) + (5) - (1) = 8.
(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,5; 2,1; 1,1; 1,6; 4,6; 4,5; ).
Оценка свободной клетки равна Δ25 = (1) - (4) + (5) - (3) + (7) - (4) = 2.
(2;6): В свободную клетку (2;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,6; 2,1; 1,1; 1,6; ).
Оценка свободной клетки равна Δ26 = (6) - (4) + (5) - (3) = 4.
(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,1; 3,5; 4,5; 4,6; 1,6; 1,1; ).
Оценка свободной клетки равна Δ31 = (6) - (5) + (4) - (7) + (3) - (5) = -4.
(3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,2; 3,5; 4,5; 4,6; 1,6; 1,1; 2,1; 2,2; ).
Оценка свободной клетки равна Δ32 = (3) - (5) + (4) - (7) + (3) - (5) + (4) - (5) = -8.
(3;6): В свободную клетку (3;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,6; 3,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ36 = (8) - (5) + (4) - (7) = 0.
(4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,1; 4,6; 1,6; 1,1; ).
Оценка свободной клетки равна Δ41 = (8) - (7) + (3) - (5) = -1.
(4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,2; 4,6; 1,6; 1,1; 2,1; 2,2; ).
Оценка свободной клетки равна Δ42 = (6) - (7) + (3) - (5) + (4) - (5) = -4.
(4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,3; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ43 = (5) - (4) + (5) - (2) = 4.
(4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,4; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ44 = (2) - (4) + (5) - (1) = 2.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (3,2;) равные: (-8).
Переход от неоптимального опорного плана к лучшему.
Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (3;2) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
5 |
4 |
6 |
8 |
9 |
3[25] |
25 |
2 |
4[30] |
5[5] |
8 |
3 |
1 |
6 |
35 |
3 |
6 |
3[5] |
2[15] |
1[25] |
5[15] |
8 |
60 |
4 |
8 |
6 |
5 |
2 |
4[40] |
7[25] |
65 |
Потребности |
30 |
10 |
15 |
25 |
55 |
50 |
3*25 + 4*30 + 5*5 + 3*5 + 2*15 + 1*25 + 5*15 + 4*40 + 7*25 = 700
Шаг 4. Определяем оценку для каждой свободной клетки.
(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1; 1,6; 4,6; 4,5; 3,5; 3,2; 2,2; 2,1; ).
Оценка свободной клетки равна Δ11 = (5) - (3) + (7) - (4) + (5) - (3) + (5) - (4) = 8.
(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,2; 1,6; 4,6; 4,5; 3,5; 3,2; ).
Оценка свободной клетки равна Δ12 = (4) - (3) + (7) - (4) + (5) - (3) = 6.
(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3; 1,6; 4,6; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ13 = (6) - (3) + (7) - (4) + (5) - (2) = 9.
(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,4; 1,6; 4,6; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ14 = (8) - (3) + (7) - (4) + (5) - (1) = 12.
(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5; 1,6; 4,6; 4,5; ).
Оценка свободной клетки равна Δ15 = (9) - (3) + (7) - (4) = 9.
(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).
Оценка свободной клетки равна Δ23 = (8) - (5) + (3) - (2) = 4.
(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,4; 2,2; 3,2; 3,4; ).
Оценка свободной клетки равна Δ24 = (3) - (5) + (3) - (1) = 0.
(2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,5; 2,2; 3,2; 3,5; ).
Оценка свободной клетки равна Δ25 = (1) - (5) + (3) - (5) = -6.
(2;6): В свободную клетку (2;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,6; 2,2; 3,2; 3,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ26 = (6) - (5) + (3) - (5) + (4) - (7) = -4.
(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,1; 3,2; 2,2; 2,1; ).
Оценка свободной клетки равна Δ31 = (6) - (3) + (5) - (4) = 4.
(3;6): В свободную клетку (3;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,6; 3,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ36 = (8) - (5) + (4) - (7) = 0.
(4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,1; 4,5; 3,5; 3,2; 2,2; 2,1; ).
Оценка свободной клетки равна Δ41 = (8) - (4) + (5) - (3) + (5) - (4) = 7.
(4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,2; 4,5; 3,5; 3,2; ).
Оценка свободной клетки равна Δ42 = (6) - (4) + (5) - (3) = 4.
(4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,3; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ43 = (5) - (4) + (5) - (2) = 4.
(4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,4; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ44 = (2) - (4) + (5) - (1) = 2.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (2,5;) равные: (-6).
Переход от неоптимального опорного плана к лучшему.
Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (2;5) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
5 |
4 |
6 |
8 |
9 |
3[25] |
25 |
2 |
4[30] |
5 |
8 |
3 |
1[5] |
6 |
35 |
3 |
6 |
3[10] |
2[15] |
1[25] |
5[10] |
8 |
60 |
4 |
8 |
6 |
5 |
2 |
4[40] |
7[25] |
65 |
Потребности |
30 |
10 |
15 |
25 |
55 |
50 |
3*25 + 4*30 + 1*5 + 3*10 + 2*15 + 1*25 + 5*10 + 4*40 + 7*25 = 670
Шаг 5. Определяем оценку для каждой свободной клетки.
(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1; 1,6; 4,6; 4,5; 2,5; 2,1; ).
Оценка свободной клетки равна Δ11 = (5) - (3) + (7) - (4) + (1) - (4) = 2.
(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,2; 1,6; 4,6; 4,5; 3,5; 3,2; ).
Оценка свободной клетки равна Δ12 = (4) - (3) + (7) - (4) + (5) - (3) = 6.
(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3; 1,6; 4,6; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ13 = (6) - (3) + (7) - (4) + (5) - (2) = 9.
(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,4; 1,6; 4,6; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ14 = (8) - (3) + (7) - (4) + (5) - (1) = 12.
(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5; 1,6; 4,6; 4,5; ).
Оценка свободной клетки равна Δ15 = (9) - (3) + (7) - (4) = 9.
(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,2; 2,5; 3,5; 3,2; ).
Оценка свободной клетки равна Δ22 = (5) - (1) + (5) - (3) = 6.
(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,3; 2,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ23 = (8) - (1) + (5) - (2) = 10.
(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,4; 2,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ24 = (3) - (1) + (5) - (1) = 6.
(2;6): В свободную клетку (2;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,6; 2,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ26 = (6) - (1) + (4) - (7) = 2.
(3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,1; 3,5; 2,5; 2,1; ).
Оценка свободной клетки равна Δ31 = (6) - (5) + (1) - (4) = -2.
(3;6): В свободную клетку (3;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,6; 3,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ36 = (8) - (5) + (4) - (7) = 0.
(4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,1; 4,5; 2,5; 2,1; ).
Оценка свободной клетки равна Δ41 = (8) - (4) + (1) - (4) = 1.
(4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,2; 4,5; 3,5; 3,2; ).
Оценка свободной клетки равна Δ42 = (6) - (4) + (5) - (3) = 4.
(4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,3; 4,5; 3,5; 3,3; ).
Оценка свободной клетки равна Δ43 = (5) - (4) + (5) - (2) = 4.
(4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,4; 4,5; 3,5; 3,4; ).
Оценка свободной клетки равна Δ44 = (2) - (4) + (5) - (1) = 2.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток (3,1;) равные: (-2).
Переход от неоптимального опорного плана к лучшему.
Поскольку в исходном опорном плане рассматриваемой задачи свободная клетка (3;1) имеет отрицательную оценку, то для получения плана, обеспечивающего меньшее значение целевой функции, эту клетку следует занять возможно большей поставкой, не нарушающей при этом условий допустимости плана.