Модель транспортной задачи

ВВЕДЕНИЕ

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

В общем виде постановка транспортной задачи заключается в следующем. Необходимо составить наилучший (оптимальный) план перевозок груза от поставщиков к потребителям с учетом ограниченных ресурсов поставщиков и потребностей потребителей. При этом надо обеспечить минимум затрат на транспортировку.

В методических указаниях даются теоретические сведения, показаны на примерах алгоритмы решения задач транспортного типа, в том числе средствами табличного редактора Excel.

Методические указания предназначены для студентов и аспирантов экономических специальностей и могут быть использованы при изучении курсов «Экономико-математические методы и модели в коммерческой деятельности» и «Компьютерное моделирование в профессиональной деятельности», а также в научных исследованиях.

ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ТРАНСПОРТНОЙ ЗАДАЧИ

Рассматривается задача транспортировки единственного продукта, который производится в определенных количествах в нескольких пунктах производства. Известны потребности в этом продукте для нескольких пунктов потребления. Требуется удовлетворить эти потребности с наименьшими издержками.

Обозначения:

a_i – объем производства в пункте i, i=1,…,n;

b_j – объем потребления в пункте j, j=1,…,m;

c_ij – затраты на транспортировку единицы продукта из i в j;

x_ij – количество продукта, перевозимого из i в j.

Модель транспортной задачи

,

.

1. Замкнутая транспортная задача

Общий объем поставок равен общему объему потребления:

.

2. Открытая транспортная задача

a) - избыток продукта.

-4-

Сведение к замкнутой задаче:

Пусть b_m+1 – величина избытка продукции;

b_m+1 = ;

с_im+1 – штраф за единицу нереализованного продукта а пункте i;

y_i – количество продукта, нереализованного в пункте i;

,

b) - дефицит продукта.

,

.

Сведение к замкнутой задаче:

Пусть а_n+1 = - величина дефицита продукта;

с_n+1j – величина ущерба от неудовлетворения потребности пункта j;

y_j – количество продукта, недопоставленного в пункт j;