Лекции по МОР. Конспект лекций по дисциплине методы оптимальных решений Направление подготовки 080100 Экономика

• Название: Конспект лекций по дисциплине методы оптимальных решений Направление подготовки 080100 Экономика
• Анкор: Лекции по МОР.docx
• Дата: 02.05.2017
• Размер: 1.02 Mb.
• Имя файла: Лекции по МОР.docx
• Тип: Конспект лекций; #6625
• страница: 13 из 16

Лекция 6. Метод искусственного базиса решения задачи линейного программирования

План.

6.1. Метод искусственного базиса.

6.2. Применение метода искусственного базиса.

6.1. Метод искусственного базиса

При решении задач симплексным методом необходимо, чтобы модель задачи была канонической и система ограничений была приведена к единичному неотрицательному базису. Встречаются случаи, когда эти преобразования оказываются громоздкими¹⁹.

Метод искусственного базиса дает возможность решать задачи, приведенные к каноническому виду, без предварительного нахождения опорного решения. Дана задача линейного программирования:



,

.

Из этой задачи составим вспомогательную задачу следующим образом:

1) систему ограничений вспомогательной задачи получаем из системы ограничений исходной, добавляя в каждое ограничение, не содержащее базисную переменную, искусственную базисную переменную;

2) целевая функция равна алгебраической сумме искусственных переменных, взятых с коэффициентом (-1);

3) условие неотрицательности распространяется на все переменные, в том числе и искусственные.

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



,

.

Система ограничений вспомогательной задачи приведена к единичному базису, поэтому она имеет решение:

= (0, 0, , 0, b₁, b₂, , b_n),

при этом  0.

Между оптимальным решением вспомогательной задачи и опорным решением исходной задачи существует зависимость:

1) если = 0 достигается при = (l₁, l₂, , l_n, 0, 0, , 0), то = (l₁, l₂, , l_n) является исходным опорным решением;

2) если max  0, то ограничения исходной задачи несовместны.

6.2. Применение метода искусственного базиса

Применение метода искусственного базиса рассмотрим на следующем примере²⁰:



при ограничениях:



Решение. Составим вспомогательную задачу:



при ограничениях:



Решим вспомогательную задачу симплексным методом:

сi	БП	0	0	0	-1	-1
		х1	х2	х3	х4	х5	bi
-1 -1	х4 х5	2 2	1 -1	1 2	1 0	0 1	1 2
j		-4	0	-3	0	0	-3
0 -1	х1 х5	1 0	½ -2	½ 1	½ -1	0 1	½ 1
j		0	2	-1	2	0	-1
0 0	х1 х3	1 0	3/2 -2	0 1	1 -1	½ 1	0 1
j		0	0	0	1	1	0

Решение вспомогательной задачи:

= (0, 0, 1, 0, 0), = 0,

Исходное опорное решение данной задачи:

= (0, 0, 1).

Проверим это решение на оптимальность:

сi	БП	4	-4	2
		х1	х2	х3	bi
4 2	х1 х3	1 0	3/2 -2	0 1	0 1
j		0	6	0	2

Ответ: = (0, 0, 1), = 2.