Развлекательный портал - Ramnek.RU


Вернуться к оглавлению>>

Экстримальные задачи непрерывного типа.



Устловие:
Считая, что все переменные являются положительными величинами, найти оптимальное решение симплекс-методом линейного программирования приведенных ниже задач (предполагается, что все переменные не отрицательны).


Задание.    
   L(x)=2x1-x2-x4
    x1-2x2+x3=10
    2x1+x2+2x4>=18
    3x1+2x2+x4<=36
   Решение.
  Приведем к каноническому виду:
    x1-2x2+x3=10
    2x1+x2+2x4-x5=18
    3x1+2x2+x4+x6=36
  Т.к. во-втором ограничение нет базиса, то введем ещё одну переменную x7. Найдем начальный базис по методу вспомогательной задачи Данцига.
  Введем вспомоготельную функцию Lвсп(х)=x7->min.
  Решим вспомогательную задачу симплекс методом.
Поиск min. Lвсп(x)->min.


Таблица1.
Xj0 B C
x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 0 1
Bi/aij
x3 10 0 1 -2 1 0 0 0 0
x7 18 1 2 1 0 2 -1 0 1 9
x6 36 0 3 2 0 1 0 1 0 36
Lвсп= 18 Dj 2 1 0 2 -1 0 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={9,36}=9
    Сделаем стобец x4 базисом.
    Для этого прибавим к строке 3 (-0.5) строки 2.
    Строку 2 умножим на 0.5.
Таблица2.
Xj0 B C
x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 0 1
Bi/aij
x3 10 0 1 -2 1 0 0 0 0
x4 9 0 1 0.5 0 1 -0.5 0 0.5
x6 27 0 2 1.5 0 0 0.5 1 -0.5
Lвсп= 0 Dj 0 0 0 0 0 0 -1

    Все маргиналы меньше или равны нулю. Оптимизация прошла успешно.
    Поскольку Lвсп= 0 => x7=0.
    Xопор=(0,0,10,9,0,27)T
   Теперь найдем симплекс методом минимум функции L(x)=2x1-x2-x4->min при следующих ограничениях:
    x1-2x2+x3=10
    x1+0.5x2+x4-0.5x5=9
    2x1+1.5x2+0.5x6=27
Таблица3.
Xj0 B C
x1 x2 x3 x4 x5 x6
2 -1 0 -1 0 0
Bi/aij
x3 10 0 1 -2 1 0 0 0
x4 9 -1 1 0.5 0 1 -0.5 0 18
x6 27 0 2 1.5 0 0 0.5 1 18
L= -9 Dj -3 0.5 0 0 0.5 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={18,18}=18
    Сделаем стобец x2 базисом.
    К строке 1 прибавим (4) строки 2.
    К строке 3 прибавим (-3) строки 2.
    Строку 2 умножим на 2.
Таблица4.
Xj0 B C
x1 x2 x3 x4 x5 x6
2 -1 0 -1 0 0
Bi/aij
x3 46 0 5 0 1 4 -2 0
x2 18 -1 2 1 0 2 -1 0
x6 0 0 -1 0 0 -3 2 1 0
L= -18 Dj -4 0 0 -1 1 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={0}=0
    Сделаем стобец x5 базисом.
    К строке 1 прибавим строку 3.
       К строке 2 прибавим (0.5) строки 3.
    Строку 3 умножим на 0.5.
Таблица5.
Xj0 B C
x1 x2 x3 x4 x5 x6
2 -1 0 -1 0 0
Bi/aij
x3 46 0 4 0 1 1 0 1 46
x2 18 -1 1.5 1 0 0.5 0 0.5 36
x5 0 0 -0.5 0 0 -1.5 1 0.5
L= -18 Dj -3.5 0 0 0.5 0 -0.5

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={46,36}=36
    Сделаем стобец x4 базисом.
    К строке 1 прибавим (-2) строки 2.
    К строке 3 прибавим (3) строки 2.
    Строку 2 умножим на 2.
Таблица6.
Xj0 B C
x1 x2 x3 x4 x5 x6
2 -1 0 -1 0 0
Bi/aij
x3 10 0 1 -2 1 0 0 0
x4 36 -1 3 2 0 1 0 1
x5 54 0 4 3 0 0 1 2
L= -36 Dj -5 -1 0 0 0 -1

    Все маргиналы меньше или равны нулю.
    Оптимизация успешно завершена.
    Найдено оптимальное решение:
    Минимум:
    X*=(0,0,10,36)T
    L*= -36.


Найдем максимум: max(L(x))=-min(-(L(x)), при следующих ограничениях:
    x1-2x2+x3=10
    2x1+x2+2x4>=18
    3x1+2x2+x4<=36
   Решение.

  Приведем к каноническому виду:

    x1-2x2+x3=10
    2x1+x2+2x4-x5=18
    3x1+2x2+x4+x6=36
  Т.к. во-втором ограничение нет базиса, то введем ещё одну переменную x7. Найдем начальный базис по методу вспомогательной задачи Данцига.
  Введем вспомоготельную функцию Lвсп(х)=x7->min.
  Решим вспомогательную задачу симплекс методом.
Таблица7.
Xj0 B C
x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 0 1
Bi/aij
x3 10 0 1 -2 1 0 0 0 0
x7 18 1 2 1 0 2 -1 0 1 9
x6 36 0 3 2 0 1 0 1 0 36
Lвсп= 18 Dj 2 1 0 2 -1 0 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={9,36}=9
    Сделаем стобец x4 базисом.
    Для этого прибавим к строке 3 (-0.5) строки 2.
    Строку 2 умножим на 0.5.
Таблица8.
Xj0 B C
x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 0 1
Bi/aij
x3 10 0 1 -2 1 0 0 0 0
x4 9 0 1 0.5 0 1 -0.5 0 0.5
x6 27 0 2 1.5 0 0 0.5 1 -0.5
Lвсп= 0 Dj 0 0 0 0 0 0 -1

    Все маргиналы меньше или равны нулю. Оптимизация прошла успешно.
    Поскольку Lвсп= 0 => x7=0.
    Xопор=(0,0,10,9,0,27)T
   Теперь найдем симплекс методом максимум функции L(x)=2x1-x2-x4->max при следующих ограничениях:
    x1-2x2+x3=10
    x1+0.5x2+x4-0.5x5=9
    2x1+1.5x2+0.5x6=27
    max(L(x))=-min(-(L(x))

Таблица9.
Xj0 B C
x1 x2 x3 x4 x5 x6
-2 1 0 1 0 0
Bi/aij
x3 10 0 1 -2 1 0 0 0 10
x4 9 1 1 0.5 0 1 -0.5 0 9
x6 27 0 2 1.5 0 0 0.5 1 13.5
L= 9 Dj 3 -0.5 0 0 -0.5 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={10,9,13.5}=9
    Сделаем стобец x1 базисом.
    К строке 1 прибавим (-1) строки 2.
    К строке 3 прибавим (-2) строки 2.
Таблица10.
Xj0 B C
x1 x2 x3 x4 x5 x6
-2 1 0 1 0 0
Bi/aij
x3 1 0 0 -2.5 1 -1 0.5 0 2
x1 9 -2 1 0.5 0 1 -0.5 0
x6 9 0 0 0.5 0 -2 1.5 1 6
L= -18 Dj 0 -2 0 -3 1 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={2,6}=2
    Сделаем стобец x5 базисом.
    К строке 2 прибавим строку 1.
    К строке 3 прибавим (-3) строки 1.
    Строку 1 умножим на 2.
Таблица11.
Xj0 B C
x1 x2 x3 x4 x5 x6
-2 1 0 1 0 0
Bi/aij
x5 2 0 0 -5 2 -2 1 0
x1 10 -2 1 -2 1 0 0 0
x6 6 0 0 8 -3 1 0 1 0.75
L= -20 Dj 0 3 -2 -1 0 0

    Т.к. не все маргиналы меньше или равны нулю, то продолжаем оптимизацию.
    min(Bi/aij)={0.75}=0.75
    Сделаем стобец x2 базисом.
    К строке 1 прибавим (0.625) строки 3.
    К строке 2 прибавим (0.25) строки 3.
    Строку 3 поделим на 8.
Таблица12.
Xj0 B C
x1 x2 x3 x4 x5 x6
-2 1 0 1 0 0
Bi/aij
x5 5.75 0 0 0 0.125 -1.375 1 0.625
x1 11.5 -2 1 0 0.25 0.25 0 0.25
x2 0.75 1 0 1 -0.375 0.125 0 0.125
L= -22.25 Dj 0 0 -0.5 -1.5 0 -0.5

    Все маргиналы меньше или равны нулю.
    Оптимизация успешно завершена.
    Найдено оптимальное решение:

    Максимум:
    X*=(11.5,0.75,0,0)T
    L*= 22.25.

   Ответ:
    Минимум:
    X*=(0,0,10,36)T
    L*= -36.
    Максимум:
    X*=(11.5,0.75,0,0)T
    L*= 22.25.

главная страница / развлечения / образование / картинки из символов /
All contents © copyright 2008 by ramnek