Xreferat.com » Рефераты по математике » Решение оптимизационной задачи линейного программирования

Решение оптимизационной задачи линейного программирования

оптимальное решение находится по следующим формулам:

Х3 = 8 + 1*d

X6 = 0 – 0,5*d

X4 = 2,67 + 0,17*d

X5 = 5,33 + 0,33*d

E = 40 + 2,5*d

При составлении этих формул использовали коэффициенты из столбца остаточной переменной Х7 в последней симплекс-таблице. По содержательному смыслу эти формулы означают изменение времени работы токарного станка или станка-автомата над каждой из деталей в сутки при изменении запаса дефицитного ресурса. Формула E = 40 + 2,5*d означает изменение количества производимых комплектов деталей в сутки. Например, если время работы токарного станка станет не 8, а 6 часов в сутки, т.е. уменьшится на 2 часа (d=-2), то базисные переменные, а также целевая функция примут следующие значения:

Х3 = 6; Х6 = 1; Х4 = 2,33; Х5 = 4,67; Е = 35.

Все остальные переменные равны нулю (они не являются базисными).

Как видно, из-за уменьшения запаса времени работы токарного станка уменьшилось время работы этого станка над деталями типа 3, но вместе с тем увеличилось время работы станка-автомата над этими же деталями. Так как станок-автомат стал работать за смену 1 час над деталями третьего типа, то он уменьшил свое время работы над деталями типа 1 и 2 (ранее он отдавал все свое время на обработку только этих деталей). И, очевидно, что если время работы токарного станка уменьшилось, то уменьшится и количество комплектов деталей, производимых в сутки.

Таким образом, для исследования влияния изменения запаса ресурса на оптимальное решение нет необходимости решать задачу заново (с новым ограничением). Для нахождения оптимального решения достаточно по окончательной симплекс-таблице исходной задачи составить уравнения и подставить в них величину изменения запаса ресурса (значение d).

Изменение запасов ресурсов (т.е. правых частей ограничений) может привести к недопустимости оптимального базиса, найденного для исходной задачи. Так как на все переменные, используемые в задаче, накладывается требование неотрицательности, допустимый диапазон изменения запаса ресурса (т. е. диапазон допустимых значений d) находят из системы неравенств. Таким образом, допустимый диапазон изменения запаса времени работы токарного станка, при котором состав переменных в базисе оптимального решения не изменяется, находится из условия:

Х3 = 8 + 1*d > 0

Х6 = 0 – 0,5*d > 0

Х4 = 2,67 + 0,17*d > 0

Х5 = 5,33 + 0,33*d > 0

Решив данную систему неравенств, получим, что –8 < d < 0. Таким образом, базис оптимального решения будет состоять из переменных (Х3,Х6,Х4,Х5), если запас времени работы токарного станка будет находиться в диапазоне от 0 до 8 часов. Выход значения d за границы этого диапазона приведет к недопустимости найденного нами оптимального решения, так как минимум одна из базисных переменных окажется отрицательной, и для того, чтобы найти оптимальное решение, нам придется решать задачу заново.

Аналогично выполняется анализ на чувствительность к изменению запаса времени работы станка-автомата.


5.4. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ


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


ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ


Данная задача по своему содержанию является частично целочисленной. Переменные X1 , X2 , X3 , X4 , X5 , X6 ,обозначающие время работы определенного станка над деталями определенного типа, должны принимать целые значения. В то же время, переменные Х7 , Х8, обозначающие время простоя соответственно токарного станка и станка-автомата, могут принимать дробные значения. Для поиска оптимального целочисленного решения воспользуемся методом Гомори для частично целочисленных задач.


    1. МЕТОД ГОМОРИ ДЛЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ

Метод Гомори для нахождения целочисленного решения относится к большой группе методов, называемых методами отсечений. Эти методы основаны на введении в задачу дополнительных ограничений, позволяющих учесть требование целочисленности. Основная идея методов отсечений состоит в том, что на полученное оптимальное нецелочисленное решение накладывается дополнительное ограничение, которое делает это решение недопустимым, но и не отсекает ни одного целочисленного решения от области допустимых решений.

Ограничения составляются по финальной симплекс-таблице, в которой получено оптимальное нецелочисленное решение. При этом на первоначальную систему ограничений накладывается новое ограничение по следующей формуле:

L1*W1 + L2*W2 + … +Ln*Wn ≥ {Bi} , где

Aij, если Aij≥0 и Wj может быть дробной, (1)

({Bi}*Aij)/({Bi}-1), если Aij<0 и Wj может быть дробной, (2)

Lj = {Aij}, если {Aij}{Bi} и Wi должна быть целой, (3)

{Bi}*(1-{Aij})/(1-{Bi}), если {Aij}>{Bi} и Wi должна быть целой, (4)

j=1,…,n

где Wn – небазисная переменная;

Bi - базисная переменная, имеющая максимальную дробную часть ( дробная часть числа – это разность между этим числом и максимальным целым числом, не превосходящим его);

Aij – коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной;

Далее полученное ограничение приводится к стандартному виду:

-L1*W1 - L2*W2 - … -Ln*Wn + Sr = -{Bi}

где r – номер итерации алгоритма.

Здесь Sr – неотрицательная остаточная переменная, не имеющая никакого содержательного смысла; в оптимальном целочисленном решении эта переменная оказывается равной нулю.

В нашем случае переменная, имеющая максимальную дробную часть – это Х4 ({2,67}=0,67), она должна быть целой, переменные Х7 и Х8 могут быть дробными, переменные Х1 и Х2 должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение. Так как все коэффициенты на пересечениях базисной переменной Х4 и небазисных переменных Х1 , Х2 , Х7 , Х8 ≥ 0(0,44≥0, 0,11≥0, 0,17≥0), то коэффициенты при переменных Х1 и Х2 рассчитали по формуле (3): L1={0,44}=0,44, L2={0,11}=0,11, а коэффициенты при переменных Х7 и Х8 рассчитали по формуле (1): L3=0,17, L4=0,17. {В4}={Х4} = {2,67} = 0,67. Ограничение будет иметь вид:

0,44Х1 + 0,11Х2 + 0,17Х7 + 0,17Х8 ≥ 0,67

Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым ( если подставить Х1=0, Х2=0, Х7=0, Х8=0, - значения переменных, полученных в оптимальном нецелочисленном решении, то получим 0≥0,67 – неверно).

Приведя ограничение к стандартному виду, имеем:

-0,44Х1 - 0,11Х2 - 0,17Х7 - 0,17Х8 + Х9 = -0,67

Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х9:


БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

БР

E

1,67 1,67 0 0 0 0 2,5 2,5 0 40

X3

1 1 1 0 0 0 1 0 0 8

X6

-0,67 -0,67 0 0 0 1 -0,5 0,5 0 0

X4

0,44 0,11 0 1 0 0 0,17 0,17 0 2,67

Х5

0,22 0,55 0 0 1 0 0,33 0,33 0 5,33

X9

-0,44

-0,11 0 0 0 0 -0,17 -0,17 1 -0,67

Таблица 8. Симплекс-таблица №7.

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

Итак, переменная, исключаемая из базиса – это X9, т.к. ее значение –0,67 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X1, т.к. |1,67/(-0,44)|=3,8, |1,67/(-0,11)|=15,2, |2,5/(-0,17)|=14,7, 3,8 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. Получим новую симплекс-таблицу:

БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

БР

E

0 1,25 0 0 0 0 1,875 1,875 3,75 37,5

X3

0 0,75 1 0 0 0 0,625 -0,375 2,25 6,5

X6

0 -0,5 0 0 0 1 -0,25 0,75 -1,5 1

X4

0 0 0 1 0 0 0 0 1 2

Х5

0 0,5 0 0 1 0 0,25 0,25 0,5 5

X1

1 0,25 0 0 0 0 0,375 0,375 -2,25 1,5

Таблица 9. Симплекс-таблица №8.

Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменная Х1, переменные Х3, Х4 и Х5 уменьшили свое значение, а переменная Х6 увеличилась. Значение целевой функции уменьшилось и стало равно 37,5 , что объясняется тем, что оптимальное нецелочисленное решение было отсечено нашим дополнительным ограничением, и для поиска оптимального целочисленного решения мы ушли вглубь области допустимых решений, где значение целевой функции меньше оптимального. Наше решение все еще нецелочисленное, поэтому составим новое ограничение.

Переменная, имеющая максимальную дробную часть – это Х3 ({6,5}=0,5) (Х1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х3), она должна быть целой, переменные Х7 , Х8 и Х9 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х3 и небазисных переменных Х2 , Х7 , Х9 ≥ 0(0,75≥0, 0,625≥0, 2,25≥0), то коэффициент при переменной Х2 рассчитаем по формуле (3): L1={0,75}=0,75, коэффициенты при переменных Х7 и Х9 рассчитаем по формуле (1): L3=0,625, L4=2,25. Так как коэффициент на пересечении базисной переменной Х3 и небазисной переменной Х8<0, то коэффициент при переменной Х8 рассчитаем по формуле (2): L2=({6,5}*(-0,375))/({6,5}-1)=0,375. {В3}={Х3} = {6,5} = 0,5. Ограничение будет иметь вид:

0,25Х2 + 0,625Х7 + 0,375Х8 + 2,25Х9 ≥ 0,5

Или, после приведения к стандартному виду, получим:

-0,25Х2 – 0,625Х7 – 0,375Х8 – 2,25Х9 + Х10 = -0,5

Добавим это ограничение к нашей предыдущей симплекс-таблице:


БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

БР

E

0 1,25 0 0 0 0 1,875 1,875 3,75 0 37,5

Х3

0 0,75 1 0 0 0 0,625 -0,375 2,25 0 6,5

X6

0 -0,5 0 0 0 1 -0,25 0,75 -1,5 0 1

X4

0 0 0 1 0 0 0 0 1 0 2

X5

1 0,5 0 0 1 0 0,2 0,25 0,5 0 5

Х1

1 0,25 0 0 0 0 0,375 0,375 -2,25 0 1,5

X10

0 -0,25 0 0 0 0 -0,375 -0,375

-2,25

1 -0,5

Таблица 10. Симплекс-таблица №9.

Переменная, исключаемая из базиса – это X10, т.к. ее значение –0,5 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –2,25. Получим новую симплекс-таблицу:


БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

БР

E

0 0,83 0 0 0 0 1,25 1,25 0 1,67 36,67

Х3

0 0,5 1 0 0 0 0,25 -0,75 0 1 6

X6

0 -0,33 0 0 0 1 0 1 0 -0,67 1,33

X4

0 0,111 0 1 0 0 -0,17 -0,17 0 0,44 1,78

X5

0 0,444 0 0 1 0 0,17 0,17 0 0,22 4,89

Х1

1 0,5 0 0 0 0 0,75 0,75 0 -1 2

X9

0 0,11 0 0 0 0 0,17 0,17 1 -0,44 0,22

Таблица 11. Симплекс-таблица №10.

Решение все еще не целочисленное, поэтому переходим к следующей итерации. Переменная, имеющая максимальную дробную часть – это Х5 ({4,89}=0,89), она должна быть целой, переменные Х7 , Х8 и Х10 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х5 и небазисных переменных Х2, X7, X8,Х10≥0(0,44≥0, 0,17≥0, 0,22≥0), то коэффициент при переменной Х2 рассчитаем по формуле (3): L1={0,44}=0,44, коэффициенты при переменных Х7, Х9 и Х10 рассчитаем по формуле (1): L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} = 0,89. Ограничение будет иметь вид:

0,44Х2 + 0,17Х7 + 0,17Х8 + 0,22Х10 ≥ 0,89

Или, после приведения к стандартному виду, получим:

-0,44Х2 – 0,17Х7 – 0,17Х8 – 0,22Х10 + Х11 = -0,89

Добавим это ограничение к нашей предыдущей симплекс-таблице:

БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

Х11

БР

E

0 0,83 0 0 0 0 1,25 1,25 0 1,67 0 36,67

Х3

0 0,5 1 0 0 0 0,25 -0,75 0 1 0 6

X6

0 -0,3 0 0 0 1 0 1 0 -0,67 0 1,33

X4

0 0,11 0 1 0 0 -0,17 -0,17 0 0,44 0 1,78

X5

0 0,44 0 0 1 0 0,17 0,17 0 0,22 0 4,89

Х1

1 0,5 0 0 0 0 0,75 0,75 0 -1 0 2

Х9

0 0,11 0 0 0 0 0,17 0,17 1 -0,44 0 2

X11

0

-0,44

0 0 0 0 -0,17 -0,17 0 -0,22 1 -0,89

Таблица 12. Симплекс-таблица №11.

Переменная, исключаемая из базиса – это X11, т.к. ее значение –0,89 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9 – минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. После пересчетов получим получим новую симплекс-таблицу:


БП

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

Х11

БР

E

0 0 0 0 0 0 0,938 0,94 0 1,25 1,89 35

Х3

0 0 1 0 0 0 0,063 -0,938 0 0,75 1,125 5

X6

0 0 0 0 0 1 0,125 1,125 0 -0,5 -0,75 2

X4

0 0 0 1 0 0 -0,125 -0,125 0 0,5 -0,25 2

X5

0 0 0 0 1 0 0 0 0 0 1 4

Х1

1 0 0 0 0 0 0,563 0,563 0 -1,25 1,125 1

Х9

0 0 0 0 0 0 0,125 0,125 1 -0,5 0,25 0

X2

0 1 0 0 0 0 0,375 0,375 0 0,5 -2,25 2

Таблица 13. Симплекс-таблица №12.

Столбец решений не содержит отрицательных элементов, все переменные X1, X2, X3 , X4 , X5 , X6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно: (X1,X2,X3,X4,X5,X6)=(1,2,5,2,4,2), целевая функция при этом принимает максимальное значение: Е=35.


ЗАКЛЮЧЕНИЕ


После проведенных вычислений, решив задачу оптимизации, мы получили следующие результаты: оптимальный план работы станков состоит в том, чтобы токарный станок работал 1 час над деталями типа 1, 2 часа над деталями типа 2 и 5 часов над деталями типа 3 за смену; станок-автомат должен работать 2 часа над деталями типа 1 , 4 часа над деталями типа 2 и 2 часа над деталями типа 3 за смену. При этом количество комплектов деталей, выпускаемых цехом, будет максимально и равно 35.

В результате проведенного анализа на чувствительность к изменению запаса времени работы токарного станка получили, что если запас времени работы этого станка будет находиться в пределах от 0 до 8 часов, то базис оптимального решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5).


СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995.

2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.2. – Мн.: БГУИР, 1996.

3. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. - Мн.: БГУИР, 1997.

  1. Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1986.


УСЛОВНЫЕ СОКРАЩЕНИЯ


БР – базисное решение

БП – базисная переменная


Условие задачи. Приложение.


+-----------------------------------------------------------------------+

¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦Вид огр.¦Значение¦

+--------+--------+--------+--------+--------+--------+--------+--------¦

¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ E ¦ ¦

+--------+--------+--------+--------+--------+--------+--------+--------¦

¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ == ¦ 0.00¦

¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ == ¦ 0.00¦

¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ <= ¦ 8.00¦

¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ <= ¦ 8.00¦

+-----------------------------------------------------------------------+


Вывод промежуточных результатов оптимизации.


+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ 1¦ E ¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+---

¦ ¦ -W ¦ -4.00¦ 1.00¦ 2.00¦ -12.00¦ 3.00¦ 2.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ ¦ X9 ¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦

¦ ¦ X10¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 8.00¦

+----------------------------------------------------------------------------------------------------------+


Ведущий элемент находится в 4 столбце и 1 строке.


Вывод промежуточных результатов оптимизации.


+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 2¦ E ¦ 0.00¦ -1.50¦ -2.00¦ 0.00¦ -4.50¦ -2.00¦ 0.00¦ 0.00¦ 0.50¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+-

¦ ¦ -W ¦ 0.00¦ -1.00¦ 2.00¦ 0.00¦ -3.00¦ 2.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦ 0.00¦

¦ +----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

¦ ¦ X4 ¦ 0.33¦ -0.17¦ 0.00¦ 1.00¦ -0.50¦ 0.00¦ 0.00¦ 0.00¦ 0.17¦ 0.00¦ 0.00¦

¦ ¦ X10¦ 0.00¦ 1.00¦ -2.00¦ 0.00¦ 3.00¦ -2.00¦ 0.00¦ 0.00¦ -1.00¦ 1.00¦ 0.00¦

¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 8.00¦

¦ ¦ X8 ¦ -0.33¦ 0.17¦ 0.00¦ 0.00¦ 1.50¦ 1.00¦ 0.00¦ 1.00¦ -0.17¦ 0.00¦ 8.00¦

+----------------------------------------------------------------------------------------------------------+


Ведущий элемент находится в 5 столбце и 2 строке.


Вывод промежуточных результатов оптимизации.


+----------------------------------------------------------------------------------------------------------+

¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦ X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦

+--+----+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--

¦ 3¦ E ¦ 0.00¦ 0.00¦

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: