Высшая Математика Решение задач и примеров - OnLine
./ Главная /Решение задачи линейного программирования, ШАГ-1/ШАГ-2/Финиш >



Задача:
Найти значения переменных x1...x6, при которых функция:
Q = 2x3+x4+x6
принимает максимальное значение, при условии следующих ограничений :
x1+x2+x3+x4+x5+x6 = 100    (1)
2x1+x2-4x3-2x4 -x6 = 0    (2)
x2-2x3 +2x5-x6 = 0    (3)
x1, x2, x3, x4, x5, x6 ≥ 0


Шаг:1
Ищем в системе ограничений базисные переменные.
Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу.

Введем по одной искусственной неотрицательной переменной ri в каждое уравнение системы ограничений.
Получим следующую систему ограничений,

x1+x2+x3+x4+x5+x6+r1 = 100    (1)
2x1+x2-4x3-2x4 -x6 +r2 = 0    (2)
x2-2x3 +2x5-x6 +r3 = 0    (3)
x1, x2, x3, x4, x5, x6, r1, r2, r3 ≥ 0

с базисными переменными r1,r2,r3.

Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2,r3). Для этого сформируем вспомогательную целевую функцию :
G = r1+r2+r3
и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.

Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:
  - вычтем из функции G уравнение 1
  - вычтем из функции G уравнение 2
  - вычтем из функции G уравнение 3

Функция G примет вид :
G = -3x1-3x2+5x3+x4-3x5+x6+100

Теперь мы можем сформировать начальную симплекс-таблицу.


Шаг:2
Начальная симплекс-таблица
БПx1x2x3x4x5x6r1r2r3РешениеОтношение
r1 1 1 1 1 1 1 1 0 0 100
100/1=100
r2 2 1 -4 -2 0 -1 0 1 0 0 --
r3 0 1 -2 0 2 -1 0 0 1 0
0/2=0
Q 0 0 2 1 0 1 0 0 0 0 --
G -3 -3 5 1 -3 1 0 0 0 -100 --


Итерация 1 Как производится итерация?...
БПx1x2x3x4x5x6r1r2РешениеОтношение
r1 1
1
2
 2 1 0
3
2
 1 0 100
100/1=100
r2 2 1 -4 -2 0 -1 0 1 0
0/2=0
x5 0
1
2
 -1 0 1
-1
2
 0 0 0 --
Q 0 0 2 1 0 1 0 0 0 --
G -3
-3
2
 2 1 0
-1
2
 0 0 -100 --


Итерация 2 Как производится итерация?...
БПx1x2x3x4x5x6r1РешениеОтношение
r1 0 0 4 2 0 2 1 100
100/4=25
x1 1
1
2
 -2 -1 0
-1
2
 0 0 --
x5 0
1
2
 -1 0 1
-1
2
 0 0 --
Q 0 0 2 1 0 1 0 0 --
G 0 0 -4 -2 0 -2 0 -100 --


Итерация 2-a Как производится итерация?...
БПx1x2x3x4x5x6РешениеОтношение
x3 0 0 1
1
2
 0
1
2
 25 --
x1 1
1
2
 0 0 0
1
2
 50 --
x5 0
1
2
 0
1
2
 1 0 25 --
Q 0 0 0 0 0 0 -50 --
G 0 0 0 0 0 0 0 --

Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"

Итерация 3 Как производится итерация?...
БПx1x2x3x4x5x6РешениеОтношение
x3 0 0 1
1
2
 0
1
2
 25 --
x1 1
1
2
 0 0 0
1
2
 50 --
x5 0
1
2
 0
1
2
 1 0 25 --
Q 0 0 0 0 0 0 -50 --


Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Ответ:
Оптимальное значение функции Q(x)=50
достигается в точке с координатами:
x1=50
x2=0
x3=25
x4=0
x5=25
x6=0

Однако коэффициент при свободной переменной x2 обратился в ноль ,и если мы ее будем изменять, то функция цели не изменится, а решение будет другим, т.е. получим еще одно оптимальное решение, которое будет называться альтернативным. Для его нахождения введем в базис переменную x2 выбрав в качестве направляющего соответствующий столбец.

Итерация 3-a Как производится итерация?...
БПx1x2x3x4x5x6РешениеОтношение
x3 0 0 1
1
2
 0
1
2
 25 --
x1 1
1
2
 0 0 0
1
2
 50
50/
1
2
=100
x5 0
1
2
 0
1
2
 1 0 25
25/
1
2
=50
Q 0 0 0 0 0 0 -50 --


Итерация 4 Как производится итерация?...
БПx1x2x3x4x5x6РешениеОтношение
x3 0 0 1
1
2
 0
1
2
 25 --
x1 1 0 0
-1
2
 -1
1
2
 25 --
x2 0 1 0 1 2 0 50 --
Q 0 0 0 0 0 0 -50 --


Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Ответ:
Оптимальное значение функции Q(x)=50
достигается в точке с координатами:
x1=25
x2=50
x3=25
x4=0
x5=0
x6=0



на ввод размеров...
к списку решаемых задач...