Задачи математического программирования

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

3. Замена базиса. Для перехода к следующей симплексной таблице (следующему опорному плану с большим значением целевой функции) делаем шаг модифицированного жорданова исклю

чения с разрешающим элементом arl, при котором базисная переменная xr становится свободной и одновременно свободная переменная xi становится базисной.

3.1 на месте разрешающего элемента ставится 1 и делится на разрешающий элемент;

3.2 остальные элементы разрешающего столбца меняют знак на противоположный и делятся на разрешающий элемент;

3.3 остальные элементы разрешающей строки делятся на разрешающий элемент;

3.4. все остальные элементы симплексной таблицы вычисляются по формуле:

3.5. элементы правого столбца и нижней строки пересчитываются по тому же принципу, что и элементы в центральной части таблицы.

Симплексная таблица, рассчитанная по алгоритму:

Таблица 2.

 

-х1

-х3

 

х2 =

0,067

0,3

6

х4 =

0,57

-0,67

1,1

х5 =

2,17

-0,67

11

f(x) =

-3,27

1,3

72,6

Следующим разрешающим столбцом будет столбец х1, а разрешающей строкой – х4. Далее действуем по тому же алгоритму.

Таблица 3.

 

-х4

-х3

1

х2 =

-0,1

0,24

5,87

х1 =

1,75

-1,17

1,03

х5 =

-3,8

1,88

5,8

f(x) =

5,7

-2,5

35,06

Следующим разрешающим столбцом будет столбец х5, а разрешающей строкой – х3. Далее действуем по тому же алгоритму.

Таблица 4.

 

-х4

-х5

1

х2 =

0,39

-0,13

4,4

х1 =

-0,61

0,6

6,19

Х3 =

-2

0,53

1,3

f(x) =

0,64

1,3

36,08

Конечная симплексная таблица:

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

Таким образом, в точке x1 = 4, x2 = 6, x3 = 1,3, x4 = 0, x5 = 0 целевая функция принимает максимальное значение f(x) = 36.

При этом переменным, которые стоят в верхней строке, в базисном решении присваивается значение 0 – это свободные переменные. Каждая из переменных, стоящая в левом столбце, приравнивается к числу, записанному в правом столбце той же самой строки – это базисные переменные.

Постановка двойственной задачи ЛП. Определить значение двойственных оценок можно следующим образом. если некоторый i-тый ресурс используется не полностью, т.е. имеется резерв, значит дополнительная переменная в ограничении для данного ресурса будет больше нуля. Очевидно, что при увеличении общего машинного времени не произошло бы увеличение целевой функции. Следовательно, машинное время не влияет на прибыль и для третьего ограничения двойственная переменная y3 = 0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка данного ограничения равна нулю.

В данном примере оба вида сырья использовались полностью, поэтому их дополнительные переменные равны нулю (в итоговой симплексной таблице переменные х3 и х4 являются свободными, значит х3 = х4 = 0). Если ресурс использовался полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и, следовательно, на величину целевой функции. Значение двойственной оценки при этом находится в симплекс-таблице на пересечении строки целевой функции со столбцом данной дополнительной переменной.

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

Таблица 4.

Исходная задача ЛП

Двойственная задача ЛП

Математическая постановка

Обозначения и интерпретация параметров задачи

xj, j = - количество производимой продукции j-го вида;

f(x) – общая прибыль от реализации продукции

yi, i = - стоимость единицы i-го ресурса;

- стоимость всех имеющихся ресурсов

Экономическая интерпретаци язадачи

Сколько и какой продукции необходимо произвести, чтобы пр заданных стоимостях cj, j = еддиницы продукции и размерах имеющихся ресурсов bi, i = максимизировать общую прибыль?

Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных их количествах bi, i = и величинах стоимости единицы продукции cj, j = минимизировать общую стоимость затрат?

Результаты решения

Результирующая симплекс-таблица

 

-х4

-х5

1

х2 =

4,4

х1 =

6,19

Х3 =

1,3

f(x) =

0,64

1,3

36,08

Основные переменные

х1 = 6,19

х2 = 4,4

дополнительные переменные

х3 = 1,3

х4 = 0

х5 = 0

Дополнительные переменные

y4 = 0

y5 = 0

основные переменные

y1 = 0,64

y2 = 1,3

y3 = 0

Интерпретация дополнительных переменных

xn+1, …., xn+m – неиспользованное (резервное) количество соответствующего ресурса (при наличие резервного ресурса соответствующая двойственная переменная навна 0)

ym+1, …, ym+n – насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции (если какая-либо из основных переменных исходной задачи равна 0)

Страница:  1  2  3  4  5  6  7  8  9  10  11  12 


Другие рефераты на тему «Математика»:

Поиск рефератов

Последние рефераты раздела

Copyright © 2010-2024 - www.refsru.com - рефераты, курсовые и дипломные работы