2.2 Решение транспортной задачи

Фирме необходимо организовать перевозку продукции с трех складов в пять магазинов. Объемы запасов шин на складах, объемы заявок магазинов и тарифы на перевозку приведены в таблице выше.

Решение задачи включает три этапа:

1. Построение математической модели

2. Построение начального плана решения

3. Оптимизация начального плана

2.2.1 Построение математической модели

Обозначим:

Х_ij – количество продукции, отправляемой со склада i в магазин j;

С_{ij –} стоимость перевозки единицы продукции со склада i в магазин j.

Математическая модель будет состоять из ряда ограничений:

а) исходя из физического смысла задачи (количество и стоимость продукции не могут быть отрицательными величинами)

Х_ij ≥ 0; С_ij ≥ 0. (1)

б ) ограничения по предложению (со складов нельзя вывести продукции больше, чем там имеется:

х₁₁ + х₁₂ + х₁₃ + х₁₄ + х₁₅ ≤ 350

х₂₁ + х₂₂ + х₂₃ + х₂₄ + х₂₅ ≤ 400 (2)

х₃₁ + х₃₂ + х₃₃ + х₃₄ + х₃₅ ≤ 400

в ) ограничения по спросу (в магазины следует завезти не меньше продукции, чем им требуется):

х₁₁ + х₂₁ + х₃₁ ≥ 200

х₁₂ + х₂₂ + х₃₂ ≥ 280

х₁₃ + х₂₃ + х₃₃ ≥ 240 (3)

х₁₄ + х₂₄ + х₃₄ ≥ 220

х₁₅ + х₂₅ + х₃₅ ≥ 210

Общая стоимость перевозок (целевая функция) равна:

(4)

Необходимо определить такие значения переменных Х_ij, которые удовлетворяют ограничениям (1), (2) и (3) и обращают в минимум целевую функцию Z (4). В такой постановке задача является транспортной задачей линейного программирования.

Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса:

(5)

Где - суммарное количество продукции на складах, (при этом - количество продукции на одном складе, i = 1,2,3); - суммарное количество продукции, требуемое в магазинах (при этом - количество продукции, которое требуется j-му магазину j=1,2,…,5).

В нашем случае

;

,

следовательно, задача с балансом.

2.2.2 Разработка эт с начальным планом решения

ЭТ приведена в Таблице 5 – режим вычислений, Таблице 6 – режим показа формул Microsoft Office.

1. Подготовим блок ячеек с исходными данными

В ячейках G1:G5 помещаем сведения о наличии продукции на складах. В ячейках В6:F6 – сведения о потребностях магазинов. В ячейках В3:F5 – данные о стоимости перевозок единицы продукции со складов в магазин.

2. Построим начальный план перевозок

Считаем, что с каждого склада в каждый магазин везут одну единицу товара (ячейки заполним В9:F11 единицами).

3. Вычислим количество перевозимой продукции

а) в ячейку I9 – введем формулу для вычисления количества продукции, вывозимой из первого склада:

=СУММ(B9:F9)

Аналогично в ячейки I10, I11 введем формулы для вычисления количества продукции, вывозимой со второго и третьего складов:

=СУММ(B10:F10); =СУММ(B11:F11).

Для начального плана перевозок все суммы равны 5.

б) в ячейку В14 введем формулу для вычисления количества продукции, которую везем в первый магазин

=СУММ(B9:B11)

Аналогично в ячейки С14:F14 введем формулы для вычисления количества продукции, которую везем во второй, третий, четвертый и пятый магазины:

C14=СУММ(C9:C11)

D14=СУММ(D9:D11)

E14=СУММ(E9:E11)

F14=СУММ(F9:F11)

4. Определим стоимость перевозок в каждый из магазинов

Для определения стоимости перевозок в первый магазин:

введем в ячейку В16 формулу:

=СУММПРОИЗВ(B3:B5;B9:B11)

В ячейке С16 вычислим стоимость перевозок во второй магазин

, т.е. введем формулу

=СУММПРОИЗВ(C3:C5;C9:C11)

Аналогично в ячейки D16:F16 введем формулы для вычисления стоимости перевозок в остальные магазины:

D16=СУММПРОИЗВ(D3:D5;D9:D11)

E16=СУММПРОИЗВ(E3:E5;E9:E11)

F16=СУММПРОИЗВ(F3:F5;F9:F11)

5. Определим общую стоимость перевозок (целевую функцию ЦФ)

(6)

Для этого введем в ячейку В18 формулу:

=СУММ(B16:F16)

Для нашего начального плана полученная стоимость равна 147 денежным единицам.

Таблица 5 – Режим вычислений

Таблица 6 – Режим показа формул