Ольга, благодарю за контрольные по строит. материалам, качественно и в срок, рад был с Вами поработать))
Информация о работе
Подробнее о работе
Оптимизировать план распределения ресурсов по видам работ при котором общие затраты будут минимальны
- 10 страниц
- 2019 год
- 13 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Условие задачи (согласно варианту) представлены в таблице:
Ресурсы Работы, которые нужно выполнить Объем имеющихся ресурсов
J1 J2 J3 J4 J5 J6
R1 7 8 5 13 6 9 400
R2 18 7 10 10 9 2 400
R3 11 6 15 7 3 4 200
R4 11 3 6 12 6 8 600
Объём требуемых ресурсов 400 200 280 200 400 320
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 400 + 400 + 200 + 600 = 1600
∑b = 400 + 200 + 280 + 200 + 400 + 320 = 1800
Как видно, суммарная потребность ресурсов превышает имеющиеся. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительного (фиктивного) поставщика ресурсов с объемом, равным 200 (1600—1800). Тарифы полагаем равными нулю.
Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен c11=7. Для этого элемента запасы равны 400, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x11 = min(400,400) = 400.
x x x x x 400 - 400 = 0
18 7 10 10 9 2 400
11 6 15 7 3 4 200
11 3 6 12 6 8 600
0 0 0 0 0 0 200
400 - 400 = 0 200 280 200 400 320
Искомый элемент равен c22=7. Для этого элемента запасы равны 400, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x22 = min(400,200) = 200.
7 x x x x x 0
18 7 10 10 9 2 400 - 200 = 200
11 x 15 7 3 4 200
11 x 6 12 6 8 600
0 x 0 0 0 0 200
0 200 - 200 = 0 280 200 400 320
Искомый элемент равен c23=10. Для этого элемента запасы равны 200, потребности 280. Поскольку минимальным является 200, то вычитаем его.
x23 = min(200,280) = 200.
7 x x x x x 0
18 7 10 x x x 200 - 200 = 0
11 x 15 7 3 4 200
11 x 6 12 6 8 600
0 x 0 0 0 0 200
0 0 280 - 200 = 80 200 400 320
Искомый элемент равен c33=15. Для этого элемента запасы равны 200, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x33 = min(200,80) = 80.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 3 4 200 - 80 = 120
11 x x 12 6 8 600
0 x x 0 0 0 200
0 0 80 - 80 = 0 200 400 320
Искомый элемент равен c34=7. Для этого элемента запасы равны 120, потребности 200. Поскольку минимальным является 120, то вычитаем его.
x34 = min(120,200) = 120.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 x x 120 - 120 = 0
11 x x 12 6 8 600
0 x x 0 0 0 200
0 0 0 200 - 120 = 80 400 320
Искомый элемент равен c44=12. Для этого элемента запасы равны 600, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x44 = min(600,80) = 80.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 x x 0
11 x x 12 6 8 600 - 80 = 520
0 x x x 0 0 200
0 0 0 80 - 80 = 0 400 320
Искомый элемент равен c45=6. Для этого элемента запасы равны 520, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x45 = min(520,400) = 400.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 x x 0
11 x x 12 6 8 520 - 400 = 120
0 x x x x 0 200
0 0 0 0 400 - 400 = 0 320
Искомый элемент равен c46=8. Для этого элемента запасы равны 120, потребности 320. Поскольку минимальным является 120, то вычитаем его.
x46 = min(120,320) = 120.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 x x 0
11 x x 12 6 8 120 - 120 = 0
0 x x x x 0 200
0 0 0 0 0 320 - 120 = 200
Искомый элемент равен c56=0. Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x56 = min(200,200) = 200.
7 x x x x x 0
18 7 10 x x x 0
11 x 15 7 x x 0
11 x x 12 6 8 0
0 x x x x 0 200 - 200 = 0
0 0 0 0 0 200 - 200 = 0
Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.
7 8 5 13 6 9 400
18 7 10 10 9 2 400
11 6 15 7 3 4 200
11 3 6 12 6 8 600
0 0 0 0 0 0 200
400 200 280 200 400 320
Искомый элемент равен c12=8, но т.к. ограничения выполнены, то x12=0.
B1 B2 B3 B4 B5 B6 Запасы
A1 7[400] 8[0] 5 13 6 9 400
A2 18 7[200] 10[200] 10 9 2 400
A3 11 6 15[80] 7[120] 3 4 200
A4 11 3 6 12[80] 6[400] 8[120] 600
A5 0 0 0 0 0 0[200] 200
Потребности
400 200 280 200 400 320
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 7*400 + 7*200 + 10*200 + 15*80 + 7*120 + 12*80 + 6*400 + 8*120 + 0*200 = 12560
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 7; 0 + v1 = 7; v1 = 7
u1 + v2 = 8; 0 + v2 = 8; v2 = 8
u2 + v2 = 7; 8 + u2 = 7; u2 = -1
u2 + v3 = 10; -1 + v3 = 10; v3 = 11
u3 + v3 = 15; 11 + u3 = 15; u3 = 4
u3 + v4 = 7; 4 + v4 = 7; v4 = 3
u4 + v4 = 12; 3 + u4 = 12; u4 = 9
u4 + v5 = 6; 9 + v5 = 6; v5 = -3
u4 + v6 = 8; 9 + v6 = 8; v6 = -1
u5 + v6 = 0; -1 + u5 = 0; u5 = 1
v1=7 v2=8 v3=11 v4=3 v5=-3 v6=-1
u1=0 7[400] 8[0] 5 13 6 9
u2=-1 18 7[200] 10[200] 10 9 2
u3=4 11 6 15[80] 7[120] 3 4
u4=9 11 3 6 12[80] 6[400] 8[120]
u5=1 0 0 0 0 0 0[200]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 11 > 5; ∆13 = 0 + 11 - 5 = 6 > 0
(3;2): 4 + 8 > 6; ∆32 = 4 + 8 - 6 = 6 > 0
(4;1): 9 + 7 > 11; ∆41 = 9 + 7 - 11 = 5 > 0
(4;2): 9 + 8 > 3; ∆42 = 9 + 8 - 3 = 14 > 0
(4;3): 9 + 11 > 6; ∆43 = 9 + 11 - 6 = 14 > 0
(5;1): 1 + 7 > 0; ∆51 = 1 + 7 - 0 = 8 > 0
(5;2): 1 + 8 > 0; ∆52 = 1 + 8 - 0 = 9 > 0
(5;3): 1 + 11 > 0; ∆53 = 1 + 11 - 0 = 12 > 0
(5;4): 1 + 3 > 0; ∆54 = 1 + 3 - 0 = 4 > 0
max(6,6,5,14,14,8,9,12,4) = 14
Выбираем максимальную оценку свободной клетки (4;2): 3
Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 Запасы
1 7[400] 8[0] 5 13 6 9 400
2 18 7[200][-] 10[200][+] 10 9 2 400
3 11 6 15[80][-] 7[120][+] 3 4 200
4 11 3[+] 6 12[80][-] 6[400] 8[120] 600
5 0 0 0 0 0 0[200] 200
Потребности
400 200 280 200 400 320
Цикл приведен в таблице (4,2 → 4,4 → 3,4 → 3,3 → 2,3 → 2,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 B5 B6 Запасы
A1 7[400] 8[0] 5 13 6 9 400
A2 18 7[120] 10[280] 10 9 2 400
A3 11 6 15[0] 7[200] 3 4 200
A4 11 3[80] 6 12 6[400] 8[120] 600
A5 0 0 0 0 0 0[200] 200
Потребности
400 200 280 200 400 320
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 7; 0 + v1 = 7; v1 = 7
u1 + v2 = 8; 0 + v2 = 8; v2 = 8
u2 + v2 = 7; 8 + u2 = 7; u2 = -1
u2 + v3 = 10; -1 + v3 = 10; v3 = 11
u3 + v3 = 15; 11 + u3 = 15; u3 = 4
u3 + v4 = 7; 4 + v4 = 7; v4 = 3
u4 + v2 = 3; 8 + u4 = 3; u4 = -5
u4 + v5 = 6; -5 + v5 = 6; v5 = 11
u4 + v6 = 8; -5 + v6 = 8; v6 = 13
u5 + v6 = 0; 13 + u5 = 0; u5 = -13
v1=7 v2=8 v3=11 v4=3 v5=11 v6=13
u1=0 7[400] 8[0] 5 13 6 9
u2=-1 18 7[120] 10[280] 10 9 2
u3=4 11 6 15[0] 7[200] 3 4
u4=-5 11 3[80] 6 12 6[400] 8[120]
u5=-13 0 0 0 0 0 0[200]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;3): 0 + 11 > 5; ∆13 = 0 + 11 - 5 = 6 > 0
(1;5): 0 + 11 > 6; ∆15 = 0 + 11 - 6 = 5 > 0
(1;6): 0 + 13 > 9; ∆16 = 0 + 13 - 9 = 4 > 0
(2;5): -1 + 11 > 9; ∆25 = -1 + 11 - 9 = 1 > 0
(2;6): -1 + 13 > 2; ∆26 = -1 + 13 - 2 = 10 > 0
(3;2): 4 + 8 > 6; ∆32 = 4 + 8 - 6 = 6 > 0
(3;5): 4 + 11 > 3; ∆35 = 4 + 11 - 3 = 12 > 0
(3;6): 4 + 13 > 4; ∆36 = 4 + 13 - 4 = 13 > 0
max(6,5,4,1,10,6,12,13) = 13
Выбираем максимальную оценку свободной клетки (3;6): 4
Для этого в перспективную клетку (3;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 6 Запасы
1 7[400] 8[0] 5 13 6 9 400
2 18 7[120][-] 10[280][+] 10 9 2 400
3 11 6 15[0]
Отсутствует
Оптимизировать план распределения ресурсов по видам работ, при котором общие затраты будут минимальны.
Ресурсы Работы, которые нужно выполнить Объем имеющихся ресурсов
J1 J2 J3 J4 J5 J6
R1 c11 c12 c13 c14 c15 c16 B1
R2 c21 c22 c23 c24 c25 c26 B2
R3 c31 c32 c33 c34 c35 c36 B3
R4 c41 c42 c43 c44 c45 c46 B4
Объём требуемых ресурсов A1 A2 A3 A4 A5 A6
cij – затраты, отвечающие выделению одной единицы ресурса Ri на работу Jj;
Вi– объем имеющихся ресурсов Ri;
Аij– объем требуемых ресурсов на работу Jj.
Проверить решение с помощью инструмента Поиск решений (надстройка Анализ данных Excel).
Отсутствует
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
