Липецкий государственный технический университет
Кафедра автоматизированных систем управления
ЛАБОРАТОРНАЯ РАБОТА №4
по Теории принятия решений
Использование искусственной переменной в программировании симплекс-методом
|
|
Студент |
|
|
|
Ключанских А.С |
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
АС-10 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
доцент |
|
|
|
Корнеев А.М. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2013
1. Задание
1. В исходную ЗЛП добавить новое ограничение таким образом, чтобы базисные переменные в соответствии с ограничениями на начальной итерации получили отрицательные значения.
2. Найти решение поставленной ЗЛП 3 способами:
-
Используя обычный симплекс-метод;
-
Используя двойственный симплекс – метод;
-
Ввести дополнительную неотрицательную искусственную переменную и найти решение с помощью симплекс-метода, пересчитывая на каждой итерации значение
.
2. Решение
Целевая функция
имеет вид:
.
А область ограничений задачи в стандартной форме имеет вид:
Найденное оптимальное решение в предыдущих практических работах:
.
Дополнительное ограничение:
,
где a1=1,
a2
= 1, b
= 2.
Таким образом,
дополнительное ограничение вид:
.
Приведем ограничения к канонической форме:
Среди переменных
задачи можно выделить базисные переменные:
и не базисные:
.
1) Используем обычный симплекс-метод для решения задачи:
Итерация 0
|
Базис |
B |
|
|
|
|
|
|
|
|
|
4 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
10 |
-1 |
2 |
0 |
1 |
0 |
0 |
0 |
|
|
14 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
|
|
56 |
7 |
2 |
0 |
0 |
0 |
1 |
0 |
|
|
-2 |
-1 |
-1 |
0 |
0 |
0 |
0 |
1 |
|
|
0 |
-5 |
-10 |
0 |
0 |
0 |
0 |
0 |
В симплекс-таблице
есть отрицательные коэффициенты строки
,
значит данное базисное решение не
оптимально.
Ведущий столбец: x2.
Ведущая строка: x3.
Итерация 1
|
Базис |
B |
|
|
|
|
|
|
|
|
|
4 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
2 |
1 |
0 |
-2 |
1 |
0 |
0 |
0 |
|
|
6 |
2 |
0 |
-2 |
0 |
1 |
0 |
0 |
|
|
48 |
9 |
0 |
-2 |
0 |
0 |
1 |
0 |
|
|
2 |
-2 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
40 |
-15 |
0 |
10 |
0 |
0 |
0 |
0 |
В симплекс-таблице
есть отрицательные коэффициенты строки
,
значит данное базисное решение не
оптимально.
Ведущий столбец: x1.
Ведущая строка: x4.
Итерация 2
|
Базис |
B |
|
|
|
|
|
|
|
|
|
6 |
0 |
1 |
-1 |
1 |
0 |
0 |
0 |
|
|
2 |
1 |
0 |
-2 |
1 |
0 |
0 |
0 |
|
|
2 |
0 |
0 |
2 |
-2 |
1 |
0 |
0 |
|
|
30 |
0 |
0 |
16 |
-9 |
0 |
1 |
0 |
|
|
6 |
0 |
0 |
-3 |
2 |
0 |
0 |
1 |
|
|
70 |
0 |
0 |
-20 |
15 |
0 |
0 |
0 |
В симплекс-таблице
есть отрицательные коэффициенты строки
,
значит данное базисное решение не
оптимально.
Ведущий столбец: x3.
Ведущая строка: x6.