Способы решения транспортной и линейной оптимизационной задач

Способы решения транспортной и линейной оптимизационной задач

1.       Линейная оптимизационная задача

транспортный задача ресурс

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

Решение: Составим математическую модель

Приведем задачу к каноническому виду

Решим задачу симплекс-методом

В строке коэффициентов целевой функции имеются отрицательные элементы, выберем минимальный из них (-5). В третьем столбце два положительных элемента, найдем минимальное симплексное отношение  

Таким образом, ключевым элементом является 2

Разделим ключевую вторую строку на 2 и вычтем ее из первой строки.

Умножим преобразованную ключевую строку на 5 и сложим ее с четвертой строкой. В итоге над ключевым элементом и под ним будут получены нули. Х₅ выводится из базиса, его место занимает Х_3. Симплекс-таблица принимает вид:

В строке целевой функции имеется отрицательный элемент (-2).

Во втором столбце имеется два положительных элемента. Найдем минимальное симплексное отношение  

Таким образом, ключевым элементом является 2.

Разделим первую строку на 2

Умножим преобразованную первую строку на 4 и вычтем ее из третьей строки.

Умножим преобразованную первую строку на 2 и сложим ее с четвертой строкой. Х₄ выводится из базиса, его место занимает Х_2. Получаем таблицу. В строке целевой функции нет отрицательных элементов, значит задача решена.

Снимает ответ. Переменные, вошедшие в базис, приравниваем к свободным членам. Переменные, которые не вошли в базис, равны нулю.

Таким образом, рекомендуем предприятию выпускать продукцию второго типа в объеме 100 ед., продукцию третьего типа в объеме 230 ед., а продукцию первого типа выпускать нецелесообразно. При этом первый и второй ресурс будут израсходованы полностью, а третьего останется 20 ед.

Подставляем значения переменных в целевую функцию

2.      
Транспортная задача

Решение: Транспортная задача закрытая, так как суммарные запасы =40+10+30+20=100 и суммарные потребности =50+10+30+10=100 совпадают.

Строим опорный план (методом минимального тарифа) с  базисными клетками.

Вначале заполним клетку (3;3). Она имеет минимальный тариф, равный единице. Третий поставщик исчерпал себя и третий потребитель удовлетворен.

Находим во всей таблице минимальный тариф. Его имеет клетка (2;1) и он равен 10. Поставляем в нее груз равный десяти от второго поставщика. Второй поставщик исчерпал себя.

Вновь находим во всей таблице минимальный тариф. Он равен 2 его имеет клетка (4;1). Поставляем первому потребителю груз 20 от четвертого поставщика. Четвертый поставщик исчерпал себя.

Находим во всей таблице минимальный тариф. Его имеет клетка (1;1). Этот тариф равен 3. Поставляем первому потребитель груз 20 от первого поставщика. Первый потребитель удовлетворен.

Находим в первой строке минимальный тариф. Он равен 5. Поставляем четвертому потребителю от первого поставщика груз 10. Четвертый потребитель удовлетворен.

Поставляем груз 10 в клетку (1;2). Первый поставщик исчерпал себя и второй потребитель удовлетворен.

Проверим план на оптимальность.

Для составления уравнений потенциалов заполним две клетки нулями.

Найдем оценки свободных клеток

Δ_ij = c_ij- (u_i + v_j ) от тарифа отнимем сумму потенциалов

Δ₁₃ = c₁₃- (u₁ + v₃ )=5-(0+4)=1

Δ₂₂ = c₂₂.- (u₂ + v₂ )=8-(-2+9)=1

Δ₂₄ = c₂₄ - (u₂ + v₄ )=3-(-2-1)=6

Δ₂₃ = c₂₃ - (u₂ + v₃ )=5-(-2+4)=3

Δ₃₁ = c₃₁ - (u₃+ v₁ )=7-(-3+3)=7

Δ₃₂ = c₃₂ - (u₃+ v₂ )=2-(-3+9)=-4

Δ₃₄ = c₃₄ - (u₃+ v₄ )=4-(-3-1)=8

Δ₄₂ = c₄₂ - (u₄+ v₂ )=4-(-1+9)=-4

Δ₄₃ = c₄₃ - (u₄+ v₃ )=10-(-1+4)=7

Δ₄₄ = c₄₄ - (u₄+ v₄ )=6-(-1-1)=4

Так как имеются отрицательные оценки план не является оптимальным.

Возьмем в качестве перспективной клетку (3;2).

Построим на ее базе цикл.

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

Будем перемешать минимальный груз, получивший знак минус. Этот груз равен 10. Если встречаем клетку со знаком плюс прибавляем в нее груз 10, если со знаком минус, вычитаем этот груз. В итоге получим следующий цикл.

После применения распределительного метода имеем таблицу

Проверим найденный план на оптимальность. Уравнения потенциалов имеют вид:

Δ₂₂ = c₂₂ - (u₂ + v₂ )=8-(-2+5)=5

Δ₂₄ = c₂₄ - (u₂ + v₄ )=3-(-2-1)=6

Δ₂₃ = c₂₃ - (u₂ + v₃ )=5-(-2+4)=3

Δ₃₁ = c₃₁ - (u₃+ v₁ )=7-(-3+3)=7

Δ₃₄ = c₃₄ - (u₃+ v₄ )=4-(-3-1)=8

Δ₄₂ = c₄₂ - (u₄+ v₂ )=4-(-1+5)=0

Δ₄₃ = c₄₃ - (u₄+ v₃ )=10-(-1+4)=7

Δ₄₄ = c₄₄ - (u₄+ v₄ )=6-(-1+5)=5

Таким образом, план оптимален, так как все оценки положительны.

Нулевая оценка свидетельствует о том, что план не является единственным.

Найдем стоимость плана

Ответ: