Дәріс Транспорттық есеп сызықтық программалау есебі ретінде

Есептің жалпы қойылымы. Транспорттық есеп келесі түрде қойылады:

Берілген m пунктте сәйкесінше a₁, a₂, …, a _m бірлікке сәйкес саннан тұратын кейбір біртекті өнім өндіріледі. Бұл өнімді сәйкесінше b₁, b₂, …, b_n санын пайдаланатын тағайындалған n пунктке жеткізу керек. Өнім бірлігін өндірістің i пунктінен j тағайындалған пунктке (пайдалану) тасымалдау c_{i j} –ға тең, ал тасымалданған өнім бірлігінің сәйкес саны x_ij (i = 1, …, m; j = 1, …, n) тең.

x_ij сандарының m * n жиынтығын, яғни!!x_ij!! матрицасын тасымалдау жоспары, ал!! c_ij!! матрицасын- транспорт шығынының матрицасы деп атаймыз.

Жоспар мүмкін деп аталады, егер x_ij саны келесі шектеулерді қанағаттандырса:

x_ij > 0 (i = 1, …, m; j = 1, …, n),

x_{i 1} + x_{i 2} + … + x_{i n} = a_i (i = 1, …, m),

x_1j + x_{2 j} + … + x_{m j} = b_j (j = 1, …, n ),

мұнда алғашқы m теңдеу әрбір өндіру пунктіндегі бүкіл өндірілген өнім тасымалданатынын, ал соңғы n теңдеу пайдалану пункттері түгелдей қанағаттандырылатынын білдіреді.

Транспорт есебі мүмкін болатын жоспарлардың ішінен тиімдісін, яғни тасымалдаудың жалпы бағасы Z = c_{i j}x_{i j} ең азын іздеуден тұрады.

Егер теңдеулер жүйесі сәйкес болса, онда

=

Осылайша, шарт

=

Бұл сұраныстар қосындысы мен ұсыныстар қосындысының теңдігі шектеулер жүйесінің бірлесуі үшін қажет, ол бірлесу үшін жеткілікті болып табылады.

Осылайша, транспорттық есеп сызықтық программалау есебіне жатады және симплекс әдісімен шешіледі. Бірақ бұл есептің тәжірибелік маңызын және шектеулер спецификасын

А) шектеулер теңдеулер түрінде берілген,

Б) әрбір белгісіз екі тек теңдеуге кіреді,

В) белгісіз коэффициенттері – бірліктер,

ескере отырып, симплекс алгоритміне қарағанда біршама үлкен арнайы алгоритмдер құрылды. Олардың бірі – төменде қарастырылатын потенциалдар әдісі–Л.В. Канторовичтың жалпы әдісінің трансорт есебін шешуге бейімделуін ұсынды және Л.В. Канторови және М.К.Гавурин, олардан кейінірек Данциг ұсынды.

Венгер әдісі деп аталатын басқасы Эгервари көрсеткен және транспорт есебінің дербес жағдайын – қызмет (немесе таңдау) туралы есепті шешуге Кун ақылы жетілдірілген, одан кейін жалпы транспорт есебін шешу үшін Манкерспен бейімделген.

Транспорт есебінің ашық моделі (қор мен қажеттіліктің бұзылған балансты).

Транспорт есебінің шешілуінің қажетті және жеткілікті шарты жіберу пункттеріндегі жүктің барлық қорының тағайындалған пункттегі осы жүкке деген қажеттілікке теңдігі болып табылады

=

Кейде бұл теңдік орындалмайды, яғни кейде жүк қоры тағайындалған пункттегі қажеттіліктен үлкен болады

> ,

Кейде тағайындалған пунктегі қажеттілік жүк қорынан асады

Lt;.

Бұл жағдайлар үшін ең аз транспорт шығынымен тасымалдау жоспарын құру туралы есеп қойылуы мүмкін.

Қажеттіліктен қор асқан кезде тасымалдаудың тиімді жоспарын іздеу үшін

>

жалған (n+1) –ші қажеттілікке ие тағайындау пунктін енгізеді.

b_n+1 = - және осы пунктте жүктерді тасымалдау бағасын нолге теңестіріп алады: c_{i, n+1} = 0 (i = 1, …, m). Алынған есеп кәдімгі транспорттық есеп болып табылады, өйткені

=

теңдігі орындалады.

Жаңа есептің тиімді жоспарынан алынған жоспары бастапқы есептің тиімді жоспары болып табылады, өйткені бұрынғы есептің жақсы жоспарының бар болуы жаңа есептің жақсы (тиімдіден жақсы) жоспарына алып келетінін көрсету қиын емес.

<

болғанда a_m+1 = - жүк қоры және c_{m+1, j} = 0 (j =1, …, n) тасымалдау шығыны бар жалған (m +1)-ші пункт енгіземіз. Осымен есеп тиімді шешімнен жоғарыдағыдай берілген есептің тиімді шешімін алуға болатын транспорт есебіне келеді.

9-дәріс Көліктік тасымалдауға шектеулер қойылған жағдайдағы тиімді маршрутты анықтау