Транспортна задача

При намиране на решение транспортен проблемметод диференциални анюитетипърво по най-добрия начинчаст от товара се разпределя между пунктовете на местоназначение (т.нар. условно оптимално разпределение) и в следващите итерации постепенно намалете общото количество неразпределени доставки. Първоначалната опция за разпределение на натоварването се определя, както следва. Във всяка колона от таблицата с данни за транспортната задача се намира най-ниската тарифа. Намерените числа се ограждат в кръгове, а клетките, съдържащи посочените числа, се попълват. В тях са записани максимално възможните числа. В резултат на това се получава определено разпределение на доставките на товари по дестинации. Това разпределение обикновено не удовлетворява ограниченията на първоначалния транспортен проблем. Следователно следващите стъпки трябва да бъдат постепенно намаляване на доставките на неразпределени товари, така че общите разходи за транспортиране да останат минимални. За да направите това, се определят излишни и недостатъчни редове.

Редовете, съответстващи на доставчици, чийто инвентар е напълно разпределен и чиито дестинации, свързани с тези клиенти, не са удовлетворени от планираните доставчици, се считат за недостатъчни. Тези линии понякога се наричат ​​също отрицателни линии. Линии, които не са напълно изчерпани, се считат за излишни. Понякога те се наричат ​​и положителни.

След като се определят излишните и недостатъчните редове, за всяка от колоните се намират разликите между числото в кръга и най-близката тарифа, записана в излишния ред. Ако числото в кръга е в положителна линия, тогава разликата не се определя. Сред получените числа намерете най-малкото. Това число се нарича междинен анюитет. След определяне на междинния анюитет се преминава към нова таблица. Тази таблица се получава от предишната таблица чрез добавяне на междинен наем към съответните тарифи в отрицателни редове. Останалите елементи остават същите. В този случай всички клетки на новата таблица се считат за свободни. След изграждането на нова таблица клетките й започват да се попълват. Сега броят на запълнените клетки е с една повече от предишния етап. Тази допълнителна клетка е в колоната, в която е записан междинният анюитет. Всички останали клетки са разположени по една във всяка от колоните и съдържат най-малките числа за дадена колона, оградени в кръгчета. Оградени в кръгчета са две еднакви числа в колоната, в която е записан междинният анюитет в предходната таблица.

Тъй като в новата таблица броят на клетките за попълване е по-голям от броя на колоните, при попълване на клетките трябва да използвате специално правило, което е следното. Изберете определена колона (ред), в която има една клетка с отбелязано кръгче в нея. Тази клетка се попълва и тази колона (ред) се изключва от разглеждане. След това вземете определен ред (колона), в който има една клетка с поставен кръг. Тази клетка се попълва и се изключва от разглеждане. тази линия(колона). Продължавайки така, след краен брой стъпки се запълват всички клетки, в които са поставени кръгчетата с оградените числа. Ако освен това е възможно да се разпредели целият наличен товар в пунктовете на отправяне между пунктовете на местоназначение, тогава получаваме оптимален плантранспортна задача. Ако не се получи оптималният план, те преминават към нова маса. За да направите това, намерете излишни и недостатъчни линии, междинен наем и изградете на тази основа нова маса. В този случай могат да възникнат някои трудности при определяне на знака на низ, когато неговият неразпределен остатък е нула. В този случай редът се счита за положителен, при условие че втората запълнена клетка, разположена в колоната, свързана с този ред от друга запълнена клетка, се намира в положителния ред.

Метод на диференциалния анюитет

За разлика от метода на потенциалите, за който първо е изграден референтен план, а след това е последователно усъвършенстван, при решаване на проблема с помощта на метода на диференциалните ренти, част от продукцията веднага се разпределя между потребителите по най-добрия възможен начин и в последващи итерации, общото количество неразпределени доставки постепенно намалява.

За да се определи решението на транспортния проблем с помощта на метода на диференциалната рента, се използва следният алгоритъм:

1. Във всяка колона определете минималната тарифа и маркирайте съответната клетка.

2. Избраните клетки се попълват с максимално възможните числа.

3. Защото в общия случай това разпределение не удовлетворява всички потребители; за да се намали количеството на незадоволените нужди в следващите стъпки, е необходимо да се оценят доставчиците.

ДЕФИНИЦИЯ 6. Редовете, съответстващи на доставчици, чийто инвентар е изчерпан и чиито разпределени нужди на клиенти не са удовлетворени, са отрицателни.

ДЕФИНИЦИЯ 7.Редовете, съответстващи на доставчици, чиито запаси не са напълно изчерпани, са положителни.

ДЕФИНИЦИЯ 8.Редовете, съответстващи на доставчици, чийто инвентар е изчерпан и чиито разпределени нужди на клиентите са удовлетворени, се оценяват с нула. Освен това, ако втората запълнена клетка, стояща в колона, свързана с този ред от друга запълнена клетка, се намира в положителен ред, този ред с нулев резултат се счита за положителен. Иначе - негативно.

4. За всяка колона, която има маркирана тарифа в отрицателния ред, намерете разликите между маркираната тарифа и най-близката тарифа в положителния ред.

5. Сред получените разлики се определя минималната. Това число се нарича междинен анюитет.

6. Изгражда се нова таблица, в която тарифите в положителните редове се пренаписват без изменения, а тарифите в отрицателните редове се увеличават с размера на междинния наем.

7. Отидете на стъпка 1.

КОМЕНТАР:а) ако има повече от една избрана клетка в ред или колона, тогава попълнете първо тези избрани клетки, които са единствените в колоната или реда;

б) ако е възможно да се разпределят всички доставки, тогава се получава оптимален план за транспортния проблем.

Допълнителни ограничения на транспортния проблем

Забранени маршрути.

Ако по някаква причина е невъзможно да се доставят продукти от точка A i до точка B j, приемете тарифа за този маршрут с произволно голяма стойност M, с ij = M, и решете проблема по обичайния начин.

Задължителни доставки.

а) Ако е необходимо да се транспортира определено количество продукт d ij от точка A i до точка B j, съответната клетка се попълва незабавно с числото d ij и след това проблемът се решава, като се счита, че запълнената клетка е свободна, но с тарифа, с ij = M, равно на Very Голям брой, а запасите и потребностите се намаляват със сумата d ij.

b) Ако е необходимо транспортиране от точка A i до точка B j не по-малко определена сумапродукти d ij , след това вземете предвид резервите и нуждите трябва да бъдат по-малки с количеството d ij , това количество d ij се счита за транспортирано по маршрута A i B j и след това решете проблема по обичайния начин.

в) Ако е необходимо да се транспортира от точка A i до точка B j не повече от определено количество продукт d ij, се въвежда допълнителна дестинация с потребност, равна на (- d ij), необходимостта от точка B j е направени равни на d ij. Тарифите за превоз до допълнителна дестинация са равни на тарифите от позиция B j, с изключение на i-тия ред, тарифата в който ще бъде равна на произволно голям брой M. Те решават проблема по обичайния начин и при писане на отговора комбинират основния и допълнителния потребител (добавете съдържанието на колоните) .

Ако при определяне на оптималния план за транспортен проблем, използвайки потенциалния метод, първо е намерен някакъв основен план и след това той е последователно подобрен, тогава при намиране на решение на транспортен проблем, използвайки метода на диференциалните ренти, първата част от товарът се разпределя между дестинациите по възможно най-добрия начин (т.нар. условно оптимално разпределение) и в следващите итерации общото количество неразпределени доставки постепенно се намалява. Първоначалната опция за разпределение на натоварването се определя, както следва. Във всяка от колоните на таблицата с данни на транспортната задача се намира минималната тарифа. Намерените числа се ограждат в кръгове, а клетките, съдържащи посочените числа, се попълват. В тях са записани максимално възможните числа. В резултат на това се получава определено разпределение на доставките на товари по дестинации. Това разпределение обикновено не удовлетворява ограниченията на първоначалния транспортен проблем. Следователно следващите стъпки трябва да бъдат постепенно намаляване на доставките на неразпределени товари, така че общите разходи за транспортиране да останат минимални. За да направите това, първо определете излишните и недостатъчните редове.

Редици, които съответстват на доставчици, чийто инвентар е напълно разпределен и чието търсене от дестинациите, свързани с планираните доставки на тези клиенти, не са удовлетворени, се считат за недостатъчни. Тези линии понякога се наричат ​​също отрицателни линии. Линии, които не са напълно изчерпани, се считат за излишни. Понякога те се наричат ​​и положителни.

След като се определят излишните и недостатъчните редове, за всяка от колоните се намират разликите между числото в кръга и най-близката тарифа, записана в излишния ред. Ако числото в кръга е в положителна линия, тогава разликата не се определя. Сред получените числа намерете най-малкото. Това число се нарича междинен анюитет . След определяне на междинния анюитет се преминава към нова таблица. Тази таблица се получава от предишната таблица чрез добавяне на междинен наем към съответните тарифи в отрицателни редове. Останалите елементи остават същите. В този случай всички клетки на новата таблица се считат за свободни. След изграждането на нова таблица клетките й започват да се попълват. Сега броят на запълнените клетки е с една повече от предишния етап. Тази допълнителна клетка е в колоната, в която е записан междинният анюитет. Всички останали клетки са разположени по една във всяка от колоните и съдържат най-малките числа за дадена колона, оградени в кръгчета. Оградени в кръгчета са две еднакви числа в колоната, в която е записан междинният анюитет в предходната таблица.

Тъй като в новата таблица броят на клетките за попълване е по-голям от броя на колоните, при попълване на клетките трябва да използвате специално правило, което е следното. Изберете определена колона (ред), в която има една клетка с поставен кръг. Тази клетка се попълва и тази колона (ред) се изключва от разглеждане. След това вземете определен ред (колона), в който има една клетка с поставен кръг. Тази клетка се попълва и този ред (колона) се изключва от разглеждане. Продължавайки така, след краен брой стъпки се запълват всички клетки, в които са поставени кръгчетата с оградените числа. Ако освен това е възможно да се разпредели целият наличен в пунктовете на отправяне товар между пунктовете на местоназначение, тогава се получава оптимален план за транспортната задача. Ако не се получи оптималният план, те преминават към нова маса. За да направите това, намерете излишни и недостатъчни редове, междинен наем и изградете нова таблица въз основа на това. В този случай могат да възникнат някои трудности при определяне на знака на низ, когато неговият неразпределен остатък е нула. В този случай редът се счита за положителен, при условие че втората запълнена клетка, разположена в колоната, свързана с този ред от друга запълнена клетка, се намира в положителния ред.

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

Описаният по-горе метод за решаване на транспортния проблем има по-прост логическа схемаизчисления от възможния метод, обсъден по-горе. Ето защо в повечето случаи за намиране на решения на конкретни транспортни проблеми с помощта на компютър се използва методът на диференциалните наеми.

Пример (4):

За транспортния проблем, чиито първоначални данни са дадени в таблица 11, намерете оптималния план, като използвате метода на диференциалните наеми.

Решение. Нека преминем от таблица 11 към таблица 12, като добавим една допълнителна колона, за да посочим излишъка и дефицита по ред и един ред, за да запишем съответните разлики.

Таблица 10.

Отправни точки	Дестинации
потребности

Таблица 11.

Отправни точки	Дестинации						недостатък излишък (
потребности
Разлика

Във всяка от колоните на таблица 12 намираме минималните тарифи и ги ограждаме. Попълнете клетките, съдържащи посочените числа. За да направите това, напишете максимално допустимото число във всяка клетка. Например в клетката, разположена в пресечната точка на реда и колоната, записваме числото 120. В тази клетка не може да се постави по-голямо число, тъй като в този случай нуждите на местоназначението ще бъдат надвишени.

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

След получаване на условно оптимален план определяме излишните и недостатъчните линии. Тук линията е недостатъчна , тъй като резервите на отправната точка са напълно използвани, а нуждите на дестинацията са частично задоволени. Количеството на дефицита е 80 единици.

струни И са излишни, тъй като запасите в произхода И не е напълно разпространена. В този случай количеството излишък на линията е равна на 60 единици, а линията е равна на единици Общата сума на излишъка съвпада с общата сума на недостига, равна на.

След като определим излишните и недостатъчните редове за всяка от колоните, намираме разликите между минималните тарифи, записани в излишните редове и тарифите в попълнените клетки. IN в такъв случайтези разлики са съответно 5, 4, 2, 1 (Таблица 11). Разликата е недефинирана за колоната, тъй като ограденото число в тази колона е в положителния ред. В колона числото в кръга е равно, а в излишните редове в клетките на дадена колона най-малкото число е числото. Следователно разликата за тази колона е равна на. По подобен начин намираме разликите за други колони: за; За; За. .

Избираме най-малката от откритите разлики, която е междинният наем. В този случай междинният наем е равен на и е в графата . След като намерихме междинния наем, преминаваме към таблица 11.

В тази таблица в редове и (които са излишни) пренаписваме съответните тарифи от ред Таблица 10. Елементите на линията (която беше недостатъчна) се получават чрез добавяне към съответните тарифи, намиращи се в таблицата на линията. 10, междинен анюитет, т.е.

В табл 11, броят на запълнените клетки се увеличава с една. Това се дължи на факта, че броят на минималните тарифи във всяка от колоните на тази таблица се увеличи с един, а именно колоната вече има два минимални елемента. Ограждаме тези числа в кръгове; клетките, в които стоят, трябва да бъдат запълнени. Също така е необходимо да попълните клетките, съдържащи най-ниските тарифи за други колони. Това са клетките на таблицата. 11, в който в кръгчета са оградени съответните тарифи.

Таблица 11.

Отправни точки	Дестинации						недостатък излишък (
потребности
Разлика

След като се определят посочените клетки, установяваме последователността на попълването им. За целта намираме колони (редове), в които има само една клетка за попълване. След като идентифицираме и попълним определена клетка, изключваме съответната колона (ред) от разглеждане и преминаваме към попълване на следващата клетка. В този случай попълваме клетките в следната последователност. Първо запълваме клетките ,,,, тъй като те са единствените клетки за попълване на колоните След като попълните посочените клетки, попълнете клетката, тъй като тя е единствената за попълване на реда . След като попълнихме тази клетка (Таблица 2.16), ние изключваме линията от разглеждане . След това в колоната остава само една клетка за попълване. Това е клетка , които попълваме. След попълване на клетките задаваме излишни и недостатъчни редове (Таблица 11). Както се вижда от таблица 11, все още има неразпределен остатък. Следователно е получен условно оптимален план за проблема и трябва да преминем към нова таблица. За да направите това, за всяка от колоните намираме разликите между числото, изписано в кръга на тази колона, и най-малкото число по отношение на нея, разположено в излишните редове (Таблица 11). Сред тези разлики най-малката е . Това е междинен наем. Нека да преминем към нова таблица (Таблица 12).

Ако при определяне на оптималния план за транспортен проблем с помощта на потенциалния метод първо беше намерен някакъв основен план и след това той беше последователно подобрен, тогава при намиране на решение на транспортен проблем с помощта на метода на диференциалните наеми, част от товара първо се разпределя между дестинациите по възможно най-добрия начин (т.нар условно оптимално разпределение) и в следващите итерации постепенно намалете общото количество неразпределени доставки. Първоначалната опция за разпределение на натоварването се определя, както следва. Във всяка от колоните на таблицата с данни на транспортната задача се намира минималната тарифа. Намерените числа се ограждат в кръгове, а клетките, съдържащи посочените числа, се попълват. В тях са записани максимално възможните числа. В резултат на това се получава определено разпределение на доставките на товари по дестинации. Това разпределение обикновено не удовлетворява ограниченията на първоначалния транспортен проблем. Следователно следващите стъпки трябва да бъдат постепенно намаляване на доставките на неразпределени товари, така че общите разходи за транспортиране да останат минимални. За да направите това, първо определете излишните и недостатъчните редове.

Редици, които съответстват на доставчици, чийто инвентар е напълно разпределен и чието търсене от дестинациите, свързани с планираните доставки на тези клиенти, не са удовлетворени, се считат за недостатъчни. Тези линии понякога се наричат ​​също отрицателни линии. Линии, които не са напълно изчерпани, се считат за излишни. Понякога те се наричат ​​и положителни.

След като се определят излишните и недостатъчните редове, за всяка от колоните се намират разликите между числото в кръга и най-близката тарифа, записана в излишния ред. Ако числото в кръга е в положителна линия, тогава разликата не се определя. Сред получените числа намерете най-малкото. Този номер се нарича междинен наем. След определяне на междинния анюитет се преминава към нова таблица. Тази таблица се получава от предишната таблица чрез добавяне на междинен наем към съответните тарифи в отрицателни редове. Останалите елементи остават същите. В този случай всички клетки на новата таблица се считат за свободни. След изграждането на нова таблица клетките й започват да се попълват. Сега броят на запълнените клетки е с една повече от предишния етап. Тази допълнителна клетка е в колоната, в която е записан междинният анюитет. Всички останали клетки са разположени по една във всяка от колоните и съдържат най-малките числа за дадена колона, оградени в кръгчета. Оградени в кръгчета са две еднакви числа в колоната, в която е записан междинният анюитет в предходната таблица.

Тъй като в новата таблица броят на клетките за попълване е по-голям от броя на колоните, при попълване на клетките трябва да използвате специално правило, което е следното. Изберете определена колона (ред), в която има една клетка с поставен кръг. Тази клетка се попълва и тази колона (ред) се изключва от разглеждане. След това вземете определен ред (колона), в който има една клетка с поставен кръг. Тази клетка се попълва и този ред (колона) се изключва от разглеждане. Продължавайки така, след краен брой стъпки се запълват всички клетки, в които са поставени кръгчетата с оградените числа. Ако освен това е възможно да се разпредели целият наличен в пунктовете на отправяне товар между пунктовете на местоназначение, тогава се получава оптимален план за транспортната задача. Ако не се получи оптималният план, те преминават към нова маса. За да направите това, намерете излишни и недостатъчни редове, междинен наем и изградете нова таблица въз основа на това. В този случай могат да възникнат някои трудности при определяне на знака на низ, когато неговият неразпределен остатък е нула. В този случай редът се счита за положителен, при условие че втората запълнена клетка, разположена в колоната, свързана с този ред от друга запълнена клетка, се намира в положителния ред.

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

Методът за решаване на транспортния проблем, описан по-горе, има по-проста логическа изчислителна схема от потенциалния метод, обсъден по-горе. Ето защо в повечето случаи за намиране на решения на конкретни транспортни проблеми с помощта на компютър се използва методът на диференциалните наеми.

5.6 Определяне на оптимален план за транспортни проблеми, които имат някои усложнения при тяхното формулиране.

Когато се намира решение на редица специфични транспортни проблеми, често е необходимо да се вземат предвид допълнителни ограничения, които не са били срещани по-горе при разглеждането прости опциитези задачи. Нека се спрем по-подробно на някои възможни усложнения при формулирането на транспортни проблеми.

1. При някои реални условия на превоз на товари от определена точка на тръгване , до вашата дестинация , не може да се приложи. За да се определят оптималните планове за подобни проблеми, се приема, че тарифата за транспортиране на единица товар от точка до точка , е произволно голям М,и при това условие известни методинамери решение на нов транспортен проблем. При това предположение възможността за транспортиране на товари от точка до точка се изключва при оптималния план на транспортната задача. . Този подход за намиране на решение на транспортен проблем се нарича забрана за превоз или блокиране съответната клетка в таблицата с данни на задачите.

2. При определени транспортни задачи допълнително условие е да се осигури транспортирането на определено количество товари по съответните маршрути. Нека, например, от точката на заминаване до точката на местоназначение е необходимо да се прехвърлят единици товар. След това посоченият номер се записва в клетката на таблицата с данни на транспортната задача, разположена в пресечната точка на реда и колоната, и в бъдеще тази клетка се счита за свободна с произволно голяма транспортна тарифа М.За така получената нова транспортна задача се намира оптимален план, който определя оптималния план първоначален проблем.

3. Понякога е необходимо да се намери решение на транспортен проблем, при който поне определено количество товар трябва да бъде доставено от точката на отпътуване до местоназначението. За да се определи оптималният план за такъв проблем, се счита, че запасите на артикула и нуждите на артикула са по-малки от действителните по единици. След това се намира оптималният план за новия транспортен проблем, въз основа на който се определя решението на първоначалния проблем.

4. При някои транспортни проблеми е необходимо да се намери оптималният план за транспортиране, при условие че от точката на заминаване до местоназначението се транспортират не повече от единици товари, т.е.

Формулираният проблем може да се реши по следния начин. В таблицата с първоначални данни за задачата за всяко ограничение (1) се предоставя допълнителна колона, т.е. въвежда се допълнителна дестинация. IN тази колоназапишете същите тарифи като в колоната, с изключение на тарифата, намираща се на ред. В допълнителната колона в този ред тарифата се счита за равна на произволно голямо число. В този случай нуждите на точката се считат за равни, а нуждите на нововъведената дестинация се считат за равни. Решението на възникналия транспортен проблем може да се намери по метода на потенциалите, като по този начин ще се определи оптималният план или ще се установи неразрешимостта на първоначалния проблем. Имайте предвид, че първоначалният транспортен проблем е разрешим само ако има поне един референтен план за него.

Горният проблем може да бъде решен по този начин. Като се вземе предвид ограничението (1), референтният план се изгражда, като се използва правилото за минимален елемент. Освен това, ако стойността, записана на тази стъпкав съответната клетка на числото се определя само от ограничение (1), тогава впоследствие само попълнената клетка се изключва от разглеждане. В други случаи отсъображенията изключват или ред, или колона (или едното, или другото).

Ако в резултат на изготвянето на план за доставка всички налични запаси от точки на отправяне са разпределени и нуждите в точките на местоназначение са задоволени, тогава се получава основен план за транспортната задача.

Ако в някой ред (и следователно в колона) има неразпределен баланс, равен на , след това се въвеждат допълнителна дестинация и допълнителна отправна точка с изисквания и доставки, равни на . В клетка, разположена в пресечната точка на колона допълнителна точкадестинация и линията на допълнителната точка на отпътуване, тарифата се счита за равна на нула. Във всички други клетки на даден ред и колона се приема, че тарифите са равни на някакво произволно голямо число М.Възникналият транспортен проблем се решава чрез потенциалния метод. След краен брой стъпки или се установява, че първоначалният проблем не съществува референтен план, или намерете неговия оптимален план. При което – оптимален план за първоначалния проблем, ако