Решение оптимизационных задач средствами EXCEL




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


На основании признака оптимальности в базис вводится вектор Ак , давший минимальную отрицательную величину симплекс разности:

                                     

 

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аr, который дает минимальное положительное оценочное отношение

                       

         

Строка Аr

называется направляющей, столбец Ак и элемент ar к – направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

                   

        

 а элементы  i-й  строки – по формулам:

             

 

Значения нового опорного плана рассчитываются по формулам:

  

 для  i = r ;         
 

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

Примечание. Для использования приведенной процедуры к минимизации линейной функции  f (x1,x2,…, xn) следует искать максимум  - f (x1,x2,…, xn), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

Пример.

Получить решение по модели: 

 

Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных  x 3   и x4:

                                                           

               

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

Номер

   

В

2

3

0

0

симплекс-

Базис

план

Q

таблицы

А3

0

300

1

3

1

0

100

0

А4

0

150

1

1

0

1

150

f(x)

0

-2

-3

0

0

А2

3

100

1/3

1

1/3

0

300

I

А4

0

50

2/3

0

-1/3

1

75

f(x)

300

-1

0

1

0

А2

3

75

0

1

1/2

-1/2

II

А1

2

75

1

0

-1/2

3/2

f(x)

375

0

0

1/2

3/2

В симплекс-таблице II получен оптимальный опорный план,  поскольку все симплекс-разности (оценки)

j. Оптимальные значения переменных равны: x1*=75,  x2* =75 (основные переменные), x3*  =0, x4*  =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.

Таким образом, в рассмотренной выше задаче об оптимальном использовании ограниченных ресурсов, оптимальная производственная программа состоит в выпуске 75ед. изделий первого вида и 75ед. изделий второго вида. С этой программой связана максимальная выручка от реализации готовой продукции – 375 у.е.




Содержание  Назад  Вперед