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

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы
Определим максимальное значение целевой функции F(X) = 6×1+7.5×2+10×3+15×4 при следующих условиях-ограничений.
4×1+5×2+10×3+2×4≤30
5×1+15×2+20×3+5×4≤70
40×1+10×2+15×3+20×4≤150
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7. 
4×1 + 5×2 + 10×3 + 2×4 + 1×5 + 0x6 + 0x7 = 30
5×1 + 15×2 + 20×3 + 5×4 + 0x5 + 1×6 + 0x7 = 70
40×1 + 10×2 + 15×3 + 20×4 + 0x5 + 0x6 + 1×7 = 150
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x5, x6, x7
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,30,70,150)
Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai4
и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Представим расчет каждого элемента в виде таблицы:

После преобразований получаем новую таблицу:

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:
x4 = 7.5
F(X) = 15 • 7.5 = 112.5
Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A.

Транспонированная матрица AT.

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (↔), называются сопряженными.
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.
Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.
Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj.
4y1+5y2+40y3≥6
5y1+15y2+10y3≥7.5
10y1+20y2+15y3≥10
2y1+5y2+20y3≥15
30y1+70y2+150y3 → min
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0

Переменные yj называются допустимым решением двойственной задачи. Переменные yj называются оптимальными, если они допустимые и на них целевая функция достигает минимальное значения.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 = 

Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 0
y3 = 0.75
Z(Y) = 30*0+70*0+150*0.75 = 112.5
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

KseniyaP 4.9

Имею красный диплом по менеджменту и кадровому делопроизводству. Дополнительно занимаюсь английским, интересуюсь экономикой, особо люблю исторические работы и родной язык (русский и литература). Пишу логично, без ошибок. Выбирай меня!

Нанять автора