Прямая задача:
z = | 15 x1 | +10 x2 | +8 x3 | +2 x4 | +0 s1 | +0 s2 | +0 s3 | +0 s4 |
| (двойств. перемен.) |
| x1 | + 4 x2 | + x3 | +5 x4 | + s1 |
|
|
| =70 | (y1) |
| 3 x1 | + 2 x2 | +3 x3 | +5 x4 |
| + s2 |
|
| =80 | (y2) |
| 2 x1 | + 3 x2 |
| +4 x4 |
|
| - s3 |
| =25 | (y3) |
| x1 |
| + x3 | + x 4 |
|
|
| - s4 | =10 | (y4) |
| 2 x1 | - x2 | + x3 |
|
|
|
|
| =0 | (y5) |
| x1, | x2, | x3, | x4, | s1, | s2, | s3, | s4 | 0 |
|
Двойственная задача имеет следующий вид:
min ω=70y1 + 80y2 + 25y3 + 10y4 +0 y5
y1 + 3 y2 + 2 y3 + y4 + 2 y5 ≥15 (x1)
4 y1 + 2 y2 + 3 y3 - y5 ≥10 (x2)
y1 + 3 y2 + + y4 + y5 ≥8 (x3)
5 y1 + 5 y2 + 4 y3 + y4 ≥2 (x4)
y1 ≥0 (s1)
y2 ≥0 (s2)
- y3 ≥0 (s3)
- y4 ≥0 (s4)
В оптимальной таблице прямой задачи (табл. 6.9) базисными являются переменные x1, x2, x3, s2, s3. Значит, согласно соотношениям дополняющей нежесткости, соответствующие этим переменным ограничения-неравенства двойственной задачи в точке оптимума выполняются как равенства. Таким образом получаем следующую систему линейных уравнений.
x1≠0 y1 + 3y2 + 2y3 + y4 + 2y5 = 15 y1 + y4 + 2y5=15 x2≠0 4y1 + 2y2 + 3y3 -y5 = 10 4y1 - y5 =10
x3≠0 y1 + 3y2 + y4 + y5 = 8 y1 + y4 + y5 =8
s2≠0 y2 = 0
s3≠0 -y3 = 0
Решив полученную систему линейных уравнений, получим:
Основная теорема двойственности гласит: "Если прямая и двойственная задача имеют решения, то их значения совпадают". Убедимся в этом:
ω=70y1+80y2+25y3+10y4 = 704,25+10(-3,25) = 297,5--32,5 = 265 ω≡z.
Согласно теории двойственности двойственная переменная yi (i=1,..,m) определяет ценность i-го ресурса (оценку ресурса, shadow price, теневую цену) – величину, на которую изменится значение целевой функции при увеличении на единицу уровня запаса соответствующего ресурса (относительную ценность единицы дополнительного ресурса).
Значит, статус и ценность ресурсов таковы (табл. 6.10):
Таблица 6.10
№ ресурса | Наименование | Статус | Ценность |
1-й | Сахар | Дефицитный | 4,25 |
2-й | Мука | Недефицитный | 0 |
3-й | Дрожжи | Недефицитный | 0 |
4-й | Требование выполнения обязательных поставок | Дефицитный | -3,25 |
5-й | Соотношение объемов выпечки ватрушек, сушек и пирожков | Дефицитный | 7 |
Т.о., при изменении в некоторых пределах уровней запасов ресурсов, имеем:
-
каждый дополнительный мешок сахара (первый ресурс) позволит увеличить суммарную прибыль пекарни на 4,25 единиц стоимости;
-
изменение уровней запасов муки и сахара (второй и третий ресурсы) не приведут к изменению суммарной прибыли;
-
каждая дополнительная партия обязательных поставок ватрушек, пирожков и сдобных булочек согласно договорам с постоянными клиентами (четвертый ресурс) уменьшит суммарную прибыль пекарни на 3,25 единиц стоимости;
-
увеличение разности объемов выпечки ватрушек, сушек и пирожков 2 x 1 - x2 + x3 (пятый ресурс) на одну партию привело бы к увеличению суммарной прибыли пекарни на 7 единиц стоимости.
Отметим, что полученные аналитическим путем значения ценности ресурсов полностью совпадают с результатами Excel (см. рис. 6.5 – столбец Теневая цена отчета по устойчивости).
6.6. Диапазоны устойчивости
Определим допустимые пределы изменения уровней запасов ресурсов и цен продукции, при которых полученное решение остаётся оптимальным.
6.6.1. Изменение компонент вектора ограничений
6.6.1.1. Недефицитные ресурсы
Теоретические положения
Если в оптимальном решении дополнительная переменная s i-го ограничения базисная, то это ограничение является не связывающим (не активным в точке оптимума), а ресурс — недефицитным. В этом случае значение дополнительной базисной переменной дает диапазон изменения, в котором соответствующая компонента может
-
уменьшаться (в случае знака ограничения “”)
-
увеличиваться (в случае знака ограничения “”)
Пусть — значение соответствующей дополнительной переменной в точке оптимума. Тогда решение остается допустимым и оптимальным в диапазоне ,
где для ограничения типа “”,
для ограничения типа “”.
- Содержание
- 1. Порядок выполнения расчетно-графической работы
- Решение задачи симплекс-методом.2
- 2. Содержание отчета по расчетно-графической работе
- Планирование операции
- Содержательная постановка задачи.
- Решение задачи симплекс-методом.
- 3. Варианты заданий расчетно-графической работы
- 3.1. Задания на планирование операции
- 3.2. Задания на применение графического способа решения задач линейного программирования
- 4. Электронная таблица Microsoft Excel
- 4.1. Терминология Excel
- 4.3.6. Ввод чисел или текста
- Ввод текста
- Ввод чисел
- Ввод дат или времени суток
- 4.3.7. Формулы
- 5. Решение задачи линейного программирования средствами Microsoft Excel
- 5.1. Содержательная формулировка задачи Задача определения ассортимента выпуска продукции [3]
- 5.2. Математическая формулировка задачи
- Суммарное время Предельное время
- 5.3. Решение задачи с помощью Microsoft Excel
- Содержимое ячеек таблицы:
- 5.4. Нахождение оптимального решения с помощью процедуры поиска решения
- 5.5. Итоговые сообщения процедуры поиска решения
- 6. Постоптимальный анализ задач линейного программирования
- 6.1. Содержательная постановка задачи
- 6.2. Математическая модель
- 6.3. Решение с помощью Microsoft Excel
- 6.4. Решение задачи симплекс-методом
- 6.5. Определение ценности ресурсов
- Прямая задача:
- В нашей задаче:
- 6.6.1.2. Дефицитные ресурсы Теоретические сведения
- В нашей задаче:
- Теоретические сведения:
- В нашей задаче:
- 6.6.2. Изменение коэффициентов целевой функции
- 6.6.2.1. Небазисные переменные Теоретические сведения
- 6.6.2.2. Базисные переменные Теоретические сведения
- В нашей задаче:
- 6.6.3. Результаты решения и постоптимального анализа задачи
- 6.6.3.1. Оптимальное решение задачи
- 6.6.3.2. Диапазоны изменения уровня запасов ресурсов
- 6.6.3.3. Ценность ресурсов
- 6.6.3.4. Диапазоны изменения цен продукции
- 6.6.4. Некоторые особенности проведения постоптимального анализа задач средствами Excel
- 6.6.4.1. Наличие ограничений типа или
- 6.6.4.2. Наличие альтернативных оптимумов
- Список литературы
- Приложение а Основные положения теории двойственности а.1. Построение двойственных задач
- А.2. Основные теоремы двойственности
- А.3. Получение решения задачи по решению двойственной задачи