2015-08-21
597
Каждой задаче линейного программирования соответствует двойственная задача. Прямая задача отражает наиболее эффективное сочетание использования ресурсов, двойственная – оптимальную комбинацию оценок дефицитных ресурсов или двойственных оценок.
Пусть дана прямая задача линейного программирования.
Имеются ресурсы В1, В2,….Вm – которые необходимо использовать для производства продукции х1, х2,….хn, причем стоимость продукции должна быть максимальной Z®max, а расход ресурсов не должен превышать их наличия.
Математическое представление прямой задачи в расширенном виде:
………………………………..
Общее структурное представление:
При составлении двойственной задачи вводят двойственные переменные - y1, y2,….ym, Их количество равно количеству ограничений, которые являются оценками имеющихся ресурсов.
Математическая запись двойственной задачи будет иметь следующий вид:
………………………………..
,
где 
– технолого-экономические коэффициенты при неизвестных 
прямой задачи;
|
|
|
– двойственные оценки или скрытые цены ресурсов прямой задачи;
– оценки целевой функции прямой задачи.
II. Тогда структурный вид двойственной задачи будет иметь вид:
Например, дана задача линейного программирования
Таблица 32
| y1 | 1. |  Х1
| + х2 | < | B1 | |
| Y2 | 2. | 100х1 | + 150 х2 | < | B2 | |
| Y3 | 3. | -10х1 | + 40х2 | < | B3 | |
| Y4 | 4. | Х2 | < | B4 | ||
| Z |
Соответствующая ей двойственная задача будет иметь вид:
у1 > 0; у2 > 0; у3 > 0; у4 > 0;
Сравнивая результаты решения прямой и обратной задач видим, что последние симплексные таблицы прямой и двойственной задач содержат одни и те же данные, поэтому нет необходимости решать двойственную задачу.
1) 
Значение целевой функции прямой задачи совпадает со значением целевой функции двойственной. 
, т.е. значение целевой функции равно произведению ресурсов на двойственные переменные.
2) Значение переменных 
двойственной задачи совпадают со значениями элементов индексной строки, соответствующими остаточным переменным оптимального плана прямой задачи.
Пределы устойчивости оптимального решения при изменении коэффициентов целевой функции (Сj.)
При изменении ресурсов и плановых заданий в некоторых пределах структура оптимального решения и двойственные оценки сохраняются, а изменяются значения базисных переменных.
При изменении коэффициентов целевой функции в определенных пределах, решение сохраняется как по составу базисных переменных, так и по их значению, но значение целевой функци и и д войственны е оценки при этом меняют ся.
