ЭММ. Вариант 5. Задача 1 Графический метод решения задач линейногопрограммирования. Составить математическую модель по условию задачи

• Название: Задача 1 Графический метод решения задач линейногопрограммирования. Составить математическую модель по условию задачи
• Дата: 01.02.2021
• Размер: 171.28 Kb.
• Имя файла: ЭММ. Вариант 5.docx
• Тип: Задача; #172996
• страница: 3 из 5

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x2	40	0	1	1/3	1/3	-1/3	0
x1	40	1	0	5/3	-1/3	4/3	0
x6	60	0	0	0	0	-1	1
F(X4)	4000	0	0	20/3	20/3	100/3	0

Оптимальный план можно записать так:

x₁ = 40, x₂ = 40, x₃ = 0

F(X) = 40*40 + 60*40 + 80*0 = 4000

Построим двойственную задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Расширенная матрица A.

1	4	3	200
1	1	2	80
1	1	2	140
40	60	80

Транспонированная матрица A^T.

1	1	1	40
4	1	1	60
3	2	2	80
200	80	140

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

Неравенства, соединенные стрелочками (↔), называются сопряженными.

y₁+y₂+y₃≥40

4y₁+y₂+y₃≥60

3y₁+2y₂+2y₃≥80

200y₁+80y₂+140y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	y1+y2+y3≥40
x2 ≥ 0	↔	4y1+y2+y3≥60
x3 ≥ 0	↔	3y1+2y2+2y3≥80
40x1+60x2+80x3 → max	↔	200y1+80y2+140y3 → min
x1+4x2+3x3≤200	↔	y1 ≥ 0
x1+x2+2x3≤80	↔	y2 ≥ 0
x1+x2+2x3≤140	↔	y3 ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

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

y₁=6²/₃, y₂=33¹/₃, y₃=0

Это же решение можно получить, применив теоремы двойственности.

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

A = (A2, A1, A6) =

4 1 0 1 1 0 1 1 1

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

D = A-1 =

1/3 -1/3 0 -1/3 4/3 0 0 -1 1

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

(60, 40, 0) x

1/3 -1/3 0 -1/3 4/3 0 0 -1 1

= (20/3;100/3;0)

Оптимальный план двойственной задачи равен:

y₁ = 6²/₃, y₂ = 33¹/₃, y₃ = 0

Z(Y) = 200*6²/₃+80*33¹/₃+140*0 = 4000

Экономический смысл всех переменных, участвующих в решении.

План производства			Остатки ресурсов, единиц
x1=40	x2=40	x3=0	x4=0	x5=0	x6=60
↨	↨	↨	↨	↨	↨
y4=0	y5=0	y6=62/3	y1=62/3	y2=331/3	y3=0
Превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции)			Объективно обусловленные оценки ресурсов (теневые, условные, скрытые цены ресурсов)

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

1*40 + 4*40 + 3*0 = 200 = 200

1*40 + 1*40 + 2*0 = 80 = 80

1*40 + 1*40 + 2*0 = 80 < 140

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁ ≠ 0).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂ ≠ 0).

3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₃ = 0.

Неиспользованный экономический резерв ресурса 3 составляет 60 (140-80).

Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).

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