На складах А, В, С находится сортовое зерно 100, 150, 250 т, которое нужно доставить в четыре пункта. Пункту 1 необходимо поставить 50 т, пункту 2 – 100, пункту 3 - 200, пункту 4 – 150 т сортового зерна. Стоимость доставки 1 т зерна со склада А в указанные пункты соответственно равна (ден. ед.) 80, 30, 50, 50: со склада В – 90, 30, 60, 70: со склада С – 80, 90, 40, 30. Составьте оптимальный план перевозки зерна из условия минимума стоимости перевозки.
Решение
Обозначим через Xij – количество груза, которое необходимо перевезти от i-го поставщика (склада) к j-му потребителю
i = 1, 2, 3;
j = 1, 2, 3, 4.
Составим экономико-математическую модель задачи.
Переменные:
X11 – объем груза, перевозимого c I склада потребителю № 1, т;
Х12 – объем груза, перевозимого c I склада потребителю № 2, т;
Х13 – объем груза, перевозимого c I склада потребителю № 3, т;
X14 – объем груза, перевозимого c I склада потребителю № 4, т;
X21 – объем груза, перевозимого cо II склада потребителю № 1, т;
Х22 – объем груза, перевозимого cо II склада потребителю № 2, т;
Х23 – объем груза, перевозимого cо II склада потребителю № 3, т;
X24 – объем груза, перевозимого cо II склада потребителю № 4, т;
X31 – объем груза, перевозимого c III склада потребителю № 1, т;
Х32 – объем груза, перевозимого c III склада потребителю № 2, т;
Х33 – объем груза, перевозимого c III склада потребителю № 3, т;
X34 – объем груза, перевозимого c III склада потребителю № 4, т;
Ограничения:
по возможности I склада, т х11 + х12 + х13+ х14 = 100;
по возможности II склада, т х21 + х22 + х23+ х24 = 150;
по возможности III склада, тх31 + х32 + х33+ х34 = 250.
по потребности потребителя № 1, т х11 + х21+ х31 = 50;
по потребности потребителя № 2, т х12 + х22+ х32 = 100;
по потребности потребителя № 3, т х13 + х23+ х33 = 200;
по потребности потребителя № 4, т х14 + х24+ х34 = 150.
Целевая функция:
F(x) = 80х11 + 30х12 + 50х13 + 50х14 + 90х21 + 30х22 + 60х23 + 70 х24 +
+ 80х31 + 90х32 + 40х33 + 30 х34→min
Вначале определяется исходный вариант перевозок, а затем последовательно производится его улучшение до получения оптимального плана.
Для получения исходного плана перевозок используем правило «северо-западного» угла
. Заполнение клеток таблицы ведём в направлении от верхней левой до нижней правой (таблица 5). То есть, за счёт ресурсов первого поставщика удовлетворяются потребности первого потребителя (заполняется клетка 1.1). Если ресурс больше, чем потребность первого потребителя, то за счёт остатка удовлетворяются потребности второго потребителя (заполняется клетка 1.2). Если же ресурса первого поставщика недостаточно, то недостающая часть берётся у второго поставщика (заполняется клетка 2.1). Так постепенно распределяются ресурсы всех поставщиков. Следуя этому правилу, получим опорный план, представленный в таблице.
Таблица 5 – Исходный план перевозок
Склады Потребители Запас
Qi
№ 1 № 2 № 3 № 4
I 80
50 30
50 50
х 50
х 100
II 90
х 30
50 60
100 70
х 150
III 80
х 90
х 40
100 30
150 250
Спрос bj
50 100 200 150 500=500
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
х11 = 50 т.; х12 = 50 т.; х22 = 50 т.; х23 = 100 т.; х33 = 100 т.; х34 = 150 т.
F (x) = 80*50+30*50+30*50+60*100+40*100+30*150 = 21 500 ден. ед.
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
По алгоритму решения следует каждую свободную клетку проверить на оптимальность
Задать вопрос
на новый заказ в Автор24.
