Решение транспортной задачи линейного программирования в матричной постановке, страница 7

β₁-α₁=1

β₄-α₁=10

β₂-α₂=14

β₃-α₃=16

β₂-α₄=8

β₃-α₄=4

β₄-α₄=9

α₁=0

Решая систему, получаем:

α₁=0, α₂= 4, α₃= - 2, α₄=10

β₁=1, β₂=18, β₃=14, β₄=10 

Проверяем рентабельность перевозок:

r₁₂= 13, r₁₃= 12, r₂₁= - 6, r₂₃= 9, r₂₄= 5, r₃₁= -4, r₃₂= 13, r₃₄= -9, r₄₄= -9. 

Рентабельными являются свободные клетки, у которых оценка рентабельности положительная. Наш план не является оптимальным, т.к. есть еще рентабельные перевозки. Найдем новый опорный план:

Введем в базис x₂₃, т.к. у этой перевозки низкая себестоимость (самая высокая рентабельность). Строим цикл пересчета:

╔════════╤════════╤════════╤════════╤════════╤════════╤═════════╗

 ║ИЗ \ В  │D1      │D2      │D3      │D4      │ПОСТАВЩ.│ U(i)    ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 1.000│ │ 5.000│ │ 2.000│ │ 10.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S1      │ 1.000  │        │        │   0    │ 1.000  │   0     ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 3.000│ │ 14.00│ │ 1.000│ │ 1.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S2      │        │ 1.000  │        │        │ 1.000  │ 5.000   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 7.000│ │ 7.000│ │ 16.00│ │ 21.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S3      │        │        │ 1.000  │        │ 1.000  │ 11.00   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │   0  │ │ 8.000│ │ 4.000│ │ 9.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S4      │        │   0    │   0    │ 1.000  │ 1.000  │-1.000   ║

 ╟────────┼────────┼────────┼────────┼────────┼────────┼─────────╢

 ║ПОТРЕБ. │ 1.000  │ 1.000  │ 1.000  │ 1.000  │        │         ║

 ║  V(j)  │ 1.000  │ 9.000  │ 5.000  │ 10.00  │        │         ║

 ╚════════╧════════╧════════╧════════╧════════╧════════╧═════════╝

Получили новый опорный план:

╔════════╤════════╤════════╤════════╤════════╤════════╤═════════╗

 ║ИЗ \ В  │D1      │D2      │D3      │D4      │ПОСТАВЩ.│ U(i)    ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 1.000│ │ 5.000│ │ 2.000│ │ 10.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S1      │ 1.000  │     0  │        │        │ 1.000  │   0     ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 3.000│ │ 14.00│ │ 1.000│ │ 1.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S2      │        │ 1.000  │   0    │        │ 1.000  │ 5.000   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │ 7.000│ │ 7.000│ │ 16.00│ │ 21.00│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S3      │        │        │ 1.000  │        │ 1.000  │ 11.00   ║

 ╟────────┼─┬──────┼─┬──────┼─┬──────┼─┬──────┼────────┼─────────╢

 ║        │ │   0  │ │ 8.000│ │ 4.000│ │ 9.000│        │         ║

 ║        │ └──────┤ └──────┤ └──────┤ └──────┤        │         ║

 ║S4      │        │   0    │        │ 1.000  │ 1.000  │-1.000   ║

 ╟────────┼────────┼────────┼────────┼────────┼────────┼─────────╢

 ║ПОТРЕБ. │ 1.000  │ 1.000  │ 1.000  │ 1.000  │        │         ║

 ║  V(j)  │ 1.000  │ 9.000  │ 5.000  │ 10.00  │        │         ║

 ╚════════╧════════╧════════╧════════╧════════╧════════╧═════════╝

Величина ЦФ = 40. Найден альтернативный план.

4)  Анализируем, что общего и в чем отличие между процессами решения методом потенциалов ТЗ и задачи о назначениях в их классической постановке.

Анализируя ТЗ и задачу о назначениях в их классической постановке, можно выделить следующие отличия: ТЗ минимизируется, а задача о назначениях, решается на максимум. В ТЗ мощность поставщика должна быть равна мощности потребителя (условие баланса или невырожденности), а в задаче о назначениях, как частный случай ТЗ, число поставщиков должно быть равным числу потребителей. ТЗ решается при ограничениях на запасы груза у поставщиков и спроса у потребителей, а в задаче о назначениях эти числа равны 1. Если в ТЗ X_ij – количество груза перевозимого от i – го поставщика к j – ому потребителю, то в задаче о назначениях X_ij –коэффициент, принимающий значение 1, если i – ый поставщик назначен на j – ое задание, и 0 в противном случае.

В процессе решения методом потенциалов ТЗ и задачи о назначении различий нет, т.к. этот метод одинаково хорошо подходит как к решению ТЗ, так и задачи о назначениях.

Вывод: В процессе выполнениялабораторной работы мы приобрели практические навыки и опыт решения транспортной задачи (ТЗ) линейного программирования в матричной постановке. Научились анализировать полученное решение и находить альтернативные варианты решения; увидели связь между ТЗ и общей задачей линейного программирования, между различными моделями ТЗ. Мы научились решать ТЗ несколькими методами, а именно – методом северо-западного угла и методом Фогеля, с помощью ПЭР. Оптимальное значение целевой функции совпало при решении задачи обоими методами (5990 = 5990), это говорит о том, что оба метода одинаково подходят для решения ТЗ. Также мы узнали о задаче о назначениях, и даже решили ее вручную методом потенциалов. После чего работа была тщательно проанализирована.