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

   В зависимости  от способа представления условий  транспортной задачи она может  быть представлена в сетевой  (схематичной) или матричной (табличной)  форме. Транспортная задача может  также решаться с ограничениями  и без ограничений. 

 

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

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

аi — величина предложения продукта в пункте i (i = 1, ..., n);

bj — величина спроса на продукт в пункте j (j = 1,..., т);

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

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

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

 

Здесь   (1) — целевая функция (минимум затрат на транспортировку продукта);

(2) — ограничения по величине предложения в каждом пункте производства;

(3) — ограничения по величине спроса в каждом пункте потребления;

(4) — условия неотрицательности объемов перевозок.

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

Общее предложение равно общему спросу:

Это необходимое и достаточное условие существования допустимого плана задачи (1)—(4).

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

а)    — излишек продукта

Способ сведения к замкнутой  задаче. Пусть bm+1 — величина избытка продукции, т.е.     - штраф за единицу продукта, не реализованного в пункте i; уi— количество продукта, не реализованного в пункте i.

Замкнутая транспортная задача имеет вид

б)    — дефицит продукта.

Способ сведения к замкнутой  задаче. Пусть аn+1 — величина дефицита продукции, т.е.    - штраф за единицу продукта, недопоставленного в пункт j; уj— количество продукта, недопоставленного в пункту.

Замкнутая транспортная задача имеет вид:

3. Транспортная  задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транспортировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.

Пусть М— большое число, например

Тогда 

В оптимальном плане {   } транспортной задачи    при ограничениях (2)—(4) xij = 0, если (i,j) Ï Е.

4. Транспортная  задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (1)—(4) вводится дополнительное ограничение: xij= vij, где vij — заданный объем перевозок.

5. Транспортная  задача с ограничениями на  пропускную способность. Если объем перевозок из пункта i в пункт j ограничен величиной wij, то в задаче (1)—(4) вводится дополнительное ограничение: xij £ wij.

6. Транспортная  задача с фиксированными доплатами. Предположим, что в открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах i = п + 1, ..., k возможно создание новых мощностей di.

Пусть переменные zi = 1, если в пункте i (i = п + 1, ..., k) вводятся мощности di и zi = 0, если в пункте i мощности не вводятся. Издержки на ввод мощностей d, в пункте i (i = n + 1, ..., k) составляют и i.

С учетом возможности создания новых мощностей транспортная задача может быть записана в следующем виде:

 

Здесь   (5) — целевая функция (минимум затрат на транспортировку и ввод мощностей);

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

   Переменными (неизвестными)  транспортной задачи являются  i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок

  .

   Так как произведение  определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид .

   Система ограничений  задачи состоит из двух групп  уравнений. Первая группа из  m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:

,   i=1,2,…,m.

   Вторая группа  из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

,   j=1, 2, … , n.

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

,                        (1)

,  i=1,2,…,m ,                         (2)

,   j=1, 2, … , n,                      (3)

,      i=1,2,,…,m,    j=1,2,…,n      (4)

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

    Такая задача  называется задачей с правильным  балансом, а ее модель – закрытой. Если же это равенство не  выполняется, то задача называется  задачей с неправильным  балансом, а ее модель – открытой.

    Математическая  формулировка транспортной задачи  такова: найти переменные задачи  ,    i=1,2,,…,m,  j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

    Математическая  модель транспортной задачи может  быть записана в векторном  виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3)

       

                                      

        .……………………………………………………

А =                                                 (6).

        ……………………………………………………

                                                    

  Сверху над каждым  столбцом матрицы указана переменная  задачи, коэффициентами при которой  являются элементы соответствующего  столбца в уравнениях системы  ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте, т.е.

Номер кординаты

       =         ;     =      .

   Обозначим через вектор ограничений (правых частей уравнений (2), (3) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:

,                             (7)

= ,                                          (8)

,      i=1,2,,…,m,    j=1,2,…,n       (9)

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3. Решение транспортной задачи по пути развоза своей продукции компании «Coca-Cola» по г.Бишкек

3.1 Описание компании  «Coca-Cola»

«Кока-Кола» (англ. Coca-Cola) — безалкогольный газированный напиток, производимый компанией The Coca-Cola Company. «Кока-Кола» была признана самым дорогим брендом в мире в 2005—2011 годах в рейтинге международного исследовательского агентства Interbrand. Сегодня данный напиток продается более чем в 200 странах мира.

Напиток «Кока-кола» был  придуман в Атланте (штат Джорджия, США) 8 мая 1886 года. Его автор —  фармацевт Джон Стит Пембертон, бывший офицер американской Армии конфедерации (есть легенда, что его придумал фермер, который продал свой рецепт Джону Ститу за 250$, о чём Джон Стит якобы сказал в одном из своих интервью). Название для нового напитка придумал бухгалтер Пембертона Фрэнк Робинсон, который также, владея каллиграфией, написал слова «Coca-Cola» красивыми фигурными буквами, до сих пор являющимися логотипом напитка.

Основные ингредиенты  кока-колы были таковы: три части  листьев коки (из этих же листьев  в1859 году Альберт Ниман (Albert Niemann) выделил особый компонент (наркотик) и назвал его кокаин) на одну часть орехов тропического дерева колы. Получившийся напиток был запатентован как лекарственное средство «от любых нервных расстройств» и начал продаваться через автомат в крупнейшей городской аптеке Джекоба в Атланте. Пембертон также утверждал, что кока-кола исцеляет от импотенции и что на неё можно перейти тем, кто пристрастился к морфию (к морфию, кстати, был неравнодушен и сам Пембертон). Здесь нужно отметить, что кокаин тогда не являлся запрещённым веществом, и о его вреде для здоровья ещё ничего не знали (к примеру, в повести «Знак четырёх» Артура Конан Дойля Шерлок Холмс употреблял кокаин в минуты бездействия, так тягостно переносимые им). Поэтому кокаин свободно продавался, и его часто добавляли для удовольствия и тонуса в напитки взамен спирта — Кока-Кола в этом не была новинкой.

Уже в конце XX века под давлением конкурентов, выпускавших напитки без кофеина и сахара, компания «Кока-Кола» начала выпускать напитки: «Classic Coke», «New Coke», «Cherry Coke», «Tab», «Caffeine-Free New Coke», «Caffeine-Free Diet Coke» и «Caffeine-Free Tab».

Кока-Кола Бишкек Боттлерс (ККББ), созданная в 1995 году, запущенно в производство 14  мая 1996 года. Основной деятельностью компании является производство, продажа и дистрибуция газированных и негазированных прохладительных напитков “The Coca-Cola Company” (TCCCККК) в Кыргызстане- “Coca-Cola”, “Fanta”, “Sprite”, воды “BonAqua” “BonAqua” still и соки “Piko”.

Уже более пятнадцати лет, ККББ постоянно развивает свой бизнес в Кыргызстане. Успешный бизнес компании выгоден как для экономики Кыргызстана, так и для общества в целом. Во-первых, это обеспечение кыргызстанцев продукцией высочайшего качества, а так же предоставление рабочих мест. Во-вторых, компания уже 15 лет на рынке Кыргызстана и за это время в государственную казну только в виде налогов отчислила 33 миллиона долларов.

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

Завод ККББ находится в Бишкеке, который обеспечивает  и обслуживает население Кыргызстана качественной продукцией. Компания также, экспортирует продукцию в Казахстан и Таджикистан. Производственная мощность составляет 9 млн. физических единиц.

На сегодняшний день ЗАО  «Кока-Кола Бишкек Боттлерс» - одно из наиболее высокотехнологичных и хорошо оборудованных производств, предоставляющее рабочие места более чем 2860 работникам внутри компании и более 2000 человек за её пределами, благодаря развитой сети и дистрибуции.

За 15 лет работы на рынке  Кыргызстана, компания приобрела репутацию  опытного, надежного и добросовестного  партнера. Слагаемые успеха – качество продукции, гибкая ценовая политика, профессионализм сотрудников и  готовность к диалогу.

 

 

 

 

 

 

 

 

 

 

 

 

 

3.2 Решение транспортной задачи методом программирования

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

Рассмотрим реализацию алгоритма решения задачи методом ветвей и границ, взяв маршрут развоза продукции компании «Coca-Cola» по торговым центрам г. Бишкек (Rahat Palace, Bishkek Park, Plaza и Vefa center), в бизнес-центр «Москва» и в 12 микрорайон из ее исходной точки – местонахождения производства ее продукции (ул. Лущихина-Тимура Фрунзе).

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

Необходимо найти оптимальный  маршрут коммивояжера в графе, представленном на рисунке:

 

 

 

 

 

Составим матрицу длин кратчайших дуг между каждой парой вершин , в случае, если дуги между вершиной i и j не существует, элементу матрицы присваивается значение ∞.

Матрица :

i j		1		2		3		4		5		6		7
1		M		7		∞		∞		3		14		∞
2		7		M		4		∞		∞		∞		∞
3		∞		4		M		6		5		∞		∞
4		∞		∞		6		M		7		8		∞
5		3		∞		5		7		M		5		∞
6		14		∞		∞		8		5		M		6
7		∞		∞		∞		∞		∞		6		M