Построение математической модели. Решение транспортной задачи

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

Фирме необходимо организовать перевозку продукции с трех складов в пять магазинов. Сведения о наличии продукции на складах, о потребности в этой продукции у магазинов и о стоимости перевозки единицы продукции с каждого склада во все магазины приведены в табл. 28.

Таблица 28

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

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

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

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

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

Обозначим:

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

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

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

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

Х_ij ³ 0; C_ij ³ 0. (1)

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

(2)

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

(3)

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

(4)

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

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

, (5)

где – суммарное количество продукции на складах,

(при этом S_i = – количество продукции на одном складе, i = 1, 2, 3);

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

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

=60,

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

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

ЭТ приведена в табл. 29 – режим вычислений, табл.30 – режим показа формул Microsoft Office и табл. 31 в OpenOffice.org Calc.

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