Лабораторная работа №3 Вариант 10
.doc
Липецкий государственный технический университет
Кафедра автоматизированных систем управления
ЛАБОРАТОРНАЯ РАБОТА №3
по Теории принятия решений
Двойственный симплекс-метод
|
Студент |
|
|
|
Ключанских А.С |
|
||||||||
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
Группа |
|
АС-10 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
||||||||
|
Принял |
|
|
|
|
|
||||||||
|
доцент |
|
|
|
Корнеев А.М. |
|
||||||||
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
Липецк 2013
1. Задание
Проанализировать имеющуюся линейную модель на чувствительность, используя двойственный симплекс - метод.
Порядок выполнения работы:
1. Исходными данными взять результаты, посчитанные симплекс-методом.
2. Ввести новые ограничения и реализовать двойственный симплекс-метод.
3. Оценить активные, пассивные и избыточные ограничения.
2. Решение
Целевая функция имеет вид: .
А область ограничений задачи в стандартной форме имеет вид:
Найденное оптимальное решение в предыдущих практических работах:
.
Симплекс-таблица, полученная в практической работе №3 имеет вид:
Базис |
B |
||||||
6 |
1 |
0 |
0 |
0 |
-1/7 |
1/7 |
|
3 |
0 |
0 |
1 |
0 |
-9/14 |
1/7 |
|
2 |
0 |
0 |
0 |
1 |
-8/7 |
1/7 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
|
c |
0 |
0 |
0 |
0 |
30/7 |
5/7 |
1) Введем дополнительное ограничение:
Уравнение прямой имеет вид:
7x1-x2=7
Ограничение имеет вид:
7x1-x2<=7
Представим в канонической форме:
7x1-x2+x7=7
Выразим x2: x2=7-x5.
Выразим x1: x1=6+x5-x6
Формируем новую строку симплекс таблицы:
x5-x6+x7=-.
Базис |
B |
|
|
|
|
|
|
|
|
6 |
1 |
0 |
0 |
0 |
-1/7 |
1/7 |
0 |
|
3 |
0 |
0 |
1 |
0 |
-9/14 |
1/7 |
0 |
|
2 |
0 |
0 |
0 |
1 |
-8/7 |
1/7 |
0 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
0 |
|
-7/2 |
0 |
0 |
0 |
0 |
13/4 |
-1 |
1 |
|
100 |
0 |
0 |
0 |
0 |
30/7 |
5/7 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных есть отрицательные элементы, значит данное базисное решение не оптимально.
Выбираем переменную, которая выводится из базиса. Находим строку, у которой самый большой по модулю отрицательный элемент .
Ведущая строка: .
Выбираем переменную, которая вводится в базис. Для элементов ведущей строки, которые меньше 0, находим .
Ведущий столбец: .
Перестроим симплекс-таблицу по правилам обычного симплекс-метода:
Базис |
B |
|||||||
11/2 |
1 |
0 |
0 |
0 |
9/28 |
0 |
1/7 |
|
7/2 |
0 |
0 |
1 |
0 |
-5/28 |
0 |
1/7 |
|
5/2 |
0 |
0 |
0 |
1 |
-19/28 |
0 |
1/7 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
0 |
|
7/2 |
0 |
0 |
0 |
0 |
-13/4 |
1 |
-1 |
|
195/2 |
0 |
0 |
0 |
0 |
185/28 |
0 |
5/7 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных нет отрицательных элементов, значит данное базисное решение оптимально.
Значение целевой функции ухудшилось по сравнению с исходным оптимальным решением, следовательно, дополнительное ограничение АКТИВНОЕ.
2) Введем дополнительное ограничение:
Уравнение прямой имеет вид:
x1-5x2=5
Ограничение имеет вид:
x1-5x2<=5
Представим в канонической форме:
x1-5x2+x7=5
Выразим x2: x2=7-x5.
Выразим x1: x1=6+x5-x6
Формируем новую строку симплекс таблицы:
x5-x6+x7=25
Базис |
B |
|||||||
6 |
1 |
0 |
0 |
0 |
-1/7 |
1/7 |
0 |
|
3 |
0 |
0 |
1 |
0 |
-9/14 |
1/7 |
0 |
|
2 |
0 |
0 |
0 |
1 |
-8/7 |
1/7 |
0 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
0 |
|
25 |
0 |
0 |
0 |
0 |
20/7 |
-5/14 |
1 |
|
100 |
0 |
0 |
0 |
0 |
30/7 |
5/7 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных нет отрицательных элементов, значит данное базисное решение оптимально.
Значение целевой функции не изменилось по сравнению с исходным оптимальным решением. С помощью графического способа можно убедиться, что оптимальное решение не принадлежит прямой, являющейся дополнительным ограничением, следовательно, дополнительное ограничение НЕАКТИВНОЕ.
3) Введем дополнительное ограничение:
Уравнение прямой имеет вид:
7x1-x2=
Ограничение имеет вид:
7x1-x2<=
Представим в канонической форме:
7x1-x2+x7=
Выразим x2: x2=7-x5.
Выразим x1: x1=6+x5-x6
Формируем новую строку симплекс таблицы:
x5-x6+x7=0
Базис |
B |
|||||||
6 |
1 |
0 |
0 |
0 |
-1/7 |
1/7 |
0 |
|
3 |
0 |
0 |
1 |
0 |
-9/14 |
1/7 |
0 |
|
2 |
0 |
0 |
0 |
1 |
-8/7 |
1/7 |
0 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
15/4 |
-1 |
1 |
|
100 |
0 |
0 |
0 |
0 |
30/7 |
5/7 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице в столбце базисных переменных нет отрицательных элементов, значит данное базисное решение оптимально.
Значение целевой функции не изменилось по сравнению с исходным оптимальным решением. С помощью графического способа можно убедиться, что оптимальное решение лежит на прямой, являющейся дополнительным ограничением, следовательно, дополнительное ограничение ИЗБЫТОЧНОЕ.