Лабораторная работа №2 Вариант 10
.docxЛипецкий государственный технический университет
Кафедра автоматизированных систем управления
ЛАБОРАТОРНАЯ РАБОТА №2
по Теории принятия решений
Симплекс-метод решения задачи линейного программирования
|
Студент |
|
|
|
Ключанских А.С |
|
|||||||||
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
|||||||||
|
Группа |
|
АС-10 |
|
|
|
|||||||||
|
|
|
|
|
|
|
|||||||||
|
Принял |
|
|
|
|
|
|||||||||
|
доцент |
|
|
|
Корнеев А.М. |
|
|||||||||
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
Липецк 2013
1. Задание
1. Решить задачу линейного программирования используя итерации симплекс-метода.
2. Построение исходной симплекс-таблицы.
3. Проверка полученного базисного плана на оптимальность по условию оптимальности.
4. Осуществление перехода к новому базисному плану.
5. Выполнение процедуры замены базиса.
6. Реализация алгоритма симплекс-метода.
2. Решение
Целевая функция имеет вид: .
А область ограничений задачи в стандартной форме имеет вид:
Найденное оптимальное решение в предыдущих практических работах:
.
Приведем исходную задачу к канонической форме:
Среди переменных задачи можно выделить базисные переменные: и не базисные: .
Итерация 0
Базис |
B |
||||||
4 |
-1 |
1 |
1 |
0 |
0 |
0 |
|
10 |
-1 |
2 |
0 |
1 |
0 |
0 |
|
14 |
0 |
2 |
0 |
0 |
1 |
0 |
|
56 |
7 |
2 |
0 |
0 |
0 |
1 |
|
0 |
-5 |
-10 |
0 |
0 |
0 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице есть отрицательные коэффициенты строки , значит данное ДБР не оптимально.
Для перехода к новому базисному плану из числа небазисных переменных с отрицательными значениями выбирается переменная, которая вводится в базис, это переменная , которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Ведущий столбец: .
Выбираем переменную, которая выводится из базиса. Для элементов ведущего столбца, которые больше 0, находим .
Ведущая строка: .
Ведущий элемент: 1.
Воспользуемся следующими формулами:
Определим элементы строки
Определим элементы строки
Определим элементы строки
Элементы строки получаются делением ведущей строки на ведущий элемент:
Определим элементы строки f(x):
f(x)=0-
Получили:
Итерация 1
Базис |
B |
||||||
2 |
1 |
0 |
-2 |
1 |
0 |
0 |
|
6 |
2 |
0 |
-2 |
0 |
1 |
0 |
|
48 |
9 |
0 |
-2 |
0 |
0 |
1 |
|
4 |
-1 |
1 |
1 |
0 |
0 |
0 |
|
40 |
-15 |
0 |
10 |
0 |
0 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице есть отрицательные коэффициенты строки , значит данное ДБР не оптимально.
Для перехода к новому базисному плану из числа небазисных переменных с отрицательными значениями выбирается переменная, которая вводится в базис, это переменная , которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Ведущий столбец: .
Выбираем переменную, которая выводится из базиса. Для элементов ведущего столбца, которые больше 0, находим .
Ведущая строка: .
Ведущий элемент: 1.
Выполняя аналогичные действия итерации 0,получим:
Итерация 2
Базис |
B |
||||||
2 |
1 |
0 |
-2 |
1 |
0 |
0 |
|
2 |
0 |
0 |
2 |
-2 |
1 |
0 |
|
30 |
0 |
0 |
16 |
-9 |
0 |
1 |
|
6 |
0 |
1 |
-1 |
1 |
0 |
0 |
|
70 |
0 |
0 |
-20 |
15 |
0 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице есть отрицательные коэффициенты строки , значит данное ДБР не оптимально.
Для перехода к новому базисному плану из числа небазисных переменных с отрицательными значениями выбирается переменная, которая вводится в базис, это переменная , которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Ведущий столбец: .
Выбираем переменную, которая выводится из базиса. Для элементов ведущего столбца, которые больше 0, находим .
Ведущая строка: .
Ведущий элемент: 2.
Выполняя действия, аналогичные предыдущим итерациям, получим:
Итерация 3
Базис |
B |
||||||
4 |
1 |
0 |
0 |
-1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
-1 |
1/2 |
0 |
|
14 |
0 |
0 |
0 |
7 |
-8 |
1 |
|
7 |
0 |
1 |
0 |
0 |
1/2 |
0 |
|
90 |
0 |
0 |
0 |
-5 |
10 |
0 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице есть отрицательные коэффициенты строки , значит данное ДБР не оптимально.
Для перехода к новому базисному плану из числа небазисных переменных с отрицательными значениями выбирается переменная, которая вводится в базис, это переменная , которой соответствует наибольшая по абсолютной величине отрицательная оценка.
Ведущий столбец: .
Выбираем переменную, которая выводится из базиса. Для элементов ведущего столбца, которые больше 0, находим .
Ведущая строка: .
Ведущий элемент: 7.
Выполняя действия, аналогичные предыдущим итерациям, получим:
Итерация 4
Базис |
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 |
|
100 |
0 |
0 |
0 |
0 |
30/7 |
5/7 |
Проверим полученный базисный план на оптимальность по условию оптимальности: В симплекс-таблице все коэффициенты строки неотрицательные, значит данное ДБР оптимально.
Таким образом, .