ДЗ - Контрольная работа математика. Задача 1 1 Задача 2 7 Задача 3 11 Задача 4 22 Задача 5 25 Список использованных источников 31 Задача 1
 Скачать 267.33 Kb.
|
Задача 2На три базы А1, А2, А3 поступил однородный груз в количестве 200, 600, 350 тонн. Полученный груз требуется перевезти в четыре пункта В1, В2, В3, В4 потребности которых составляют 150, 300 , 250, 450 тонн. Стоимости перевозки единицы груза из пункта Аi в пункт Bj составляет сij и представлены в таблице.
Требуется составить такой план перевозки груза, при котором суммарные затраты на перевозки будут минимальны. Решение: Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 200 + 600 + 350 = 1150 ∑b = 150 + 300 + 250 + 450 = 1150 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Искомый элемент равен c12=1. Для этого элемента запасы равны 200, потребности 300. Поскольку минимальным является 200, то вычитаем его. x12 = min(200,300) = 200. Искомый элемент равен c33=2. Для этого элемента запасы равны 350, потребности 250. Поскольку минимальным является 250, то вычитаем его. x33 = min(350,250) = 250. Искомый элемент равен c22=3. Для этого элемента запасы равны 600, потребности 100. Поскольку минимальным является 100, то вычитаем его. x22 = min(600,100) = 100. Искомый элемент равен c21=4. Для этого элемента запасы равны 500, потребности 150. Поскольку минимальным является 150, то вычитаем его. x21 = min(500,150) = 150. Искомый элемент равен c24=5. Для этого элемента запасы равны 350, потребности 450. Поскольку минимальным является 350, то вычитаем его. x24 = min(350,450) = 350. Искомый элемент равен c34=6. Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его. x34 = min(100,100) = 100.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 1*200 + 4*150 + 3*100 + 5*350 + 2*250 + 6*100 = 3950 Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 1; 0 + v2 = 1; v2 = 1 u2 + v2 = 3; 1 + u2 = 3; u2 = 2 u2 + v1 = 4; 2 + v1 = 4; v1 = 2 u2 + v4 = 5; 2 + v4 = 5; v4 = 3 u3 + v4 = 6; 3 + u3 = 6; u3 = 3 u3 + v3 = 2; 3 + v3 = 2; v3 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;4): 0 + 3 > 2; ∆14 = 0 + 3 - 2 = 1 > 0 Выбираем максимальную оценку свободной клетки (1;4): 2 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 200. Прибавляем 200 к объемам грузов, стоящих в плюсовых клетках и вычитаем 200 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v4 = 2; 0 + v4 = 2; v4 = 2 u2 + v4 = 5; 2 + u2 = 5; u2 = 3 u2 + v1 = 4; 3 + v1 = 4; v1 = 1 u2 + v2 = 3; 3 + v2 = 3; v2 = 0 u3 + v4 = 6; 2 + u3 = 6; u3 = 4 u3 + v3 = 2; 4 + v3 = 2; v3 = -2
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 2*200 + 4*150 + 3*300 + 5*150 + 2*250 + 6*100 = 3750 |