Освоение симплекс-метода решения задач ЛП. Целевая функция и ограничения модели в стандартной форме

Страницы работы

4 страницы (Word-файл)

Фрагмент текста работы

Лабораторная работа № 5

Цель работы: Освоить симплекс-метод решения задач ЛП.

Постановка задачи: решить задачу линейного программирования maxF=3x1+3x2 симплекс-методом при условиях x1-4x2≤4, 3x1+2x2≤6, -x1+x2≤1, x1+2x2≥2 (-x1+x2≤3, 4x1+3x2≤20)

Ход работы:

Сперва представим целевую функцию и ограничения модели в стандартной форме:

                    z-3x1-3x2                     =0         (целевая функция)

(ограничения).

 
                                 

x1-4x2+s1                    =4

3x1+ 2x2    +s2             =6

-x1+x2             +s3        =1

x1 +2x2                 +s4   =2    

Как отмечалось ранее, в качестве начального пробного решения используется решение системы уравнений, в которой две (6—4) переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка x1=x2=0 сразу же приводит к следующему результату: s1=4, s2=6, s3=1, s4=2  (т.е. решению, соответствующему точке C на графике из предыдущей лабораторной). Полученные результаты удобно представить в виде таблицы 1.

                        Таблица 1. Исходная симплекс-таблица

Базисные переменные

Z

X1

X2

S1

S2

S3

S4

Решение   b

Z

1

-3

-3

0

0

0

0

0

S1

0

1

-4

1

0

0

0

4

S2

0

3

2

0

1

0

0

6

S3

0

-1

1

0

0

1

0

1

S4

0

1

2

0

0

0

1

2

Анализируя z-уравнение, нетрудно заметить, что обе небазисные переменные x1 и x2, равные нулю, имеют отрицательные коэффициенты. Так как мы имеем дело с задачей максимизации, значение z может быть улучшено при увеличении как x1, так и x2 . Однако всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента (в z-уравнении), так как в этом случае оптимум достигается быстрее. Применяя условие оптимальности к таблице 1, выберем в качестве переменной, включаемой в базис, переменную x1 . Переменная должна быть выбрана из совокупности базисных переменных s1, s2, s3, s4. Процедура выбора исключаемой переменной предполагает проверку условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та из переменных текущего базиса, которая первой обращается в нуль при увеличении включаемой переменной x2 вплоть до значения, соответствующего смежной экстремальной точке. Симплекс-таблица 2, получаемая после проверки условия допустимости (т. е. после вычисления соответствующих отношений и определения исключаемой переменной) приведена ниже.

                              Таблица 2. Определение ведущего элемента

Базисные переменные

X1

X2

S1

S2

S3

S4

Решение

b

Отношения

z

-3

-3

0

0

0

0

0

0

S1

1

-4

1

0

0

0

4

4/1

S2

3

2

3

1

0

0

6

6/2

S3

-1

1

0

0

1

0

1

1/1

S4

1

1

0

0

0

1

2

8/2

Из таблицы видно что строка S2 является ведущей, а столбец X1 является ведущим столбцом, из этого следует, что 3 это ведущий элемент.

После того как определены включаемая и исключаемая переменные (с использованием условий оптимальности и допустимости), следующая итерация (поиск нового базисного решения) осуществляется методом исключения переменных, илиметодом Гаусса — Жордана.

Процессизменения базиса включает вычислительные процедуры двух типов.

Тип 1 (формирование ведущего уравнения).

Новая ведущая строка = Предыдущая ведущая строка/ Ведущий элемент

Тип 2 (формирование всех остальных уравнений, включая z-уравнение).

Новое уравнение = Предыдущее уравнение—

          Коэффициент

         ведущего столбца

  —    предыдущего             (Новая ведущая строка).  

         уравнения

Процедура 1 приводит к следующим изменениям исходной симплекс-таблицы (таблица 3).

Таблица 3. Новая ведущая строка.

Базисные переменные

X1

X2

S1

S2

S3

S4

Решение   b

Z

S1

X1

1

2/3

0

1/3

0

0

6/2=3

S3

S4

Чтобы составить новую симплекс-таблицу, выполним необходимые вычислительные процедуры типа 2.

1. z-уравнение.

Предыдущее z-уравнение:  (-3   -3   0   0    0    0    0  )

-(-3) × Новая ведущая строка:  ( 3    2    0   1    0    0    9  )

=Новое z-уравнение:        ( 0   -1    0   1    0    0    9  )

2. s1-уравнение

Предыдущее s1-уравнение: (1    -4    1    0    0    0    4)

-(1) × Новая ведущая строка:  (-1    -2/3    0    -1/3    0    0    -3)

= Новое s1-уравнение:       (0    -14/3    1    -1/3    0    0    1)

3. s3-уравнение.

Предыдущее s3-уравнение: (-1    1    0    0    1    0    1)

-(-1) × Новая ведущая строка:    (1    2/3    0    1/3    0    0    3) 

= Новое s3-уравнение:         (0    5/3    0    1/3    1    0    4)

4. s4-уравнение.

Предыдущее s3-уравнение: (1    1    0    0    0    1    2)

-(1) × Новая ведущая строка:    (-1    -2/3    0    -1/3    0    0    -3) 

= Новое s3-уравнение:         (0    1/3    0    -1/3    0    1    -1)

Результат вычислений с помощью рассмотренных операций представлен в таблице 4.

Таблица 4. Промежуточное решение.

Базисные переменные

X1

X2

S1

S2

S3

S4

Реше- ние b

Отно-шения

Z

0

-1

0

1

0

0

12

S1

0

-14/3

1

-1/3

0

0

1

1/(-14/3)

X1

1

2/3

0

1/3

0

0

3

3/(2/3)

S3

0

5/3

0

1/3

1

0

4

4/(5/3)

S4

0

1/3

0

-1/3

0

1

-1

-1/(1/3)

В новом решении x2=1 и x1=0 (точка A на рисунке предыдущей лабараторной). Из таблицы 4 следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать x2, так как коэффициент при этой переменной в z-уравнении равен -1. Исходя из условия допустимости, определяем, что исключаемой переменной будет s1. Отношения, фигурирующие в правой части таблицы 4, показывают, что в новом базисном решении значение включаемой переменной x2 будет равно -3/14. Оптимальное решение представлено в симплекс-таблице 5 (результирующие значения были найдены по аналогии с предыдущей таблицей).

Таблица 5. Оптимальное решение.

Базисные переменные

X1

X2

S1

S2

S3

S4

Решение b

Z

0

1

-3/14

1/14

0

0

3/14

X2

0

0

3/14

15/14

0

0

3

X1

1

0

1/7

-0,43

0

0

1,3

S3

0

0

0,12

10,7

0

0

4,2

S4

0

0

9/14

-0,54

0

0

5/14

В новом базисном решении x1=1,3 и x2=3 (точка В на рисунке

Похожие материалы

Информация о работе