ЛП: частные случаи (упражнения – решения)

Особые случаи

Этот учебник предлагает исправленные упражнения для конкретных случаев (вырождение, заглавная М, симплекс в два этапа).

Руководство

Брокеру необходимо для своих клиентов 108 МВтч электроэнергии для города 1 и 96 МВтч электроэнергии для города 2. Однако законы Кирхгофа не позволяют дистрибьютору нацеливать поток энергии на один город. Два дистрибьютора обслуживают эти города: дистрибьютор А может отправить 12 МВтч в город 1 и 8 МВтч в город 2 за купленный лот; Дистрибьютор B может отправить 9 МВтч в город 1 и 12 МВтч в город 2 за купленный лот. Все лоты имеют одинаковую цену. Сколько лотов должен купить брокер, чтобы удовлетворить потребности двух городов в энергии? Решить графическим методом и симплексом.

Коррекция

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

Что дает для графическое разрешение :

Градиент равен (-1, -1), поскольку он является минимальным (min f(x) = – max -f(x)). в поле определения зеленым цветом точка C является единственным экстремумом, являющимся глобальным оптимумом. Разложение предыдущей системы в виде равенства дает для координат (6, 4) с Z = 10.

Для разрешения симплекса необходимо прежде всего привести его к стандартной форме.

Вы должны решить двухфазный симплекс чтобы исключить искусственные переменные:

И результат первого этапа. Заметим, что Z=0, значит, есть решение проблемы:

Для второго этапа строка Z пересчитывается после удаления столбцов искусственных переменных. Для этого используем правильные коэффициенты целевой функции (-1, -1, 0, 0):

-(0) + (-1 * 6) + (-1 * 4) = -10 для столбца b (P0)
-(-1) + (-1 * 1) + (-1 * 0) = 0 для столбца P1
-(-1) + (-1 * 0) + (-1 * 1) = 0 для столбца P2
-(0) + (-1 * -1/6) + (-1 * 1/9) = 1/18 для столбца P3
-(0) + (-1 * 1/8) + (-1 * -1/6) = 1/24 для столбца P4

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

Все коэффициенты за пределами столбца b положительны, поэтому симплекс уже имеет оптимальное решение Z = 10 с вектором (6, 4, 0, 0).

Упражняться

Упражнение 1

Розничный торговец электроэнергией пообещал своим клиентам, что не менее 25% его электроэнергии будет поступать из возобновляемых источников. Он подсчитал, что в наступающем году его рынок составит максимум 18 ТВтч. Он также предварительно выбрал трех поставщиков, у которых будет покупать электроэнергию оптом. Вот количество (в ТВтч), тариф на возобновляемую электроэнергию и генерируемая маржа (в тысячах евро/ТВтч), которую могут обеспечить эти три производителя. У каких производителей и в каком количестве этот перекупщик должен покупать электроэнергию, чтобы получить максимально возможную прибыль? Решите линейная задача методом большого М с использованием Excel.

Коррекция

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

Задача решается в два этапа, потому что есть искусственная переменная. Вот таблица первого этапа:

И решение первой фазы, мы замечаем, что Z=0, так что есть решение проблемы:

После пересчета коэффициентов Z второй этап начинается со следующей таблицы:

И заканчивается следующей таблицей:

Упражнение 2

Решите следующую линейную программу (в Excel):

Коррекция

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

Поэтому необходимо решить проблему большого M, чтобы исключить искусственные переменные. Симплекс, который нужно решить:

Что дает результат:

Устранив искусственные переменные и вернувшись к двойная программа имеем следующую таблицу:

Оптимальное решение имеет вектор (3/7, 2/7) с Z=65/7. Давайте пройдем через дополнительные пробелы, чтобы найти решение основного.

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

• Х1 + 5 Х4 = 15
• 2х1 – 4х4 = 10

Вектор решения основного числа равен (55/7, 0, 0, 10/7) и Z=65/7. Существует сильная двойственность, поэтому это оптимальное решение первобытного.

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

Упражнение 3

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

Задача формулируется следующим образом: экорайон стремится получить максимальную прибыль за продажу энергии в размере 25 кВтч. Эко-район должен продать все излишки энергии.

Коррекция

Чтобы решить эту проблему, учтите, что каждое предложение представлено переменной (в процентах принятия предложения), которая будет находиться в диапазоне от 0 до 1.

Проблема формулируется следующим образом:

Что дает стандартный вид:

Начнем с решения большого M:

После решения заглавной М и возврата к стандартной форме:

Заметим, что значение Z для переменной 1, 2, 3, 4, 5 равно нулю, поэтому существует бесконечное множество решений. Полученное здесь решение Z=166/5 с вектором (1, 9/10, 1, 0, 1, 0).