Лабораторная работа №5 Решение злп методом искусственного базиса. Двойственность в злп.

Цель работы.

Изучение метода искусственного базиса решения ЗЛП и построение математических моделей двойственных задач.

Содержание лабораторной работы

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

Задание на лабораторную работу:

Вариант 6.

Ход работы.

Система уравнений имеет непредпочтительный вид (отсутствуют переменные в предпочтительном виде), следовательно, применяем метод искусственного базиса, вводя переменные W1 и W2. Таким образом, процесс решения ЗЛП сведется к решению М-задачи, получаем:

Составим симплексную таблицу для М-задачи.

						Х1			Х2			Х3			Х4			W1			W2			Симплексные отношения
БП	Сб	А0		8			-6			-5			2			-м			-м
W1	-м	16		1			4			-1			1			1			0			16/1=16, min
W1	-м	20		4			-6			3			-7			0			1
Zj-Cj			0		-8			6			5			-2			0			0
			-36м		-5м			2м			-2м			6м
Х4	2	16		1			4			-1			1			1			0			16/1=16
W2	-м	132		11			22			-4			0			7			1			132/11=12, min
Zj-Cj			32		-6			14			3			0			2			0
			-132м		-11м			-22м			4м						-6м
Х4	2	4		0			2			-7/11			1			4/11			-1/11
Х1	8	12		1			2			-4/11			0			7/11			1/11
Zj-Cj			104		0			26			9/11			0			64/11			6/11
																	м			м

Начальное решение не является оптимальным, т.к. в строке оценок содержатся отрицательные, следовательно, решение можно улучшить. Определим переменную, которая войдет в список базисных: разрешающий столбец х₄, т.к. 2+6м максимальная по модулю оценка среди отрицательных. Разрешающую строку найдем через симплексные отношения min{16}=16. Первая строка разрешающая. Элемент А_1,4=1разрешающий.

Аналогично для второй итерации, разрешающий элемент выберем А_2,1.

Полученное решениеx₂= {12, 0, 0, 4, 0, 0} оптимально, т.к. среди оценок нет отрицательных.

Значение ЦФ:

Найдем оптимальное решение исходной задачи, используя табличный процессор Excel.

Рисунок 1 - Форма для ввода условий

Выбираем наибольший положительный элемент в ячейках С2:G3. Он равен 4 и находится в ячейке D3, значит столбец D разрешающий. Выберем разрешающий элемент D3=4.

Составив новую симплекс-таблицу, получаем

Рисунок 2 –Результат второй итерации

Улучшая результат итераций (т.к. не все оценки отрицательны), получим:

Рисунок 3- Конечный результат итераций

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

х₁=12, х₄=4.

.

Двойственность в ЗЛП.

Задание.

Вид технологической операции	Нормы затрат времени для производства кабеля			Общий фонд времени
	Типа А	Типа B
Получение проволоки	8	3	28
Изоляция	6	7	27
Скручивание	6	2	22
Освинцовывание	0	1	22
Испытание	7	8	16
Доход от реализации	13	10

Экономико-математическая модель исходной задачи:

Введем переменные x₁ и x₂, составим ЦФ и систему ограничений:

→max

Рисунок 3- Решение исходной задачи

Рисунок 4- Отчет по результатам

Экономико-математическая модель двойственной задачи:

Введем переменные y_i(i=1,5), составим ЦФ и систему ограничений:

, (y_j0, y_j =1,5)

Решение двойственной задачи можно найти в отчете Поиска решений – отчете по устойчивости. Теневые цены ресурсов равны0;0;0;0;1.86.

Рисунок 5 - Отчет по устойчивости

ОперацияO₅ имеет отличную от нуля оценку – он используется в оптимальном плане полностью, является дефицитным, сдерживает рост целевой функции.

Остальные ресурсы используются не полностью, поэтому имеют нулевые двойственные оценки, не влияют на план выпуска продукции.

Общая стоимость используемых ресурсов при выпуске 2 продуктов типаА составит:

Ответы на контрольные вопросы.

1. В чем заключается сущность двойственности в линейном программировании?

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

2. Как по решению исходной найти решение двойственной задачи? (и наоборот)

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Решение двойственной задачи можно найти в отчете Поиска решений – отчете по устойчивости.

3. Какие задачи линейного программирования относятся к симметричным и несимметричным, в чем их отличие?

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