математика. Документ Microsoft Word (10) (1). min, при этом x
 Скачать 190.19 Kb.
|
|
1. Проверка критерия оптимальности. Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: x1 = 0, x2 = 32/5, x3 = 0, x4 = 2/5 F(X) = 3*0 + 1*32/5 + 2*0 + 2*2/5 = 41/5 Анализ оптимального плана. В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 9. Значение 0 в столбце x2 означает, что использование x2 - выгодно. Значение 0 в столбце x4 означает, что использование x4 - выгодно. Значение 0 в столбце x5 означает, что теневая цена (двойственная оценка) равна y1=0. Значение 2/5 в столбце x6 означает, что теневая цена (двойственная оценка) равна y2=2/5. Значение 1/5 в столбце x7 означает, что теневая цена (двойственная оценка) равна y3=1/5. Примечание: 1. По какому методу пересчитываются симплекс-таблицы? Используется правило прямоугольника (метод жордановских преобразований). 2. Обязательно ли каждый раз выбирать максимальное значение из индексной строки? Можно не выбирать, но это может привести к зацикливанию алгоритма. 3. В индексной строке в n-ом столбце нулевое значение. Что это означает? Нулевые значения должны соответствовать переменным, вошедшим в базис. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных. Построим двойственную задачу по следующим правилам. 1. Количество переменных в двойственной задаче равно количеству неравенств в исходной. 2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной. 3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется. Расширенная матрица A.
Транспонированная матрица AT.
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной. Неравенства, соединенные стрелочками (↔), называются сопряженными. 2y1+y2+y3≤3 3y1+2y2+y3≤1 y1+y2+y3≤2 2y1+3y2+4y3≤2 2y1+8y2+5y3 → max y1 ≥ 0 y2 ≥ 0 y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов. Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. y1=0, y2=2/5, y3=1/5 Это же решение можно получить, применив теоремы двойственности. Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных. Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен: y1 = 0, y2 = 2/5, y3 = 1/5 Z(Y) = 2*0+8*2/5+5*1/5 = 41/5 Экономический смысл всех переменных, участвующих в решении.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||