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

Заключение
В данной курсовой работе была решена задача о выборе оптимальной технологии при помощи инструментария линейного программирования, а именно симплекс-метода.
По результатам можно сказать, что для достижения максимума производительности наиболее оптимальна технология номер 1, в сочетании с технологией номер 3.
При их использовании в полученных часовых отрезках достигается максимум целевой функции 23400, что означает получение конечной продукции в максимально возможных объемах при имеющихся ресурсах.
Подобные метод принятия управленческих решений удобен и эффективен при решении задач, которые можно выразить с помощью линейного программирования, поскольку позволяет найти оптимальный вариант при помощи математического инструментария при огромном многообразии вариантов решения.
 

...

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3
ПОСТАНОВКА ЗАДАЧИ И ИСХОДНЫЕ ДАННЫЕ 4
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 5
ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ 8
МЕТОД ПЕРЕБОРА 10
СИМПЛЕКС-МЕТОД 11
МЕТОД РЕШЕНИЯ ПРИ ПОМОЩИ EXCEL 15
ПРАКТИЧЕСКАЯ ЧАСТЬ 15
РЕШЕНИЕ ЗАДАЧИ 15
ЗАКЛЮЧЕНИЕ 24
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 25

Введение
Деятельность отдельных людей и коллективов часто связана с принятием таких решений, которые позволяют получить в некотором смысле наилучший (оптимальный) результат.
При этом в каждой конкретной ситуации необходимо считаться с реальными условиями. Так, предприятие не может обеспечить максимальную прибыль без учета реальных запасов сырья, его стоимости, конъюнктуры рынка и целого ряда других факторов.
Задачами подобного типа занимается математическая дисциплина, которая называется “Исследование операций”. В рамках этой дисциплины рассматриваются математические модели различных управленческих, экономических и инженерных задач оптимизации. Построение и анализ таких моделей позволяет найти оптимум в той или иной оптимизационной (управленческой, экономической или инженерной) задаче в ус ловиях, когда существуют какие-либо ограничения. При этом обычно подразумевается использование математических методов для моделирования и анализа возникающих ситуаций. В 1938 г. перед проф. Ленинградского государственного университета Л. В. Канторовичем была поставлена задача: как наилучшим образом распределить работу восьми станков фанерного треста при условии, что известна производительность каждого станка по любому из пяти видов обрабатываемых материалов? Он нашел метод решения этой задачи, ставший общепринятым и получивший название “Линейное программирование”.
Сегодня линейное и, шире, математическое программирование – один из основных методов принятия производственно-экономических решений.
 

1), то величина f0, а, следовательно, и значение целевой функции fx будет изменяться. Увеличению целевой функции соответствует перемещение в направлении, указанном на рис. 1 стрелкой. Ограничения или условия типа равенств, называемые также связью, на плоскости x1, x2 изображаются так же, как целевая функция, прямыми линиями (рис. 2). Если связь a11x1+ a12x2= b1, то ей "убивается" одна степень свободы, т.е. число переменных, которыми можно варьировать, определяется разностью между числом переменных xi, i=1,n и числом ограничений типа равенств m-v=n-m (m<n). Эти переменные называются свободными переменными, а число ν определяет число степеней свободы. Рис.2Ограничения типа неравенств оставляют ту же степень свободы, поэтому их может быть сколько угодно. Эти ограничения определяют толькообласть допустимых решений. Неравенства a21x1+ a22x2≤ b2, a31x1+ a32x2≤ b3 разделяют всю плоскость (x1, x2) на две области: запрещенную и разрешенную (рис. 3).Рис.3 Как правило, при геометрическом представлении ограничений типа неравенств на плоскости наносят штриховку в сторону запрещенной области. На рис. 3 разрешенной областью является область АВС0, эта область представляет собой выпуклый многогранник. В задачах линейного программирования принято максимизировать функцию цели f, поэтому оптимальное решение всегда лежит в вершине допустимого многогранника, образованного ограничениями.Метод перебораДля нахождения оптимального решения нужно вычислить значения функции цели для всех базисных решений и выбрать из них экстремальное. Такой способ определения оптимального решения задачи линейного программирования называется методом перебора. При большом количестве базисных решений метод перебора становится слишком трудоемким.Рассмотрим более подробно процедуру получения оптимального решения канонической задачи линейного программирования методом перебора.fXextr f(x)= c1x1+ c2x2+…+cnxn, xi ≥ 0, i = 1, 2, ..., N,a11x1+a12x2+ …+a1nxn=b1,aj1x1+aj2x2+ …+ajnxn= bj,am1x1+am2x2+ …+amnxn= bm, Предположим, что переменные xi (i = 1, 2, ..., N) пронумерованы так, что первые M переменных являются базисными, а остальные P = N – M переменных – свободными. Учитывая это, перепишем систему в виде a11x1+a12x2+ …+a1mxm=b1-(a1m+1xm+1+…+a1m+pxm+p),a21x1+a22x2+ …+a2mxm=b2-(a2m+1xm+1+…+a2m+pxm+p)aj1x1+aj2x2+ …+ajmxm=bj-(ajm+1xm+1+…+ajm+pxm+p),Полученная система является системой M уравнений для M базисных переменных (неизвестных) x1, x2, ..., xm. Решение этой системы (если ее определитель не равен нулю) позволяет выразить базисные переменные x1, x2, ..., xm через свободные переменные xm+1, xm+2, ..., xm+p:x1=1a11xm+1+a12xm+2+ …+a1pxm+p,x2=2a21xm+1+a22xm+2+ …+a2pxm+p,xi=iai1xm+1+ai2xm+2+ …+aipxm+p,(7)где параметры 1 и aij получены в результате решения системы.Функцию цели f также следует выразить через свободные переменные: fxm+1,xm+2, …, xm+p= d0+d1xm+1+d2xm+2+ …+ dpxm+p (8)Где dk – коэффициенты, появляющиеся при подстановке системы (7) в целевую функцию.Так как оптимум целевой функции достигается на базисном решении, то минимум (максимум) f реализуется, если все коэффициенты dk (k = 1,...,P) в функции (8) положительны (отрицательны).Если хотя бы один из коэффициентов dk будет отрицательным (положительным), то полученное в (8) значение f не будет минимальным (максимальным) и весь процесс следует повторить заново, выбирая в качестве базисных другой набор переменных.Симплекс-методСимплекс-метод позволяет отказаться от метода перебора при решении задач линейной оптимизации, является основным численным методом решения задач линейного программирования и позволяет за меньшее число шагов, чем в методе перебора, получить решение.Рассмотрим каноническую задачу линейной оптимизации в которой переменные xi ≥ 0 (i = 1, 2, ..., N) разделены на M базисных переменных, обозначенных как yi, j = 1, 2, ..., M, и P свободных переменных, за которыми сохранено обозначение x, т. е. xk, k = 1, 2, ..., P, и базисные переменные yi выражены через свободные xk,: y1=1+a11x1+a12x2+ …+a1pxp,y2=2+a21x1+a22x2+ …+a2pxp,ym=m+am1x1+am2x2+ …+ampxp,Если постоянные j (j = 1, 2, ..., M) неотрицательны, то решение – допустимое.Выразим функцию цели через полученное допустимое решениеf=d0+d1x1+d2x2+ …+dpxpи получим базисное решение: y1=β1, y2=β2… , ym=βm, f=y1=d0,Если все коэффициенты при свободных переменных dk (k = 1, ..., P) положительны (отрицательны), то функция цели на базисном решении достигает минимума (максимума). Если какие-то из коэффициентов dk отрицательны (положительны), то функция цели будет убывать (возрастать) при увеличении свободных переменных. В этой ситуации свободные переменные при отрицательных (положительных) константах dk целесообразно отнести к базисным переменным, так как они однозначно вычисляются и им нельзя придавать произвольные значения. Процесс перевода соответствующих свободных переменных в базисные осуществляется поэтапно. Среди свободных переменных с отрицательными (положительными) коэффициентами в выбирается переменная с максимальным по абсолютной величине коэффициентом и включается в базисные.Переводя свободную переменную в базисные, необходимо исключить из базисных одну переменную и перевести ее в свободные. Для определения исключаемой переменной необходимо увеличивать включаемую в базис свободную переменную. Увеличение свободной переменной приводит к требуемому уменьшению (увеличению) целевой функции f. Это можно делать до тех пор, пока какая-то из базисных переменных не станет отрицательной. Именно эту базисную переменную – исключаем из базиса.Для определения необходимо записать систему ограничений при условии, что значения всех свободных переменных, кроме включаемой в базис, равны нулю, y1= 1+1BxB, y2= 2+2BxB, yM= M+MBxB,и рассмотрим систему ограничений как набор независимых уравнений относительно xB y1→ 1+1BxB=0 ,y2→ 2+2BxB=0, yM→ M+MBxB=0,(8)То из уравнений, которое имеет минимальное положительное решение xB= -1/1B≥0 (j = 1, 2, ..., M), определяет исключаемую из базиса переменную yf. Уравнение в содержащее переменную yf, называется главным, или разрешающим, уравнением.После того, как включаемая в базис переменная xB и исключаемая из базиса переменная yf определены, необходимо выразить новые базисные переменные (которые включают xB) через новые свободные переменные (которые включают yf), т. е. решить систему линейных уравнений относительно новых базисных переменных. В результате базисные переменные снова записываются в виде системы (8), в котором постоянные j (j = 1, 2, ..., M) неотрицательны.Далее, весь процесс повторяется до тех пор, пока не будет достигнут экстремум.Реализация алгоритма симплекс-метода1. Записать задачу в канонической форме: заменить все ограничения-неравенства на ограничения-равенства с положительной правой частью. 2. Разделить переменные на базисные и свободные: перенести свободные переменные в правую часть ограничений-равенств. 3. Выразить базисные переменные через свободные: решить систему линейных уравнений (ограничений-равенств) относительно базисных переменных. 4. Проверить неотрицательность базисных переменных: убедиться в неотрицательности свободных членов в выражениях для базисных переменных. Если это не так, то вернуться к п. 2, выбирая другой вариант разделения переменных на базисные и свободные. (Этот пункт существен только при первоначальном разделении переменных на базисные и свободные.) 5. Выразить функцию цели f через свободные переменные: базисные переменные, входящие в f, выразить через свободные переменные. 6. Вычислить полученное базисное решение и функцию цели f на нем: приравнять к нулю свободные переменные. 7. Проанализировать формулу функции цели f: если все коэффициенты при свободных переменных положительны (отрицательны), то найденное базисное решение будет минимальным (максимальным) и задача считается решенной. 8. Определить включаемую в базис и исключаемую из базиса переменные: если не все коэффициенты при свободных переменных в функции цели f положительны (отрицательны), то следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, например xB, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных, например yf, не станет равной нулю. (Естественно, что при этом остальные свободные переменные сохраняют свои нулевые значения.) Свободную переменную xB, рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную yf рассматриваем как новую свободную переменную (исключаемую из базиса). 9. Используя новое разделение переменных на базисные и свободные, вернуться к п. 3 и повторять все этапы до тех пор, пока не будет найдено оптимальное решение.Метод решения при помощи ExcelДля того, чтобы найти оптимальное решение в задачах линейного программирования не обязательно считать самостоятельно. В вычислениях может помочь программа Excel, а точнее ее надстройка «Поиск решения». Надстройка Поиск решений предназначается для сложных вычислений, когда имеется больше одной неизвестной. Также надстройку нередко называют «Решатель», поскольку она способна вести точные и быстрые вычисления, зачастую независимо от того, насколько сложная задача ей представлена.Когда у пользователя присутствует целевая функция, зависящая от нескольких параметров, надстройка будет подбирать решения задачи в соответствии с исходными данными. Таковыми может оказаться переменная, неизвестная или, например, итоговое значение. То есть, пользователь может иметь начальные характеристики и ответ, а программа подберет ход решения, предоставит формулу.Поиск решений в Excel применяется для самых сложных задач, где имеется несколько неизвестных, часто встречаются переменные. В общей постановке их можно сформулировать следующим образом:Найти неизвестные→несколько «x».При условии, что→формула или функция.При ограничениях→здесь обычно указывается неравенство, либо минимальные/максимальные значения.Также нужно указать на ячейки, с которыми следует проводить вычисления. Есть возможность решать несколько разных задач, если задать программе соответствующие параметры.Практическая частьРешение задачи Рассмотрев теоретические основы линейного программирования, а так же составив модель поставленной задачи, можно преступить к ее решению.