Найдем наименьшее значение линейной функции
|
L =
|
- x1
|
+ 12 x2
|
-6 x4
|
+ 5 x5
|
|
|
|
x1
|
+
|
25
|
x2
|
|
|
|
|
-13
|
x4
|
+
|
4
|
x5
|
=
|
16
|
|
3
|
x1
|
+
|
7
|
x2
|
+
|
2
|
x3
|
+
|
|
x4
|
|
-8
|
x5
|
=
|
4
|
|
-4
|
x1
|
+
|
12
|
x2
|
+
|
5
|
x3
|
|
|
|
+
|
6
|
x5
|
=
|
21
|
Умножим коэффициенты исходной функции на -1.
|
G =
|
x1
|
-12 x2
|
+ 6 x4
|
-5 x5
|
Будем искать наибольшее значение получившийся функции.
|
Нам необходимо найти начальное опорное (абсолютно произвольное) решение
для функции G, которое бы удовлетворяло системе наложенных ограничений.
Далее, применяя симплекс таблицы, мы будем получать решения, при которых
значение функции будет, как минимум, не убывать. И так до тех пор, пока не
достигнем оптимально решения, при котором функция достигает своего максимума.
Если, конечно, рассматриваемая нами линейная функция обладаем максимальным
значением при заданной системе ограничений. Перед применением симплекс таблиц,
необходимо преобразовать систему линейных ограничений и рассматриваемую нами
функцию G к вполне определенному виду.
|
Свободные члены системы ограничений неотрицательные.
|
Определимся с начальным опорным решением.
|
Наличие единичного базиса в системе ограничений позволяет легко найти начальное
опорное решение. Рассмотрим подробнее:
|
В уравнении 1 нет переменной, которая входила бы в него с коэффициентом 1 ,
а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к
данному уравнению искусственную переменную r1. Очевидно, переменная r1
будет являться базисной переменной, т.к. входит в уравнение 1 с коэффициентом 1
и не входит в оставшиеся уравнения системы ограничений.
|
В уравнении 2 нет переменной, которая входила бы в него с коэффициентом 1 , а
в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к
данному уравнению искусственную переменную r2. Переменная r2 будет
являться базисной переменной.
|
В уравнении 3 нет переменной, которая входила бы в него с коэффициентом 1 ,
а в остальные уравнения системы входила бы с коэффициентом ноль. Добавим к
данному уравнению искусственную переменную r3. Переменная r3 будет
являться базисной переменной.
|
|
|
|
x1
|
+
|
25
|
x2
|
|
|
|
|
-13
|
x4
|
+
|
4
|
x5
|
+
|
|
r1
|
|
|
|
|
|
|
=
|
16
|
|
3
|
x1
|
+
|
7
|
x2
|
+
|
2
|
x3
|
+
|
|
x4
|
|
-8
|
x5
|
|
|
|
+
|
|
r2
|
|
|
|
=
|
4
|
|
-4
|
x1
|
+
|
12
|
x2
|
+
|
5
|
x3
|
|
|
|
+
|
6
|
x5
|
|
|
|
|
|
|
+
|
|
r3
|
=
|
21
|
Переменные , которые не являются базисными называются свободными переменными.
Приравняв свободные переменные нулю в получившийся системе ограничений мы
получим начальное решение.
|
X нач = ( 0 , 0 , 0 , 0 , 0 , 16 , 4 , 21 )
Для нахождения начального опорного решения функции G, сначала придется
решить вспомогательную задачу.
Введем в рассмотрение вспомогательную функцию W :
|
Найдем наибольшее значение функции W.
Схема решения вспомогательной задачи абсолютно аналогична схеме описанной выше.
Есть только одно исключение: вспомогательная задача всегда имеет решение.
В процессе решения данной задачи возможны два варианта.
Если максимальное значение вспомогательной функции W равно нулю,
т.е. все искусственные переменные обращаются в нуль - это будет свидетельствовать
о том, что мы нашли начальное опорное решение функции G.
В противном случае, не существует решений, удовлетворяющих системе ограничений
нашей задачи.
|
Функция G и вспомогательная функция W не должны содержать базисных переменных.
|
Из уравнения 1 последней системы выразим r1 и подставим в выражение функции W, получим
|
W =
|
-16
|
+ x1
|
+ 25 x2
|
-13 x4
|
+ 4 x5
|
- r2
|
- r3
|
Из уравнения 2 последней системы выразим r2 и подставим в выражение функции W, получим
|
W =
|
-20
|
+ 4 x1
|
+ 32 x2
|
+ 2 x3
|
-12 x4
|
-4 x5
|
- r3
|
Из уравнения 3 последней системы выразим r3 и подставим в выражение функции W, получим
|
W =
|
-41
|
+ 44 x2
|
+ 7 x3
|
-12 x4
|
+ 2 x5
|
Значение функции W для начального решения: W (X нач) = -41
|
Вернемся к рассмотрению функции G.
|
G =
|
x1
|
-12 x2
|
+ 6 x4
|
-5 x5
|
Функция G и вспомогательная функция W не содержат базисных переменных.
|
Для составления начальной симплекс таблицы мы выполнили все условия.
|
При составлении исходной симплекс таблицы, коэффициенты при переменных функции
G записываются с противоположными знаками, а свободный член со своим знаком.
Для функции W правило аналогичное.
|
За ведущий выберем столбец 2 , так как -44 наименьший элемент в W строке.
Элемент W строки, принадлежащий столбцу свободных членов не рассматриваем.
|
|
Скачать 0.98 Mb.