По данным таблицы поставить задачу линейного программирования (транспортную задачу), то есть написать целевую функцию и систему линейных ограничений.
Составить начальный опорный план двумя способами: методом северо-западного угла и методом минимального элемента. Для каждого начального опорного плана подсчитать стоимость перевозок. Найти оптимальный план для полученной транспортной задачи. Определить, единственен он или нет.
Решение
1) Целевая функция
Z(X)=71x11+63x12+19x13+27x14+34x15+49x21+34x22+81x23+43x24+69x25+51x31+45x32+34x33+64x34+28x35+22x41+52x42+48x43+15x44+72x45+40x51+24x52+60x53+54x54+32x55 →min
2) Система линейных ограничений
x11+x12+x13+x14+x15=90
x21+x22+x23+x24+x25=80
x31+x32+x33+x34+x3=130
x41+x42+x43+x44+x45=75
x51+x52+x53+x54+x55=45
x11+x21+x31+x41+x51=100
x12+x22+x32+x42+x52=110
x13+x23+x33+x43+x53=77
x14+x24+x34+x44+x54=63
x15+x25+x35+x45+x55=70
xij≥0, i=0,1.2,…5, j=0,1,2,…5.
3) Определение сбалансированности
∑a = 90 + 80 + 130 + 75 + 45 = 420∑b = 100 + 110 + 77 + 63 + 70 = 420Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 Запасы
A1 71 63 19 27 34 90
A2 49 34 81 43 69 80
A3 51 45 34 64 28 130
A4 22 52 48 15 72 75
A5 40 24 60 54 32 45
Потребности
100 110 77 63 70
Этап I. Построение начального опорного плана.1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 71[90] 63 19 27 34 90
A2 49[10] 34[70] 81 43 69 80
A3 51 45[40] 34[77] 64[13] 28 130
A4 22 52 48 15[50] 72[25] 75
A5 40 24 60 54 32[45] 45
Потребности
100 110 77 63 70
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.2
. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.Значение целевой функции для этого опорного плана (стоимость перевозок) равно:F(x) = 71*90 + 49*10 + 34*70 + 45*40 + 34*77 + 64*13 + 15*50 + 72*25 + 32*45 = 18500
4) Метод минимального элемента
Этап I. Построение начального опорного плана.1. Используя метод наименьшей стоимости, построим опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 71[13] 63 19[77] 27 34 90
A2 49[15] 34[65] 81 43 69 80
A3 51[60] 45 34 64 28[70] 130
A4 22[12] 52 48 15[63] 72 75
A5 40 24[45] 60 54 32 45
Потребности
100 110 77 63 70
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.Значение целевой функции для этого опорного плана (стоимость перевозки) равно:F(x) = 71*13 + 19*77 + 49*15 + 34*65 + 51*60 + 28*70 + 22*12 + 15*63 + 24*45 = 12640Этап II
Задать вопрос
на новый заказ в Автор24.
