Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ёкономико-математическа€ модель транспортной задачи




¬ажным частным случаем задачи линейного программировани€ €вл€етс€ так называема€ транспортна€ задача.

 лассическа€ транспортна€ задача Ц задача о наиболее экономном плане перевозок однородного продукта (или взаимозамен€емых продуктов) из пунктов производства в пункты потреблени€.

Ёкономико-математическа€ модель транспортной задачи в общем виде может быть сформулирована следующим образом:

»меетс€ m пунктов производства однородного продукта и n пунктов потреблени€. ƒл€ каждого пункта производства i задан объем производства јi, дл€ каждого пункта потреблени€ j известна потребность (спрос) ¬j (в тех же единицах измерени€). »звестны издержки сij, св€занные с перевозкой единицы продукта из пункта i в пункт j.

“ребуетс€ составить план перевозок, обеспечивающий наиболее экономным путем (т.е. при наименьших транспортных издержках) удовлетворение всех пунктов потреблени€ за счет реализации всего продукта, произведенного пунктами производства. ѕри этом предполагаетс€, что суммарный спрос (¬=åj¬j) равен суммарному объему производства (ј=åiјi). “акие задачи называютс€ закрытыми транспортными задачами.

„то такое план перевозок? ѕлан перевозок определ€ет:

—колько единиц продукта перевозитс€ от каждого пункта производства к каждому пункту потреблени€, т.е. план представл€етс€ набором чисел х ij (всего таких чисел m´n), где х ij показывает, сколько единиц продукта должно быть перевезено от i-го производител€ j-му потребителю. ќтметим также, что в термин Ђтранспортные издержкиї (сij) не всегда вкладываетс€ строгий экономический смысл. Ёто могут быть рассто€ни€, тарифы, врем€, расход топлива и т.п. ¬ каждой конкретной задаче оговариваетс€ конкретный смысл коэффициентов с ij.

—истема ограничений примет вид

= јi (i=1,2,Е,m), (2.3.1)

= ¬j (j=1,2,Еn). (2.3.2)

—истема (2.3.1) включает в себ€ уравнени€ баланса по поставщикам, а система (2.3.2) Ц по потребител€м. —уммарные транспортные издержки выражаютс€ в виде следующей линейной функции, которую необходимо минимизировать

F = à min (2.3.3)

ћатематическа€ модель транспортной задачи в общей постановке будет следующей: на множестве неотрицательных решений системы ограничений (2.3.1), (2.3.2) (мы будем называть такие решени€ допустимые) найти такое решение ’=(х 11, х 12,Е, х ij,Е, х mn), при котором значение целевой функции (2.3.3) минимально. ”слови€ транспортной задачи весьма удобно представл€ть в табличной форме.

“аблица 2.3.1

ѕункт произ- водства i ќбъем произ- водства јi ѕункты потреблени€ j и их спрос ¬j
    Е n
¬1 ¬2 Е ¬n
    ј1   с11 х 11 с12   х 12 Е с1n   х 1n
      ј2   с21   х 21 с22   х 22     Е с2n   х 2n
Е Е Е Е Е Е
  m   јm сm1   х m1 сm2   х m2 Е сmn   х mn

¬ левом верхнем углу произвольной клетки (i,j) (i Ц номер строки, jЦномер столбца) стоит показатель транспортных затратсij, в правом нижнем Ц значени€ переменных х ij(план перевозок). Ћюбое решение ’=(х 11, х 12,Е, х ij,Е, х mn) системы ограничений (2.3.1) Ц (2.3.2) назовем распределением поставок.

ѕростой модификацией данной модели €вл€етс€ модель процесса назначени€. –ечь идЄт о назначении m различных специалистов на n мест работы при условии, что каждую работу должен выполн€ть лишь один специалист, и каждый специалист должен выполн€ть лишь одну работу. ѕриоритетна€ возможность i-го специалиста на получение j-й работы оцениваетс€ коэффициентами cij матрицы —. ѕри моделировании таких процессов x ij вводитс€ как булевска€ переменна€:

x ij=

ѕравые части всех ограничений в этом случае равны 1.

јi =1 (i=1,2,Е,m), ¬j =1 (j=1,2,Еn).

ѕоказательно, что, в отличие от решени€ транспортной задачи, попытка применени€ на производстве оптимального решени€ задачи о назначении привела к неожиданным социальным последстви€м. “ак бригады, где регул€рно примен€лась подобна€ практика, мес€ца через три обычно разваливались, рабочие начинали оттуда бежать. ƒело в том, что перечень работ изо дн€ в день практически оставалс€ неизменным, следовательно, и оптимальное решение также не мен€лось. “аким образом, происходило закрепление определеeнных видов работ за конкретными рабочими, что приводило к существенной дифференциации в заработках и затрудн€ло желающим повысить свою квалификацию. ѕоэтому более "опытные" бригадиры, отслежива€ потребности членов бригады, самосто€тельно подбирали некоторым рабочим соответствующие работы, а дл€ остальных рабочих и оставшихс€ работ решалась уже задача о назначении. ѕолучавшеес€ решение естественно не было оптимальным, но зато в бригаде царил мир и пор€док. ќптимальное же решение использовалось исключительно во врем€ авралов и коммунистических субботников, т.е. в тех случа€х, когда требовалось показать наивысшую производительность труда.

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

ћногими математиками, начина€ с ’алмоша, предлагалось использовать задачу о назначени€х дл€ составлени€ супружеских пар (MarriageProblem), тракту€ коэффициенты cij как "меру счасть€" будущего союза. ѕравда, постановка задачи выгл€дела несколько искусственной, так как каждый раз приходилось фантазировать, чтобы оправдать необходимость массовых бракосочетаний. ќднако реальна€ жизнь оказалась богаче подобных фантазий и основатель "÷еркви унификации" кореец —он ћьюонг ћун (он же ћун —он ћен или просто ћун) уже около п€тидес€ти лет каждый год решает подобную задачу дл€ тыс€ч своих последователей.

–ассмотрим простейший числовой пример транспортной задачи (таб. 2.3.2).

«десь параметры задачи принимают следующие значени€:

с11 =2, с12 =1, с13 =5, с21 =3, с22 =4, с23 =3, с31 =4, с32 =6, с33=6;

ј1 =50, ј2 =60, ј3 =70, ¬1 =40, ¬2 =85, ¬3=55.

“аблица 2.3.2

       
  2 х 11 1 х 12 5 х 13
  3 х 21 4 х 22 х 23
  4 х 31 х 32 6 х 33

—оставим систему уравнений дл€ этого примера.

„тобы объем производства каждого поставщика был реализован, необходимо выполнение баланса по каждой строке таблицы, т.е.

х 11 + х 12 + х 13 =50

х 21 + х 22 + х 23 = 60 (2.3.4)

х 31 + х 32 + х 33= 70

јналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнени€ баланса выписываем дл€ каждого столбца таблицы:

х 11 + х 21 + х 31 = 40

х 12 + х 22 + х 32 = 85 (2.3.5)

х 13 + х 23 + х 33= 55

—уммарные транспортные затраты F ( целева€ функци€ ) выражаютс€ через издержки и поставки следующим образом:

F = 2 х 11 + х 12 + 5 х 13 + 3 х 21 +4 х 22 + 3 х 23 +4 х 31 + 6 х 32 + 6 х 33.

¬ этом примере шесть уравнений и дев€ть переменных, система (2.3.4)Ц(2.3.5) имеет бесчисленное множество решений (допустимых поставок). ¬от одно из них:

“аблица 2.3.3

       
  2 1 5
  3 4  
  4 15 6

—уммарные транспортные затраты дл€ данного распределени€:

F = 2´40 +1´10 + 5´0 + 3´0 +4´60 + 3´0+4´0 + 6´15 + 6´55=750.

¬сего в этом примере около 3600 только целочисленных решений, а если допустить дробность Ц то бесконечное множество. ¬се допустимые решени€ удовлетвор€ют системе ограничений, но отличаютс€ друг от друга величиной суммарных транспортных издержек.

¬от еще одна допустима€ поставка:

“аблица 2.3.4

       
  2 1 5
  3 4  
  4 35 6

—уммарные транспортные затраты дл€ данного распределени€:

F = 1´50 + 3´40 +3´20 + 6´35 + 6´35=650.

Ќаша задача научитьс€ находить оптимальное решение, т.е. такое, дл€ которого целева€ функци€ имеет наименьшее значение.

»сходный опорный план.

ѕервым шагом при решении транспортной задачи €вл€етс€ получение допустимого решени€, которое называют исходный опорный план. »сходный план можно легко получить, использу€ простой алгоритм, разработанный ƒанцигом и названный „арнсом и  упером Управилом северо-западного углаФ, хот€ исходный план, полученный этим способом, как правило, весьма далек от оптимального.

Уѕравило северо-западного углаФ формулируетс€ следующим образом:

1. Ќачать с северо-западного угла исходной таблицы Ц клетки (1,1), куда дать максимально возможную поставку:

х 11 =miníј11ý.

2. —ледующую максимально возможную поставку дать либо в клетку (1,2), либо в клетку (2,1), в зависимости от результата первого шага.

3. ѕродолжить этот процесс шаг за шагом от северо-западного до юго-восточного угла таблицы.

“аким образом, в нашем примере (см. табл. 2.3.3) процесс определени€ исходного плана происходит следующим образом:

¬ клетку (1,1) даем максимально возможную поставку:

х 11 =miní50,40ý=40.

ѕосле этого спрос 1-го потребител€ будет полностью удовлетворен, в результате чего первый столбец таблицы выпадает из последующего рассмотрени€. ѕереходим к клетке (1,2) и даем в нее максимально возможное значение. ”читыва€, что 1-й поставщик уже отдал 40 единиц своей продукции и у него осталось только 50 Ц 40 = 10 единиц, получим х 12 =miní10,85ý=10. ѕосле этого объемы 1-го производител€ полностью реализованы и из рассмотрени€ выпадает перва€ строка таблицы. ¬ оставшейс€ таблице снова находим Ђсеверо-западный уголї и т.д. ¬ результате получаем исходное распределение поставок (см. табл. 2.3.3).

„исло заполненных клеток в полученном распределении оказалось равным m+nЦ1=3+3Ц1 = 5. Ёто не случайно. ƒействительно, на каждом шаге (кроме последнего) из рассмотрени€ выпадали либо строка, либо столбец, а на последнем шаге и столбец и строка.

ѕоэтому число заполненных клеток на единицу меньше, чем сумма числа строк и столбцов, т.е. равно m+nЦ1. —праведлива теорема (которую мы примем без доказательств) утверждающа€, что в оптимальном решении число заполненных клеток (т.е. основных, так называемых базисных переменных) должно быть равно m+nЦ1.

—ущественный недостаток метода Усеверо-западного углаФ состоит в том, что он построен без учета значений транспортных издержек. ћожно модифицировать данный метод, избавившись от этого недостатка: на каждом шаге максимально возможную поставку следует давать не в Усеверо-западнуюФ клетку оставшейс€ таблицы, а в клетку с наименьшим значением транспортных издержек. ѕри этом распределение поставок оказываетс€, вообще говор€, ближе к оптимуму, чем распределение, полученное методом Усеверо-западного углаФ. “акой метод получени€ исходного плана называетс€ методом наименьших затрат. »сходный план, полученный данным методом, приведен в табл. 2.3.4.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-09-20; ћы поможем в написании ваших работ!; просмотров: 4190 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—ложнее всего начать действовать, все остальное зависит только от упорства. © јмели€ Ёрхарт
==> читать все изречени€...

1850 - | 1746 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.021 с.