В. 39 Математическая модель транспортной задачи

Имеется m - складов и n - магазинов. На складах хранится некоторое количество однородной продукции.

Склад № i имеет запас продукции = a_i (i= 1,2..m)

Каждый магазин имеет потребность в продукции b_j (j=1,2,..n)

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

Задача: Определить объём перевозки из каждого склада в каждый магазин так, чтобы суммарные затраты на перевозки были min.

Пример в тетради!

Потребуем, чтобы .

Построим математическую модель.

1) (х_ij показывает сколько везем, с_ij- сколько стоит)

2) (выводим с i-го склада столько, сколько на нём имеется).

3) (привозим в j-ый магазин столько, сколько ему нужно).

4) х_ij≥0

1-4 - это транспортная задача в матричной подстановке.

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

Если выполняется условие (*), то транспортная задача называется закрытой (замкнутой).

Если исходная задача не замкнута, то имеются 2 возможности:

1) (запасы > потребностей), добавляем фиктивный магазин (свалку).

Потребности магазина: Цены перевозок на свалку = 0.

2) (потребности > запасов), вводим фиктивный склад;