Транспортная задача линейного программирования

Пример 7.3.

Торговая фирма «Изумруд» включает четыре филиала (Ф1, Ф2, ФЗ, Ф4) и шесть складов (Cl, С2, СЗ, С4, С5, С6) в различных регионах страны. Каждый месяц различные филиалы фирмы Ф1, Ф2, ФЗ, Ф4 производят 110, 65, 50, 75 ед. продукции соответственно. Вся производимая продукция направляется на склады, вместимость которых следующая: 47,62,36,55,85,25 сд. продукции. Определите план перевозок, исходя из условия минимизации ежемесячных расходов на транспортировку. Издержки транспортировки продукции от филиалов до складов в уел. ед. представлены в табл. 7.2.

Таблица 7.2

Решение

Создание математической модели. Введем следующие обозначения:

Xjj — количество поставляемой продукции с г-го склада (С,) в /-й филиал (Ф_у), где 2 = 1,2, 3, 4, 5, 6;у= 1,2, 3, 4.

Тогда целевая функция будет иметь вид: 2х_и + 4х₁₂ + + 6дг₁₄ + з:₂₁ + Зз:₂₂ +.

⁺ &г₂з ⁺ 2*24 ⁺ 1*31 ^{+32 +} ^^хзз ⁺ 4x_3i + 4"г₄₁ + 2"г₄₂ + 5. г₄₃ + 7. г₄₄ + 2х₅₁ + 4т₅₂ + х₅₃ + + 7*54 + 5л*₆₁ + х_(У2 + 4х₆₃ + д:₆₄ min, при ограничениях:

^{х + x}i2 ^{+ хз + хи ^ 47 — количество поставляемой продукции со склада С_{ во все филиалы;}

х_2{ + х₂₂ + х₂₃ + х₂₄ < 62 — количество поставляемой продукции со склада С₂ во все филиалы;

х_3{ + х₃₂ + х₃₃ + х^ < 36 — количество поставляемой продукции со склада С₃ во все филиалы;

х₄₁ ^{+ Х}А2 ^{+ х}43 ^{+ х} ^ 55 — количество поставляемой продукции со склада С₄ во все филиалы;

х_5{ + х₅₂ + х₅₃ + х₅₄ < 85 — количество поставляемой продукции со склада С₅ во все филиалы;

х_6{ + д*_б2 + х_ез + д:₆₄ < 25 — количество поставляемой продукции со склада С₆ во все филиалы;

^{х +х}2 ^+Хз^+ХА1 ^+Л51″ ^|" ^Л:61 = НО — количество поставляемой продукции в филиал Ф, со всех складов;

х₁₂ + д:₂₂ + х₃₂ + х₄₂ + х₅₂ + х₆₂ = 65 — количество поставляемой продукции в филиал Ф₂ со всех складов;

х₁₃ + х₂₃ + х₃₃ + х_АЗ + х₅₃ + х₆₃ = 50 — количество поставляемой продукции в филиал Ф₃ со всех складов;

х₁₄ + х₂₄ + х₃₄ + х_и + х₅₄ + д*₆₄ = 75 — количество поставляемой продукции в филиал Ф₄ со всех складов;

> 0, где i = 1, 2, 3, 4, 5, 6; j = 1, 2, 3, 4.

Технология решения задачи в Excel.

• 1. Введем данные задачи, как показано на рис. 7.3. В столбце Н (115:118) введены возможности филиалов по производству продукции в месяц (в шт.), а в строке 9 (B9:G9) введены максимальные вместимости складов. В ячейках B5: G8 — издержки транспортировки продукции от филиалов до складов.
• 2. В диапазон ячеек B12: G15 введены возможные изменяемые значения (в шт.) перевозки продукции от филиалов фирмы до складов. Вводим в эти ячейки, например, числа 1.
• 3. В ячейке Н12 с помощью автосуммирования вычисляем сумму чисел B12: G12. Копируем полученный результат в ячейки Н13:1115. Таким же образом в ячейке В16 вычисляем сумму чисел В12: В15. Копируем полученную формулу в ячейки C16: G16.
• 4. В ячейках B19: G22 вычисляем стоимость (в руб.) доставки продукции от филиалов до складов. Для этого выделяем диапазон ячеек B19: G22, ставим знак равно, далее выделяем диапазон ячеек B5: G8, ставим знак умножения и выделяем диапазон ячеек B12: G15. После этого нажимаем комбинацию клавиш Shift + Ctrl + Enter.

Рис. 73. Фрагмент примера 7.3 в Excel.

Ячейки B12: G15 должны быть целыми и не отрицательными (так как количество перевозимой продукции не может быть меньше нуля и равняться дробному числу), т. е. B12: G15>=0, B12: G15 = целое; произведенная продукция должна быть полностью вывезена в склады, т. е. Н5: Н8 = Н12: Н15. В-трстьих, возможности складов нс должны превышать заявленных, т. е. B9: G9<=B16:G16.

• 6. В ячейке Н24 находим сумму чисел B12: G15 — это будет целевая функция.
• 7. Задаем команду ДАННЫЕ / Анализ / Поиск решения.
• 8. В окне Поиск решения введем данные:
  • — в поле Оптимизировать целевую ячейку укажем адрес Н24;
  • — в разделе До: выберем Минимум;
  • — в поле Изменяя ячейки переменных определим изменяемые ячейки (В12:В15);
  • — в ноле В соответствии с ограничениями, но одному добавим следующие ограничения задачи (Н5:Н8=Н12:Н15; B12: G15>=0; B9: G9<=B16:G16; В12: С15=целое). Для этого щелкнем по кнопке Добавить и в появившемся окне Добавление ограничения введем ссылку на диапазон ячеек (Н5:Н8), оператор ограничения (=) и диапазон ячеек (Н12:Н15). Для добавления следующего ограничения щелкнем кнопку Добавить и повторим процедуру добавления ограничения; после ввода последнего ограничения щелкнем кнопку ОК;
  • — в диалоговом окне Параметры поиска решения щелкнем кнопку Найти решение; в диалоговом окне Результаты поиска решения установим переключатель Сохранить найденное решение.

В результате с помощью средства Поиск решения будет найдена минимальная сумма издержек транспортировки продукции от филиалов до складов (487 у.е.).