Математика 15

<

092613 1711 151 Математика 15

Задание 2.

 

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

 

092613 1711 152 Математика 15

 

Решение:

 

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

 

092613 1711 153 Математика 15

 

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

 

092613 1711 154 Математика 15

 

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

 

092613 1711 155 Математика 15

 

Если после минимизации функции 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 1711 156 Математика 15.

 

Перейдем к следующей таблице, руководствуясь следующими правилами.

1. Переменная из разрешающего столбца переходит в основные, а переменная из разрешающей строки в неосновные.

2. В столбцах соответствующих основным переменным, проставляем нули и единицы. 1 – против «своей» основной переменной, 0 – против «чужой» основной переменной, 0 – в последней строке для всех основных переменных.

3. Новую строку с тем же номером, что и разрешающая строка в предыдущей таблице, получаем делением разрешающей строки предыдущей таблицы на разрешающей элемент.

4. Остальные элементы вычисляем по правилу прямоугольника по формулам:

 

092613 1711 157 Математика 15, 092613 1711 158 Математика 15, где q – разрешающая строка, s – разрешающий столбец, aij – разрешающий элемент.


Шаг 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 

38/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 1711 159 Математика 15, при заданных ограничениях, достигает в точке с координатами 092613 1711 1510 Математика 15, 092613 1711 1511 Математика 15

<

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

WordPress: 21.95MB | MySQL:114 | 1,637sec