Симплекс-метод решения задачи линейного программирования. Исенбаева Е.Н. - 8 стр.

UptoLike

ВУЗ: 

ИжГТУ им. Калашникова | Ижевск

Составители: 

Рубрика: 

8
Построение симплекс-таблиц продолжается до тех пор, пока не
будет получено оптимальное решение.
Замечание 1. Если для некоторой крайней точки
0
0
X
~
для
1 ≤ k ≤ m+n, то X
0
∈ R
n
- оптимальное решение задачи (1)-(3), причем
)X(Z)X
~
(Z
~
00
= .
Замечание 2. Пусть в некоторой крайней точке все симплексные
разности неотрицательные Δ
k
≥ 0 ( mn,1k += ) и существует такое, что
А
k
0
– небазисный вектор и Δ
k
0
= 0. Тогда максимум достигается по
крайней мере в двух в двух точках, т.е. имеет место альтернативный
оптимум.
Замечание 3. Решение двойственной задачи находится по по-
следней симплексной таблице. Последние m компонент вектора сим-
плексных разностей – оптимальное решение двойственной задачи.
Значение целевых функций прямой и двойственной задачи в опти-
мальных точках совпадают.
Замечание 4.
При решении задачи минимизации в базис вводит-
ся вектор с наибольшей положительной симплексной разностью [2].
3. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ
Найти максимальное значение линейной функции
Z = x
1
+ 2x
2
при ограничениях
x
1
+ x
2
≤ 0
-x
1
+ x
2
≤ 3 (17)
x
1
- x
2
≤ 3, x
1,
x
2
≥ 0.
Перейдем от исходной задачи к задаче с ограничениями типа
равенств. Введем вектор балансовых переменных y, размерность ко-
торого равна числу неравенств в системе ограничений: y = (x
3
, x
4
, x
5
).
Все балансовые переменные неотрицательные, в целевой функции им
соответствуют коэффициенты, равные нулю. Исходную задачу преоб-
разовали к виду
Z
~
= x
1
+ 2⋅x
2
+ 0⋅x
3
+ 0⋅x
4
+ 0⋅x
5
→ max
x
1
+ x
2
+ x
3
= 9
-x
1
+ x
2
+ x
4
= 3 (18)
x
1
- x
2
+ x
5
=3
x
1
, x
2
, x
3
, x
4
, x
5
≥ 0. 
       Построение симплекс-таблиц продолжается до тех пор, пока не
будет получено оптимальное решение.
                                                                ~
       Замечание 1. Если для некоторой крайней точки X 00 для
1 ≤ k ≤ m+n, то X0 ∈ Rn - оптимальное решение задачи (1)-(3), причем
~ ~
Z(X 0 ) = Z(X 0 ) .
       Замечание 2. Пусть в некоторой крайней точке все симплексные
разности неотрицательные Δk ≥ 0 ( k = 1, n + m ) и существует такое, что
Аk0 – небазисный вектор и Δk0 = 0. Тогда максимум достигается по
крайней мере в двух в двух точках, т.е. имеет место альтернативный
оптимум.
       Замечание 3. Решение двойственной задачи находится по по-
следней симплексной таблице. Последние m компонент вектора сим-
плексных разностей – оптимальное решение двойственной задачи.
Значение целевых функций прямой и двойственной задачи в опти-
мальных точках совпадают.
       Замечание 4. При решении задачи минимизации в базис вводит-
ся вектор с наибольшей положительной симплексной разностью [2].


      3. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
         ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

      Найти максимальное значение линейной функции
                              Z = x1 + 2x2
при ограничениях
                               x1 + x2 ≤ 0
                              -x1 + x2 ≤ 3                      (17)
                                x1 - x2 ≤ 3, x1,x2 ≥ 0.
      Перейдем от исходной задачи к задаче с ограничениями типа
равенств. Введем вектор балансовых переменных y, размерность ко-
торого равна числу неравенств в системе ограничений: y = (x3, x4, x5).
Все балансовые переменные неотрицательные, в целевой функции им
соответствуют коэффициенты, равные нулю. Исходную задачу преоб-
разовали к виду
                 ~
                 Z = x1 + 2⋅x2 + 0⋅x3 + 0⋅x4 + 0⋅x5 → max
                     x1 + x2 + x3                     =9
                    -x1 + x2            + x4          =3         (18)
                     x1 - x2                 + x5 =3

                          x1, x2, x3, x4, x5 ≥ 0.




                                    8

Страницы