Экономико-математические модели. Задача 60. ТК 8. Решение Проверим необходимое и достаточное условие разрешимости задачи
 Скачать 108.25 Kb.
|
  Решение: Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 280 + 220 + 300 = 800 ∑b = 190 + 140 + 180 + 120 + 170 = 800 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу.
Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Искомый элемент равен c12=3. Для этого элемента запасы равны 280, потребности 140. Поскольку минимальным является 140, то вычитаем его. x12 = min(280,140) = 140.
Искомый элемент равен c21=3. Для этого элемента запасы равны 220, потребности 190. Поскольку минимальным является 190, то вычитаем его. x21 = min(220,190) = 190.
Искомый элемент равен c13=9. Для этого элемента запасы равны 140, потребности 180. Поскольку минимальным является 140, то вычитаем его. x13 = min(140,180) = 140.
Искомый элемент равен c23=12. Для этого элемента запасы равны 30, потребности 40. Поскольку минимальным является 30, то вычитаем его. x23 = min(30,40) = 30.
Искомый элемент равен c33=16. Для этого элемента запасы равны 300, потребности 10. Поскольку минимальным является 10, то вычитаем его. x33 = min(300,10) = 10.
Искомый элемент равен c34=19. Для этого элемента запасы равны 290, потребности 120. Поскольку минимальным является 120, то вычитаем его. x34 = min(290,120) = 120.
Искомый элемент равен c35=46. Для этого элемента запасы равны 170, потребности 170. Поскольку минимальным является 170, то вычитаем его. x35 = min(170,170) = 170.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 3*140 + 9*140 + 3*190 + 12*30 + 16*10 + 19*120 + 46*170 = 12870 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 3; 0 + v2 = 3; v2 = 3 u1 + v3 = 9; 0 + v3 = 9; v3 = 9 u2 + v3 = 12; 9 + u2 = 12; u2 = 3 u2 + v1 = 3; 3 + v1 = 3; v1 = 0 u3 + v3 = 16; 9 + u3 = 16; u3 = 7 u3 + v4 = 19; 7 + v4 = 19; v4 = 12 u3 + v5 = 46; 7 + v5 = 46; v5 = 39
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;5): 0 + 39 > 35; ∆15 = 0 + 39 - 35 = 4 > 0 Выбираем максимальную оценку свободной клетки (1;5): 35 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5 → 1,3 → 3,3 → 3,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 140. Прибавляем 140 к объемам грузов, стоящих в плюсовых клетках и вычитаем 140 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 3; 0 + v2 = 3; v2 = 3 u1 + v5 = 35; 0 + v5 = 35; v5 = 35 u3 + v5 = 46; 35 + u3 = 46; u3 = 11 u3 + v3 = 16; 11 + v3 = 16; v3 = 5 u2 + v3 = 12; 5 + u2 = 12; u2 = 7 u2 + v1 = 3; 7 + v1 = 3; v1 = -4 u3 + v4 = 19; 11 + v4 = 19; v4 = 8
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (3;2): 11 + 3 > 11; ∆32 = 11 + 3 - 11 = 3 > 0 Выбираем максимальную оценку свободной клетки (3;2): 11 Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,2 → 3,5 → 1,5 → 1,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 3; 0 + v2 = 3; v2 = 3 u3 + v2 = 11; 3 + u3 = 11; u3 = 8 u3 + v3 = 16; 8 + v3 = 16; v3 = 8 u2 + v3 = 12; 8 + u2 = 12; u2 = 4 u2 + v1 = 3; 4 + v1 = 3; v1 = -1 u3 + v4 = 19; 8 + v4 = 19; v4 = 11 u1 + v5 = 35; 0 + v5 = 35; v5 = 35
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 3*110 + 35*170 + 3*190 + 12*30 + 11*30 + 16*150 + 19*120 = 12220 Анализ оптимального плана. Из 1-ой базы необходимо груз направить в 2-й пункт (110 ед.), в 5-й пункт (170 ед.) Из 2-ой базы необходимо груз направить в 1-й пункт (190 ед.), в 3-й пункт (30 ед.) Из 3-ей базы необходимо груз направить в 2-й пункт (30 ед.), в 3-й пункт (150 ед.), в 4-й пункт (120 ед.) |