Создан заказ №1297566
10 июля 2016
Провести моделирование и решить специальную задачу линейного программирования Транспортная задача
Как заказчик описал требования к работе:
Нужен аспирант или преподаватель, чтобы помочь сделать решение задач по экономическому анализу, сроки очень сжатые. Отзовитесь, пожалуйста!
Фрагмент выполненной работы:
Провести моделирование и решить специальную задачу линейного программирования.
Транспортная задача.
Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ. (работа была выполнена специалистами author24.ru) Имеются экономические оценки транспортных затрат (в у.е.) на перевозку 1тонны песка с карьеров на ремонтные участки. Числовые данные для решения содержатся ниже в матрице планирования
Требуется:
1) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.
2) Что произойдет с оптимальным планом, если изменятся условия перевозок:
а) появится запрет на перевозки от первого карьера до второго участка работ?;
б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?
Матрица планирования:
карьеры участки работ В1
В2
В3 В4
В5 предложение
А1
3 4 5 15 24 15
А2
19 2 22 4 13 15
А3 20 27 1 17 19 15
Потребности 11 11 11 16 11
Решение:
Построим математическую модель данной задачи. Пусть xij – объем перевозки от i-го карьера к j-му участку. Тогда, чтобы потребность каждого из участков была реализована, необходимо составить уравнения баланса для каждой строки таблицы распределений:
Аналогично, чтобы спрос каждого из участков был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы:
Очевидно, что объем перевозимого песка не может быть отрицательным, поэтому следует дополнительно предположить, что
.
Суммарные затраты F выражаются через коэффициенты затрат на перевозку и себестоимость единицы продукции на каждом заводе
1 способ.
Решим задачу методом потенциалов
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 15 + 15 + 15 = 45
∑b = 11 + 11 + 11 + 16 + 11 = 60
Как видно, суммарная потребность песка на участках превышает запасы песка на карьерах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный (фиктивный) карьер с запасом песка, равным 15 (45—60). Тарифы перевозки единицы песка с карьера на участки во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
карьеры участки работ В1
В2
В3 В4
В5 предложение
А1
3 4 5 15 24 15
А2
19 2 22 4 13 15
А3 20 27 1 17 19 15
А4
15
Потребности 11 11 11 16 11
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1
Для этого элемента запасы равны 15, потребности 11. Поскольку минимальным является 11, то вычитаем его.
x33 = min(15,11) = 11.
3 4 x
15 24 15
19 2 x
4 13 15
20 27 1 17 19 15 - 11 = 4
0 0 x
0 0 15
11 11 11 - 11 = 0 16 11 0
Искомый элемент равен 2
Для этого элемента запасы равны 15, потребности 11. Поскольку минимальным является 11, то вычитаем его.
x22 = min(15,11) = 11.
3 x
x
15 24 15
19 2 x
4 13 15 - 11 = 4
20 x
1 17 19 4
0 x
x
0 0 15
11 11 - 11 = 0 0 16 11 0
Искомый элемент равен 3 . Для этого элемента запасы равны 15, потребности 11. Поскольку минимальным является 11, то вычитаем его. x11 = min(15,11) = 11. Аналогично заполняем все строки и столбцы, получим
1 2 3 4 5 Предложения
1 3[11] 4 5 15[4] 24 15
2 19 2[11] 22 4[4] 13 15
3 20 27 1[11] 17[4] 19 15
4 0 0 0 0[4] 0[11] 15
Потребности 11 11 11 16 11
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Значение целевой функции для этого опорного плана равно:
F(x) = 3·11 + 15·4 + 2·11 + 4·4 + 1·11 + 17·4 + 0·4 + 0·11 = 210
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u1 + v4 = 15; 0 + v4 = 15; v4 = 15
u2 + v4 = 4; 15 + u2 = 4; u2 = -11
u2 + v2 = 2; -11 + v2 = 2; v2 = 13
u3 + v4 = 17; 15 + u3 = 17; u3 = 2
u3 + v3 = 1; 2 + v3 = 1; v3 = -1
u4 + v4 = 0; 15 + u4 = 0; u4 = -15
u4 + v5 = 0; -15 + v5 = 0; v5 = 15
v1=3 v2=13 v3=-1 v4=15 v5=15
u1=0 3[11] 4 5 15[4] 24
u2=-11 19 2[11] 22 4[4] 13
u3=2 20 27 1[11] 17[4] 19
u4=-15 0 0 0 0[4] 0[11]
план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;2): 0 + 13 > 4; ∆12 = 0 + 13 - 4 = 9
Выбираем максимальную оценку свободной клетки (1;2): 4
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Предложение
1 3[11] 4[+] 5 15[4][-] 24 15
2 19 2[11][-] 22 4[4][+] 13 15
3 20 27 1[11] 17[4] 19 15
4 0 0 0 0[4] 0[11] 15
Потребности 11 11 11 16 11
Цикл приведен в таблице (1,2 → 1,4 → 2,4 → 2,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 4...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
11 июля 2016
Заказ завершен, заказчик получил финальный файл с работой
5
Провести моделирование и решить специальную задачу линейного программирования
Транспортная задача.jpg
2021-04-13 10:46
Последний отзыв студента о бирже Автор24
Общая оценка
4.5
Положительно
Спасибо большое! Очень помогли и выручили! буду обращаться еще много впереди задач...
Хочешь такую же работу?
300 ₽
