Математика 17

<

092613 1917 171 Математика 17Решить симлекс-методом задачу линейного программирования

092613 1917 172 Математика 17

 

Решение:

Приведем задачу к каноническому виду. Так как в первое ограничение имеет вид «≤», то введем в него дополнительную переменную x3>0 со знаком «+». Так как второе и третье ограничения имеют вид «≥», то введем в них дополнительные переменные x4>0 и x5>0 со знаком «-». Преобразуем неравенства в равенства и запишем задачу в каноническом виде.

092613 1917 173 Математика 17

Второе и третье уравнения дают отрицательную компоненту в базисное решение. Введем в них искусственные переменные y1 и y2 с тем же знаком, что и свободный член.

092613 1917 174 Математика 17

 

Целевая функция преобразуется в вид

092613 1917 175 Математика 17

Если после минимизации функции M ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции M ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет. На практике ищут не минимум M-функции, а максимум –M-функции.

Составим первую симплексную таблицу, в которой переменные x3, y1, y2 – основные. Предпоследняя строка заполняется коэффициентами линейной функции с противоположным знаком. Последняя строка получается умножением M-функции на сумму строк y1 и y2.

 

Базис 

Переменные 

Свободный член 

Оценочное отношение 

x1

x2

x3

x4

x5

y1

y2

x3

1  

2  

1

0  

0  

0  

0  

10  

10/1=10

y1

2  

-3  

0  

-1  

0  

1  

0  

14  

14/2=7

y2

3  

4  

0  

0  

-1  

0  

1  

2  

2/3

F 

3  

7  

0  

0  

0  

0  

0  

0  

 

M 

-5  

-1  

0  

1  

1  

0  

0  

-16  

 

 

Разрешающим столбцом является столбец переменной x1, здесь находится наибольший по модулю отрицательный элемент в целевой функции. Разрешающей строкой является строка переменной y2, где находится самое меньшее оценочное отношение. На пересечении разрешающих строки и столбца стоит разрешающий элемент 092613 1917 176 Математика 17.

 

Перейдем к следующей таблице.


Шаг 1

 

Базис

Переменные

Свободный член

Оценочное отношение

x1

x2

x3

x4

x5

y1

x3

0

2/3

1  

0  

1/3 

0  

28/3

28/3:1/3=28

y1

0 

-17/3 

0  

-1  

2/3 

1  

38/3 

28/3:2/3=19

x1

1

4/3

0  

0  

-1/3 

0  

2/3

 

F

0

3

0  

0  

1 

0  

-2

 

M

0

17/3

0  

1  

<

-2/3 

0  

-38/3

 

 

 

Шаг 2

 

Базис

Переменные

Свободный член

Оценочное отношение

x1

x2

x3

x4

x5

x3

0  

7/2 

1  

1/2 

0  

3  

3:7/2=6/7 

x5

0  

-17/2 

0  

-3/2 

1  

19  

 

x1

1  

-3/2 

0  

-1/2 

0  

7  

 

F

0  

23/2 

0  

3/2 

0  

-21  

 

M

0  

0  

0  

0  

0  

0  

 

 

 

Получено оптимальное решение вспомогательной задачи — найден максимум –M-функции, т.к. в строке целевой функции нет отрицательных коэффициентов. Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Строка M нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке F.

Шаг 3

 

Базис

Переменные

Свободный член

Оценочное отношение

x1

x2

x3

x4

x5

x3

0  

7/2

1  

1/2 

0  

3  

3:7/2=6/7 

x5

0  

-17/2 

0  

-3/2 

1  

19  

 

x1

1  

-3/2 

0  

-1/2 

0  

7  

 

F

0  

23/2 

0  

3/2 

0  

-21  

 


Шаг 4

 

Базис

Переменные

Свободный член

Оценочное отношение

x1

x2

x3

x4

x5

x2

0  

1  

2/7  

1/7 

0  

6/7 

 

x5

0  

0  

17/7 

-2/7 

1  

184/7 

 

x1

1  

0  

3/7

-2/7 

0  

58/7  

 

F

0  

0  

-23/7 

-1/7 

0  

-216/7  

 

 

 

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

Ответ: Наибольшее значение функция 092613 1917 177 Математика 17, при заданных ограничениях, достигает в точке с координатами 092613 1917 178 Математика 17, 092613 1917 179 Математика 17

<

Комментирование закрыто.

MAXCACHE: 0.95MB/0.00040 sec

WordPress: 23.51MB | MySQL:116 | 1,712sec