ДЗ - Контрольная работа математика. Задача 1 1 Задача 2 7 Задача 3 11 Задача 4 22 Задача 5 25 Список использованных источников 31 Задача 1
 Скачать 267.33 Kb.
|
Задача 5На три базы А1, А2, А3 поступил однородный груз в количестве 250, 600, 300 тонн. Полученный груз требуется перевезти в пять пунктов В1, В2, В3, В4, В5 потребности которых составляют 150, 300 , 350, 450, 250 тонн. Стоимости перевозки единицы груза из пункта Аi в пункт Bj составляет сij и представлены в таблице.
Требуется составить такой план перевозки груза, при котором суммарные затраты на перевозки будут минимальны. Решение: Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 250 + 600 + 300 = 1150 ∑b = 150 + 300 + 350 + 450 + 250 = 1500 Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 350 (1150—1500). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Занесем исходные данные в распределительную таблицу.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Искомый элемент равен c12=1. Для этого элемента запасы равны 250, потребности 300. Поскольку минимальным является 250, то вычитаем его. x12 = min(250,300) = 250. Искомый элемент равен c25=1. Для этого элемента запасы равны 600, потребности 250. Поскольку минимальным является 250, то вычитаем его. x25 = min(600,250) = 250. Искомый элемент равен c33=2. Для этого элемента запасы равны 300, потребности 350. Поскольку минимальным является 300, то вычитаем его. x33 = min(300,350) = 300. Искомый элемент равен c22=3. Для этого элемента запасы равны 350, потребности 50. Поскольку минимальным является 50, то вычитаем его. x22 = min(350,50) = 50. Искомый элемент равен c21=4. Для этого элемента запасы равны 300, потребности 150. Поскольку минимальным является 150, то вычитаем его. x21 = min(300,150) = 150. Искомый элемент равен c24=5. Для этого элемента запасы равны 150, потребности 450. Поскольку минимальным является 150, то вычитаем его. x24 = min(150,450) = 150. Искомый элемент равен c43=0. Для этого элемента запасы равны 350, потребности 50. Поскольку минимальным является 50, то вычитаем его. x43 = min(350,50) = 50. Искомый элемент равен c44=0. Для этого элемента запасы равны 300, потребности 300. Поскольку минимальным является 300, то вычитаем его. x44 = min(300,300) = 300.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 1*250 + 4*150 + 3*50 + 5*150 + 1*250 + 2*300 + 0*50 + 0*300 = 2600 Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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 u4 + v4 = 0; 3 + u4 = 0; u4 = -3 u4 + v3 = 0; -3 + v3 = 0; v3 = 3 u3 + v3 = 2; 3 + u3 = 2; u3 = -1 u2 + v5 = 1; 2 + v5 = 1; v5 = -1
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;4): 0 + 3 > 2; ∆14 = 0 + 3 - 2 = 1 > 0 Выбираем максимальную оценку свободной клетки (1;4): 2 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 150. Прибавляем 150 к объемам грузов, стоящих в плюсовых клетках и вычитаем 150 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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 + v5 = 1; 2 + v5 = 1; v5 = -1 u1 + v4 = 2; 0 + v4 = 2; v4 = 2 u4 + v4 = 0; 2 + u4 = 0; u4 = -2 u4 + v3 = 0; -2 + v3 = 0; v3 = 2 u3 + v3 = 2; 2 + u3 = 2; u3 = 0
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 1*100 + 2*150 + 4*150 + 3*200 + 1*250 + 2*300 + 0*50 + 0*300 = 2450 Список использованных источников1. Гармаш А.Н., Орлова И.В. Математические методы в управлении: учебное пособие, - М.: Вузовский учебник, 2017. – 272 с. 2. Зайцев, М.Г. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы / М.Г. Зайцев, С.Е. Варюхин. - М.: Дело АНХ, 2015. - 640 c. 3.Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – 2-е изд., испр. и доп. - М.: Вузовский учебник: ИНФРА-М, 2018. – 140 с. 4.Федосеев В.В., Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебник для бакалавров. 3-е изд., перераб. и доп.- М.: Издательство Юрайт, 2018. – 304 с. |