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

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы
Определим максимальное значение целевой функции 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

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

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

Готовые работы на продажу

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Нажимая "Купить" вы будете перенаправлены на страницу карточки работы.

Гарантия на работу 10 дней.

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

400₽

• Решение задач
• Информатика
• Выполнил: user946470

Купить

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

500₽

• Курсовая работа
• Программирование
• Выполнил: Heinenof

Купить