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

Международный университет природы, общества

и человека «Дубна» филиал «Угреша»

 
 
 
 

Курсовая  работа по дисциплине:

 

«Математические модели принятие управленческих решений»

 

Тема: Решение  транспортной задачи.

 
 
 
 
 
 
 
 
 
 
 
 

Дисциплина: Математические модели принятие

  управленческих решений

 

      Выполнил: Студент группы                      

 

Проверил:  Соловьев Э.Д

 
 
 
 
 
 
 
 
 
 
 

2009 г.

Оглавление 

 
 
 
 

1.

2.

3.

4.

5.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

 

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

 

Задание

 

Компания «Феникс» производит светильники для офисов и квартир.

Филиалы производственных цехов и соответственно складов находятся в г. Дубна, г. Солнечногорск и г. Серпухов.

На складе в  Люберцах находятся 725 светильников, в Дзержинском - 1015 и в Лыткарино - 435.

Потребительские фирмы по оптовой продаже находятся  в Москве, Дзержинском, Кашире и Химках.

Эти фирмы готовы закупить соответственно 880, 580, 290 и 210 светильников.

Удельные затраты  на перевозку одного комплекта приведены  в таблице:

 
 
 

Необходимо  минимизировать издержки всех перевозок.

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

Определить  количество перевозимых светильников по всем маршрутам.

Количество недопоставленных светильников, или оставшихся на складах.

 
 
 
 
 
 
 
 
 
 
 
 
 

Теория 

Основные метода решения  распределительных задач, в частности  линейного 
программирования, построены на допущении, что объёмы, имеющихся в 
наличии ресурсов (Bi), требуемые объёмы (аi) и затраты (Сi,j) точно 
известны. 
 
Если общий объём наличных ресурсов (bi (i=l...m) равен общей потребности 
в них (ai(j=l...n), то имеет место сбалансированная (закрытая) 
распределительная задача: Если же (аj ( (bi, то задача называется 
несбалансированной (открытой). Если ресурсы можно разделить между 
работами, то некоторые работы можно выполнять с помощью различных 
комбинаций ресурсов. Если работы и ресурсы измеряются в единицах одной и 
той же шкалы, то такие задачи обычно называют транспортными или задачами 
разложения. Если же работы и ресурсы выражаются в различных единицах 
измерениях, то задача называется общей распределительной задачей. Таким 
образом транспортная задача является

 

Составление опорного плана. 
 
Решение транспортной задача начинается с нахождения опорного плана. Для 
этого существуют различные способы. Например, способ "северо-западного 
угла", способ минимальной стоимости по строке, способ минимальной 
стоимости по столбцу и способ минимальной стоимости таблицы. 
 
Способ "северо-западного угла". Будем заполнять таблицу перевозками 
постепенно начиная с левой верхней ячейки ( “ceвеpo-западного” угла 
таблицы ). Будем рассуждать при этом следующим образом. пункт B1 подал 
заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, 
имеющегося в пункте A1 , и запишем перевозку 18 в клетке (1,1). После 
этого заявка пункта B1 удовлетворена, а в пункте A1 осталось ещё 30 
единиц груза. Удовлетворим засчёт них заявку пункта В2, (27 единиц), 
запишем 27 в клетке (1,2); 
 
оставшиеся 3 единицы пункта а1 назначим пункту В3. В составе заявки 
пункта В3 остались неудовлетворенными 39 единиц. Из них 30 покроем за 
счет пункта А2, чем его запас будет исчерпан, и еще 9 возьмём из пункта 
Аз. Из оставшихся 18 единиц пункта Аз 12 выделим пункту В4; оставшиеся 6 
единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 
покроет его заявку. За этом распределение запасов закончено; каждый 
пункт назначения получил груз согласно своей заявки. Это выражается в 
том, что сумма перевозок в каждой строке равна соответствующему запасу, 
а в столбце — заявке. Таким образом, нами сразу же составлен клан 
перевозок, удовлетворяющий балансовым условиям. Полученное решение 
является опорным решением транспортной задачи: 
 
Составленный нами план перевозок, не является оптимальным по стоимости, 
так как при его построении мы совсем не учитывали стоимость перевозок 
Сi,j. 
 
Другой способ — способ минимальной стоимости по строке — основан на том, 
что мы распределяем продукцию от пункта Аi, не в любой из пунктов Вj, а 
в тот, к которому стоимость перевозки минимальна. Если в этом пункте 
заявка полностью удовлетворена, то мы убираем его из расчетов м находим 
минимальную стоимость перевозки из оставшихся пунктов Вj. Во всем 
остальном этот метод схож с методом "северо-западного угла". Способ 
минимальной стоимости по столбцу аналогичен предыдущему способу. Их 
отличие состоит в том, что во втором способе мы распределяем продукцию 
от пунктов Bi к пунктам Аj, по минимальной стоимости Cj.i. Опорный план, 
составленный способами минимальных стоимостей, обычно боже близок к 
оптимальному решению. Клетки таблицы, в которых стоят ненулевые 
перевозки, являются базисными. Их число должно равняться m + n - 1. 
Необходимо отметить также, что встречаются такие ситуации, когда 
количество базисных клеток меньше чем m + n - 1. В этом случае 
распределительная задача называется вырожденной. И следует в одной из 
свободных клеток поставить количество перевозок равное нулю. 
 
Составляя план по способам минимальных стоимостей в отличии от плана по 
способу "северо-западного угла" мы учитываем стоимости перевозок Сi.j, 
но все же не можем утверждать, что составленный нами план является 
оптимальным.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Решения

Распределяем  груз методом наилучших тарифов.

 

Целевая функция 

F(x)= 880*8+580*25+145*20+145*25+210*20+225*20+225*0 =

=7040+14500+2900+3625+4200+4500+0 = 36765

a1=0

a1+b2 =25 → b2=25

a1+b3=20 → b3=20

a2+b1=8 → b1=3

a2+b3=25 → a2=5

a2+b5=0 → b5=-5

a3+b4=20 → b4=15

a3+b5==0 →a3=5

 

      Оценка  оптимальности 

∆₁₁=(0+3)-10= -7

∆₁₄=(0+15)-25= -10

∆₁₅=(0+(-5))-0= -5

∆₂₂=(5+25)-30= 0

∆₂₄=(5+15)-20= 0

∆₃₁=(5+3)-15= -7

∆₃₂=(5+25)-35= -5

∆₃₃=(5+20)-30= -5