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

Нужен антирадар? На сайте Цифротека нашел интересный рейтинг антирадаров.

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

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

Устловие:
Считая, что все переменные являются положительными величинами, найти оптимальное решение симплекс-методом линейного программирования приведенных ниже задач (предполагается, что все переменные не отрицательны).
Задание.    
   L(x)=-16x1-x2+x3+5x4+5x5
    2x1+x2+x3=10
    -2x1+3x2-x4=6
    2x1+4x2-x5=8
   Решение.

   
   L(x) ->min (2 к/р)
   L(x) ->max (3 к/р)
   
   1. Нахождение минимума функции L(X):
   
   Так как нет базиса в 3-ем уравнение добавляем еще одну вспомогательную переменную x6
   
    2x1+x2+x3=10
    -2x1+3x2-x4=6
    2x1+4x2-x5+x6=8     x6->min
    L(x)->min
   Найдем опорное решение с помощью вспомогательной задачи Данцига (метод искусственного базиса):
    Lвсп=x6->min
   
   Нахождение опорного решения:
   
    2x1+x2+x3=10
    -2x1+3x2-x4=6
    2x1+4x2-x5+x6=8    
   
   Lвсп=x6->min

   Составим симплекс таблицу*:

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

Таблица2.
Xj0 B C
x1 x2 x3 x4 x5 x6
0 0 0 0 0 1
Bi/aij
x3 8 0 1.5 0 1 0 0.25 -0.25
x4 0 0 -3.5 0 0 1 0.75 -0.75
x2 2 0 0.5 1 0 0 -0.25 0.25
Lвсп= 0 Dj 0 0 0 0 0 -1

    Все маргиналы меньше или равны нулю. Оптимизация прошла успешно.
    Lвсп= 0 => Xопор=(0,2,8,0,0)T
    Найдем минимум функции L(x) с помощью симплекс-метода. Составим симплекс таблицу:
Таблица3.
Xj0 B C
x1 x2 x3 x4 x5
-16 -1 1 5 5
Bi/aij
x3 8 1 1.5 0 1 0 0.25
x4 0 5 -3.5 0 0 1 0.75
x2 2 -1 0.5 1 0 0 -0.25
L= 6 Dj -0.5 0 0 0 -0.75

    Все маргиналы меньше или равны нулю. Оптимизация прошла успешно.
    Lmin= 6
    X=(0,2,8,0,0)T
   2. Нахождение максимума функции L(X):
   L(x)=-16x1-x2+x3+5x4+5x5->max
   Или: L(x)=16x1+x2-x3-5x4-5x5->min
   
   Ограничения:
    2x1+x2+x3=10
    -2x1+3x2-x4=6
    2x1+4x2-x5=8
   Так как ограничения не изменились, то и опорное решение останется прежним: Xопор=(0,2,8,0,0)T
   Составим симплекс таблицу:
Таблица4.
Xj0 B C
x1 x2 x3 x4 x5
16 1 -1 -5 -5
Bi/aij
x3 8 -1 1.5 0 1 0 0.25 32
x4 0 -5 -3.5 0 0 1 0.75 0
x2 2 1 0.5 1 0 0 -0.25
L= -6 Dj 0.5 0 0 0 0.75

Таблица5.
Xj0 B C
x1 x2 x3 x4 x5
16 1 -1 -5 -5
Bi/aij
x3 8 -1 2/3 0 1 -1/3 0 3/4
x5 0 -5 14/3 0 0 4/3 -1 0
x2 2 1 -2/3 1 0 -1/3 0
L= -6 Dj 4 0 0 -1 0

Таблица6.
Xj0 B C
x1 x2 x3 x4 x5
16 1 -1 -5 -5
Bi/aij
x1 3 16 1 0 0.375 -0.125 0
x5 14 -5 0 0 1.75 0.75 1
x2 4 1 0 1 0.25 0.25 0
L= -18 Dj 0 0 -1.5 -0.5 0

    Все маргиналы меньше или равны нулю.
    Оптимизация успешно завершена.
    Найдено оптимальное решение:
    X*=(3,4,0,0,14)T
    Lmax=18.
   Ответ:
    Минимум:
    X*=(0,2,8,0,0)T
    Lmin= 6
    Максимум:
    X*=(3,4,0,0,14)T
    Lmax=18.

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