Лекция 10

Лекция 10

Двойственные задачи линейного программирования

Каждой задаче линейного программирования соответствует двойственная задача. Прямая задача отражает наиболее эффективное сочетание использования ресурсов, двойственная – оптимальную комбинацию оценок дефицитных ресурсов или двойственных оценок.

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

Имеются ресурсы В1, В2,….Вm – которые необходимо использовать для производства продукции х1, х2,….хn, причем стоимость продукции должна быть максимальной Z®max, а расход ресурсов не должен превышать их наличия.

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

………………………………..

Общее структурное представление:

При составлении двойственной задачи вводят двойственные переменные - y1, y2,….ym, Их количество равно количеству ограничений, которые являются оценками имеющихся ресурсов.

Математическая запись двойственной задачи будет иметь следующий вид:

………………………………..

,

где аij – технолого-экономические коэффициенты при неизвестных хj прямой задачи;

уi – двойственные оценки или скрытые цены ресурсов прямой задачи;

сj – оценки целевой функции прямой задачи.

Тогда структурный вид двойственной задачи будет иметь вид:

Например, дана задача линейного программирования

y1	1.	Х1	+ х2	<	1000	B1
Y2	2.	100х1	+ 150 х2	<	1200	B2
Y3	3.	-10х1	+ 40х2	<	100	B3
Y4	4.		Х2	<	300	B4
Z

Соответствующая ей двойственная задача будет иметь вид:

у1 > 0; у2 > 0; у3 > 0; у4 > 0;

Сравнивая результаты решения прямой и обратной задач видим, что последние симплексные таблицы прямой и двойственной задач содержат одни и те же данные, поэтому нет необходимости решать двойственную задачу.

1)  Значение целевой функции прямой задачи совпадает со значением целевой функции двойственной.

произведения ресурсов на двойственные переменные.

2)  Значение переменных двойственной задачи совпадают со значениями элементов индексной строки, соответствующими остаточным переменным оптимального плана прямой задачи.

Пределы устойчивости оптимального решения при изменении коэффициентов целевой функции (Сj.),

При изменении ресурсов и плановых заданий в некоторых пределах структура оптимального решения и двойственные оценки сохраняются, а изменяются значения базисных переменных.

При изменении коэффициентов целевой функции в определенных пределах, решение сохраняется как по составу базисных переменных, так и по их значению, но значение целевой функции и двойственные оценки при этом меняются.

Изменение коэффициентов в целевой функции при переменной, вошедшей в базисное решение.

При изменении коэффициента целевой функции на величину изменятся только элементы индексной строки:

Новое значение элементов индексной строки при небазисных переменных равно соответствующему значению элемента индексной строки плюс произведение коэффициента замещения, расположенного в строке соответствующей базисной переменной на величину изменения коэффициента. Как определить величину dc, т. е. диапазон изменения коэффициентов целевой функции.

Для этого делим соответствующие элементы индексной строки на коэффициенты замещения при базисной переменной (оценку которой в целевой функции меняем на величину dc ), результаты берем с обратным знаком. Из полученных частных выбираем min по модулю отрицательное и положительное частное. Это и будут допустимым диапазоном изменения оценки при базисной переменной в целевой функции.

Изменение коэффициента в целевой функции при переменной, не вошедшей в базисное решение.

Изменение коэффициента при небазисной переменной приводит к изменению только одного элемента индексной строки, соответствующей этой переменной., где - величина, на которую был изменен коэффициент .

При решении задач на max диапазон изменения коэффициента небазисной переменной не должен превышать соответствующего элемента по индексной строке: , так как в последней симплексной таблице все коэффициенты индексной строки должны быть > 0.