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

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

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

Руководство

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

линейное программирование, двойная форма, дополнительные пробелы, исправленные упражнения

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

Коррекция

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

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

линейное программирование, двойная форма, дополнительные пробелы, исправленные упражнения

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

линейное программирование, двойная форма, дополнительные пробелы, исправленные упражнения

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

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

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

  • Икс2 + 2x4 = 8
  • 2x24 = 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. По сильной двойственности это оптимальное решение.

Делиться
ru_RURU