Урок 2. Двойственная задача линейного программирования. Excel

Статья с подробным разбором.

Запись математической модели пары двойственных задач линейного программирования
Нахождение решения двойственной задачи по последней симплекс-таблице прямой задачи
Решение двойственной задачи по отчёту "устойчивость" прямой задачи
Видео

Запись математической модели пары двойственных задач линейного программирования
Модель прямой задачи линейного программирования из урока 1:

x₁ ≥ 0

x₂ ≥ 0

x₃ ≥ 0

x₄ ≥ 0

4x₁+2x₂+4x₃+3x₄ → max

10x₁+20x₂+15x₃+18x₄≤250

5x₂+8x₃+7x₄≤40

15x₁+18x₂+12x₃+20x₄≤100

8x₁+12x₂+11x₃+10x₄≤80

Записываем в Excel матрицу прямой задачи:

Матрица прямой задачи в Excel

Транспонируем полученную матрицу и получаем матрицу двойственной задачи:
ТРАНСП(C12:G16)

Матрица обратной задачи в Excel

Двойственная задача запишется в виде:

Двойственная задача II

10y₁+15y₃+8y₄≥4

20y₁+5y₂+18y₃+12y₄≥2

15y₁+8y₂+12y₃+11y₄≥4

18y₁+7y₂+20y₃+10y₄≥3

250y₁+40y₂+100y₃+80y₄ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

y₄ ≥ 0

Запишем обе задачи

Исходная задача I		Двойственная задача II
x₁ ≥ 0	↔	10y₁+15y₃+8y₄≥4
x₂ ≥ 0	↔	20y₁+5y₂+18y₃+12y₄≥2
x₃ ≥ 0	↔	15y₁+8y₂+12y₃+11y₄≥4
x₄ ≥ 0	↔	18y₁+7y₂+20y₃+10y₄≥3
4x₁+2x₂+4x₃+3x₄ → max	↔	250y₁+40y₂+100y₃+80y₄ → min
10x₁+20x₂+15x₃+18x₄≤250	↔	y₁ ≥ 0
5x₂+8x₃+7x₄≤40	↔	y₂ ≥ 0
15x₁+18x₂+12x₃+20x₄≤100	↔	y₃ ≥ 0
8x₁+12x₂+11x₃+10x₄≤80	↔	y₄ ≥ 0

Запишем матрицы соответствия переменных двойственных задач:

Матрицы соответствия переменных двойственных задач

Единица по диагонали означает соответствие:
x₁↔y₅; x₂↔y₆; x₃↔y₇ ; x₄↔y₈; x₅↔y₁; x₆↔y₂; x₇↔y₃; x₈↔y₄

Нахождение решения двойственной задачи по последней симплекс-таблице прямой задачи
Подпишем соответствующие переменные к последней симплекс-таблице из урока 3

Последняя симплекс-таблица прямой задачи

Решение двойственной задачи по отчёту «устойчивость» прямой задачи
Приведём отчёт по "устойчивости из урока 1.

Отчёт по "устойчивости"

Видим, что решение полученное из последней симплекс-таблицы прямой задачи совпадает со значениями, полученными через надстройку «поиск решения» в отчёте на устойчивость.
Значения целевых функций для оптимальных планов двойственных задач совпадают F _min = f_max = 30,667.
Значения Y6=3,3 и Y8=3,0333 означают, что при производстве одного вида продукции 2-го и 4-го вида значение целевой функции уменьшится на 3,3 и 3,0333 денежных единиц соответственно.
Y5=Y7=0 означает, что производство 1-го и 3-го видов продукции является наиболее эффективным.
Значения Y2=0,1 и Y3=0,267 означают, что при увеличении запасов 2-го и 3-го видов сырья на одну весовую единицу, значение целевой функции возрастёт на 0,1 и 0,267 денежных единиц соответственно. Так же это означает дефицитность этих видов ресурсов, так как оценки выше нуля.
Y1=Y4=0 – это означает, что ресурсы 1-го и 4-го видов не являются дефицитными и их увеличение никак не повлияет на значение целевой функции.
Эти выводы действительны в пределах интервалах устойчивости изменения ресурсов и коэффициентов целевой функции.
Надстройка «поиск решения» автоматически считает интервалы устойчивости для коэффициентов целевой функции и ресурсов. Интервалы устойчивости показаны в столбцах «допустимое увеличение» и «допустимое уменьшение».
В следующей статье мы рассмотрим определение интервалов устойчивости ресурсов и коэффициентов целевой функции на основании последней симплекс-таблице из занятия 3.
Файл с решением:
https://t.me/smys_l/129

Заявка на услуги

Укажите наиболее удобный для ВАС способ связи
и с Вами свяжутся в ближайшее время

Нажимая на кнопку, Вы соглашаетесь на обработку персональных данных в соответствии с Условиями.