Задача линейного программирования. Проверка оптимальности текущего плана, страница 25

Решение 1.Проверяем выполнение необходимого и достаточного условия разрешимости задача: , . Значит данная задача открытая.

2.Введем фиктивного поставщика с запасами а₃ = 50-40 = 10 и нулевыми стоимости перевозок единиц груза (см. табл. 16)

3.Находим первоначальное решение, например, методом минимального элемента. Заполнение фиктивного поставщика в последнюю очередь. Для удобства укажем последовательность заполнения таблицы поставок:  х₁₃ = 15, х₂₂ = 15, х₂₁ = 10, х₃₁ = 5, х₃₃ = 5.

                                                                                           Таблица 16

4.Находим матрицу оценок  .

Так как Δ_ij ≤ 0  i,j, то план перевозокоптимальный.

Стоимость перевозок по оптимальному плану   min Z(X) = Z(X^*)=1·15+3·10+2·15=75.

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

Теорема. Пусть имеется транспортная задача, тогда: если  - некоторые оптимальные решения задачи, то где t₁+t₂=1, t₁≥ 0, t₂≥ 0, также является оптимальным решением.

Пример 3. Найти оптимальное решение для транспортной задачи (табл. 17).

Таблица 17

Решение.1)Находим первоначальный план методом минимального элемента.

Заполняем таблицу следующим образом: х₁₁=40,  х₂₂ = 10,  х₂₃ = 10,  х₁₃ = 15.

Таблица 18

,

.

2) Проверим оптимальность текущего плана .

Все оценки клеток табл. 18  ∆_ij ≤ 0, значит план  оптимален.

Так как оценка свободной клетки (2, 1) нулевая, т.е. ∆₂₁ = 0, то задача имеет не единственное решение. Для отыскания общего оптимального решения, прежде всего, необходимо перейти к следующему новому оптимальному решению.

3) ∆₂₁ = 0  следует перемещать по циклу с замещением клетки (2, 1).

Находим        θ₁= {x₁₁=40, x₂₃=10 } =10, откуда находим второе оптимальное решение

Таблица 19

 

4) находим общее оптимальное решение   ,  где  t₁ + t₂ = 1,  t₁ ≥ 0,  t₂ ≥ 0.

Таким образом, общее оптимальное решение  .

Задаваясь любыми значениями  t₁, t₂ при сохранении условий  t₁ ≥ 0,  t₂≥ 0  и  t₁ + t₂ = 1, будем получать различные оптимальные решения, а среди них и указанные выше оптимальные решения.

Решение транспортной задачи на ЭВМ. Исходные данные для транспортной задачи в таблице на рис. 1.

Рис. 1. Исходные данные транспортной задачи