LP: Двойное и дополнительное отклонение (упражнения - решения)

Двойной и дополнительный спред

Данная ТД предлагает различные корректирующие упражнения на двойная программа и алгоритм дополнительного разрыва. За упражнениями следуют исправления.

Руководство

давайте возьмем это линейная программа следующий :

Решите линейную программу.

Коррекция

Есть четыре базовых переменных для двух ограничений, возможно, что задача не ограничена и не имеет решения. Поскольку есть два ограничения, у двойного будет две переменные, легко найти графическое решение этой новой линейной программы.

Двойственность следующая:

А вот его графическое представление, с минимумом в (1,1) и для целевой функции 15.

Давайте посмотрим на них дополнительные отклонения найти решение исходного.

• Две переменные не равны нулю, поэтому два ограничения первичного числа насыщены (ограничение становится равным).
• В двойственном случае ограничения 1 и 3 ненасыщаемы для решения (1,1), это означает, что первая переменная и третья переменная простого числа равны нулю.

Таким образом, нам нужно решить следующие два уравнения:

• Икс₂ + 2x₄ = 8
• 2x₂ +х₄ = 7

Что дает для решения (0, 2, 0, 3) и для целевой функции 15. Решения прямого и двойственного равны, существует сильная двойственность, поэтому это оптимальное решение.

Упражняться

Упражнение 1

Решите следующую линейную программу, используя двойную (графическое разрешение + симплекс и дополнительные отклонения):

Коррекция

Линейная программа находится под каноническая форма, поэтому мы можем вычислить дуал, не изменяя форму программы. Двойственность следующая:

с графическим разрешением:

Глобальный оптимум уникален и находится в точке (6/5, 7/5) с целевой функцией Z=79/5.

Для симплекса стандартная форма добавляет резервная переменная для каждого ограничения линейной программы. Финальная таблица:

Вектор решения двойственности равен (6/5, 7/5, 0, 0, 19/5, 19/5) с Z=79/5. Дополнительные отклонения предоставляют следующую информацию:

• Третье и четвертое ограничения двойственного ненасыщаемы, третья и четвертая переменные первичного равны нулю.
• Две основные переменные отличны от нуля, поэтому два ограничения основного числа насыщены.

Итак, нам нужно решить систему уравнений:

• х1 + 3 х2 = 5
• 2х1 + х2 = 7

Вектор (16/5, 3/5, 0, 0) является решением системы с Z = 79/5. Существует сильная двойственность, поэтому это глобальный оптимум линейной программы.

Упражнение 2

Рассмотрим следующую линейную программу:

Рассчитать оптимальное решение по графическому разрешению. Целевая функция имеет для нового коэффициента (3, 5) проверку того, что решение, найденное ранее, всегда оптимально с использованием двойных и дополнительных отклонений.

Коррекция

в поле определения является следующим:

Графическое решение представляет собой вектор (5, 3) с Z=13.

С коэффициентами целевой функции в (3, 5) мы будем иметь Z = 30. Проверим с дополнительными отклонениями, имеем ли мы сильную двойственность. Двойная программа выглядит следующим образом:

Дополнительные отклонения заключаются в следующем:

• две базовые переменные первичного числа отличны от нуля, поэтому два ограничения двойственного числа насыщены
• первое ограничение первичного числа ненасыщаемо, поэтому первая переменная двойственного числа равна нулю.

Итак, нам нужно решить следующую систему:

• 3x3 = 3
• х2 – х3 = 5

Вектор (0, 6, 1) является решением системы с Z = 30. Существует сильная двойственность, поэтому (5, 3) всегда является оптимальным решением первичной программы.

Упражнение 3

Рассмотрим следующую линейную программу:

Проверьте оптимальность решения (250, 500, 1500), используя двойное и дополнительное отклонения.

То математическое моделирование оказывается ложным, и после проверки вектор ограничения b равен (950, 550, 1575, 6900). С помощью дуала проверьте, допустимо ли решение и является ли оно оптимальным решением.

Аналогично с вектором (1000, 500, 1500, 9750).

Коррекция

Вектор (250, 500, 1500) является допустимым решением, поскольку не нарушается ни одно ограничение. Оптимальное решение имеет значение Z=11500. Проверим его оптимальность по двойственной и дополнительной лакунам. Двойственность следующая:

Дополнительные отклонения предоставляют следующую информацию:

• никакая базовая переменная первичного числа не равна нулю, поэтому ограничения двойственного числа насыщены
• первое ограничение первичного числа не насыщено, поэтому первая переменная двойственного числа равна нулю

Это дает следующую систему:

• 3х4 = 4
• Х2 + 6Х4 = 12
• Х3 + 2 Х4 = 3

С вектором решения (0, 4, 1/3, 4/3) с Z=11500. Существует сильная двойственность, так что это действительно оптимальное решение.

Давайте снова проверим оптимальность с помощью простого числа со столбцом b = (950, 550, 1575, 6900), изменится только целевая функция двойственного числа. Решение допустимо, а дополнительные отклонения таковы:

• Три основные переменные не равны нулю, поэтому ограничения двойственности насыщены.
• Ни одно ограничение не является насыщенным, поэтому базовые переменные двойственности равны нулю.

Нет необходимости решать двойственное, потому что все базовые переменные равны нулю (Z=0), решения двойственного нет. Это означает, что решение двойственного уравнения не находится на экстремуме области определения.

Аналогично с вектором b= (1000, 500, 1500, 9750). Решение допустимо, а дополнительные отклонения дают следующую информацию:

• Три основные переменные не равны нулю, поэтому ограничения двойственности насыщены.
• Первое и четвертое ограничения ненасыщаемы, поэтому первая и четвертая базовые переменные двойственности равны нулю.

Система не допускает решения, поэтому предлагаемое решение не находится на экстремуме области определения. Поэтому он не может быть оптимумом линейной программы.

Подтвердите свои навыки

Упражнение 4

Когда в сеть подается некоторое количество электричества, эта энергия распространяется по линиям с наименьшим сопротивлением. Узнать линии, которые будут заимствованы этим энергетическим потоком, можно с помощью линейной программы.

Для этого необходимо определить сеть и поток энергии:

• поток начинается из одного источника и распространяется по пути с наименьшим сопротивлением к потребителю
• линии односторонние, поток энергии может двигаться только в направлении тока, уже протекающего по линии

Сеть представляется в виде графа следующим образом: узлы — подстанции, а дуги — линии, узел 1 — начало источника энергии, узел 7 — пункт назначения потока энергии.

Переменные:

• для каждой строки переменная от 0 до 1 дает процент использования строки.

Целевая функция:

• мы стремимся минимизировать общую стоимость, то есть сумму процентов использования линий, умноженных на стоимость линии.

Ограничения следующие:

• для исходного узла сумма переменных исходящих дуг минус сумма переменных входящих дуг равна 1
• для узла прибытия сумма переменных входящих дуг минус сумма переменных исходящих дуг равна 1
• для остальных узлов сумма переменных исходящих дуг за вычетом суммы переменных входящих дуг равна 0.

Представьте линейную программу предыдущего графика, рассчитайте двойственную программу и решите ее с помощью Excel. Выведите результат программы Primal, обратите внимание, что систему уравнений можно решить в Excel с помощью команды {=PRODUCTMAT(INVERSEMAT(Система); Целевой вектор)} где коэффициенты заданы в матричной форме.

Например :

Коррекция

Линейная программа, представляющая задачу кратчайший путь является следующим:

Следующая программа Excel дает первичные решения зеленым цветом, а двойные решения — красным (основные ограничения находятся в строках, а двойные ограничения — в столбцах), обратите внимание, что ограничения первичного равенства заставляют двойные переменные находиться в наборе действительных чисел:

Ограничения 4, 5, 7, 8 двойственного ненасыщаемы, поэтому переменные 4, 5, 7, 8 простого числа равны нулю. Итак, нам нужно решить следующую систему:

Эту систему можно очень просто решить без Excel и с вектором ( 0, 1, 0, 0, 0, 1, 0, 0, 1, 1) и Z = 22 в качестве ответа. Существует сильная двойственность, поэтому это оптимальное решение. Если представить дуги, используемые потоком энергии, красным цветом, получится следующий график диффузии:

Упражнение 5

Энергетический остров (локальная сеть, отрезанная от глобальной сети) имеет два источника энергии и три поселка-потребителя. Завод 1 производит 550 МВтч, а завод 2 производит 350 МВтч. Деревня 1 требует 400 МВтч, деревня 2 требует 300 МВтч, а деревня 3 требует 200 МВтч. Стоимость каждого МВтч, проходящего по сетевой линии, указана в евро, как показано на графике ниже:

Решение существует, если доступное количество больше или равно запрошенному количеству.

1. Сформулируйте задачу минимизации стоимости транзита энергии от производителей к потребителям, объясните целевую функцию и ограничения.
2. Сформулируйте задачу максимизации прибыли от транзита энергии (точка зрения сетевого менеджера).
3. Решите одну из задач и найдите решение другой, используя дополнительные пропуски.

Коррекция

Доступно 900 количеств и столько же запросов, поэтому есть возможное решение. Переменные:

• для каждой строки X представляет количество, проходящее через линию.

Целевая функция:

• минимизировать общую стоимость ресурсов, проходящих по всем линиям.

Ограничения следующие:

• ограничения запасов (меньше или равно)
• ограничения спроса (больше или равно).

Линейная программа выглядит следующим образом:

Как и в предыдущем упражнении, мы решим прямое и двойное числа на одном листе Excel:

Решение двойственности дает вектор решения (0, 2, 5, 6, 3) с пятым и шестым ненасыщаемыми ограничениями. Мы делаем вывод, что первое ограничение первичного числа ненасыщаемо (следовательно, с ненулевой переменной отклонения) и что пятая и шестая базовые переменные равны нулю. Итак, нам нужно решить следующую систему:

Можно найти решение и без Excel, он даст базовый вектор (50, 300, 200, 350, 0, 0) при Z=3700. По сильной двойственности это оптимальное решение.