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

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

модели) – 80 шт;

объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3)неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

Решение задачи линейного программирования графическим методом[шт/сутки]

Ограничения по суточному объему первой и второй технологических линий имеют вид:

Решение задачи линейного программирования графическим методом [шт/сутки]

Неотрицательность объемов производства задается как

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

Таким образом, математическая модель этой задачи имеет вид

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

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


3.3 Нахождение оптимального решения задачи с помощью линейного метода.


Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:

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

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

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).

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

прямая (1) – точки (0;95) и (63,(3);0), прямая (2) проходит через точку Решение задачи линейного программирования графическим методом параллельно оси Решение задачи линейного программирования графическим методом, прямая (3) проходит через точку Решение задачи линейного программирования графическим методом параллельно оси Решение задачи линейного программирования графическим методом.

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

Рис.3.1. Графическое решение задачи о производстве радиоприемников.


Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим Решение задачи линейного программирования графическим методом, что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

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

Точки пересечения с осями – (0;75) и (37,5;0)

Строим вектор Решение задачи линейного программирования графическим методом из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора Решение задачи линейного программирования графическим методом. Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

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

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно Решение задачи линейного программирования графическим методом[$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.


4.АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


4.1. Теоретическое введение


Неизбежное колебание значений таких экономических параметров, как цены на продукцию и сырье, запасы сырья, спрос на рынке и т.д. может привести к неоптимальности или непригодности прежнего режима работы. Для учета подобных ситуаций проводится анализ чувствительности, т.е. анализ того, как возможные изменения параметров исходной модели повлияют на полученное ранее оптимальное решение задачи ЛП.

Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

на сколько можно увеличить (ограничения типа Решение задачи линейного программирования графическим методом) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

на сколько можно уменьшить (ограничения типа Решение задачи линейного программирования графическим методом) запас недефицитного ресурса при сохранении оптимального значения ЦФ?

2. Увеличение (ограничения типа Решение задачи линейного программирования графическим методом) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения коэффициентовЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

4.2. Методика графического анализа чувствительности оптимального решения.


4.2.1. Первая задача анализа на чувствительность (анализ на чувствительность к правой части ограничений)


Проанализируем чувствительность оптимального решения задачи о производстве радиоприемников. ОДР задачи (рис.3.1) – многоугольник ABCDE. В оптимальной точке D пересекаются прямые (1) и (2). Поэтому ограничения (1) и (2) являются связывающими, а соответствующие им ресурсы (суточный объем элементов электронных схем и производительность первой технологической линии) – дефицитными.

Рассмотрим экономический смысл этих понятий. Точка максимума ЦФ D соответствует суточному производству 60 шт радиоприемников первой модели и 5 шт радиоприемников второй модели. В производстве радиоприемников используются однотипные элементы электронных схем. Суточный запас на складе этих элементов – это правая часть связывающего ограничения (1) (950 шт/сутки). Согласно этому ограничению, на производство в точке D расходуется

Решение задачи линейного программирования графическим методом [шт элементов/сутки](1).

Аналогично видим, что производительность первой технологической линии - это правая часть связывающего ограничения (2) (60 шт/сутки). Согласно этому ограничению в точке D данная линия производит 60 радиоприемников первой модели в сутки.

Таким образом, понятие "связывающие ограничения" (1) и (2) означает, что при производстве радиоприемников в точке D(60;5) запасы элементов электронных схем расходуются полностью, а так же производительность первой технологической линии используется в полном объеме. По этой причине невозможно дальнейшее наращивание производства. В этом заключается экономический смысл понятия дефицитности ресурсов, т.е. если предприятие сможет увеличить суточные запасы элементов электронных схем или производительность первой технологической линии, то это позволит увеличить выпуск радиоприемников. В связи с этим возникает вопрос: до какого уровня целесообразно увеличить данные ресурсы, и на сколько при этом увеличится оптимальное производство радиоприемников?

Правило №1

Чтобы графически определить максимальное увеличение запаса дефицитного ресурса, вызывающее улучшение оптимального решения,

необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным.

При прохождении прямой (1) через точку К (рис.4.1) многоугольник ABKE становится ОДР, а ограничение (1) – избыточным. Действительно, если удалить прямую (1), проходящую через точку К, то ОДР ABKE не изменится. Точка К становится оптимальной, в этой точке ограничения (2) и (3) становятся связывающими.

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

Рис.4.1. Анализ увеличения суточного запаса элементов электронных схем

Правило №2

Чтобы численно определить максимальную величину запаса дефицитного ресурса, вызывающую улучшение оптимального решения,

необходимо:

1) определить координаты точки Решение задачи линейного программирования графическим методом, в которой соответствующее ограничение становится избыточным;

2) подставить координаты Решение задачи линейного программирования графическим методом в левую часть соответствующего ограничения.

Координаты точки К(60;80) находятся путем решения системы уравнений прямых (2) и (3). Т.е. в этой точке предприятие будет производить 60 шт радиоприемников первой модели и 80 шт радиоприемников второй модели. Подставим Решение задачи линейного программирования графическим методом и Решение задачи линейного программирования графическим методом в левую часть ограничения (1) и получим максимально допустимый запас элементов электронных схем

Решение задачи линейного программирования графическим методом [шт эл/сутки].

Дальнейшее увеличение запаса элементов электронных схем нецелесообразно, потому что это не изменит ОДР и не приведет к другому оптимальному решению (см. рис.4.1). Доход от продажи радиоприемников в объеме, соответствующем точке К, можно рассчитать, подставив ее координаты в выражение ЦФ

Решение задачи линейного программирования графическим методом [$/сутки].

Рассмотрим вопрос о целесообразности увеличения производительности первой технологической линии. Согласно правилу №1, соответствующее ограничение (2) становится избыточным в точке J, в которой пересекаются прямая (1) и ось переменной Решение задачи линейного программирования графическим методом (рис.4.2). Многоугольник ABCJ становится ОДР, а точка J(63,33;0) (или (63;0)-целочисленное решение) – оптимальным решением.

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

Рис.4.2. Анализ увеличения производительности первой технологической линии

В точке J выгодно производить только радиоприемники первой модели (63 шт в сутки). Доход от продажи при этом составит

Решение задачи линейного программирования графическим методом [$/сутки]

Чтобы обеспечить такой режим работы, согласно правилу №2, производительность первой технологической линии надо увеличить до величины

Решение задачи линейного программирования графическим методом [шт/сутки].

Ограничение (3) является несвязывающим, т.к. не проходит через оптимальную точку D (см. рис.4.3). Соответствующий ему ресурс (производительность второй технологической линии) является недефицитным. С экономической точки зрения это означает, что в данный момент уровень производительности второй технологической линии непосредственно не определяет объемы производства. Поэтому некоторое его колебание может никак не повлиять на оптимальный режим производства в точке D.

Например, увеличение (уменьшение) суточного объема второй технологической линии будет соответствовать перемещению прямой ограничения Решение задачи линейного программирования графическим методом (3) вверх (вниз). Перемещение прямой (3) вверх никак не может изменить точку D максимума ЦФ. Перемещение же прямой (3) вниз не влияет на существующее оптимальное решение только до пересечения с точкой D (см. ниже правило №3). Из рис.4.3 видно, что дальнейшее перемещение (3) приведет к тому, что точка D будет за пределами новой ОДР, выделенной более темным цветом. Кроме того, любое оптимальное решение для этой новой ОДР будет хуже точки D.

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

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


Правило №3

Чтобы определить максимальное уменьшение запаса недефицитного ресурса, не меняющее оптимальное решение,

необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой.

Правило №4

Чтобы численно определить минимальную величину запаса недефицитного ресурса, не меняющую оптимальное решение,

необходимо подставить координаты оптимальной точки в левую часть соответствующего ограничения.

Чтобы выяснить, до каких пределов уменьшение производительности второй технологической линии не повлияет на производство в точке D, используем правило №4 Подставляем в левую часть ограничения (3) координаты точки D, получаем

Решение задачи линейного программирования графическим методом[шт/сутки].

Делаем вывод: предельный уровень, до которого может уменьшиться объем второй технологической линии, и при котором не изменится оптимальность полученного ранее решения, равен 5 шт радиоприемников в сутки.

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


Таблица 4.1

№ Тип ресурса

Max

изменение ресурса,

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

Max

изменение

дохода,

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

$/сутки

Ценность

дополнительной

единицы ресурса

Решение задачи линейного программирования графическим методом, $/шт

(1) Дефицитный 1700-950=+750 4000-2500=+1500

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

(2) Дефицитный 63-60=+3 2520-2500=+20

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

(3) Недефицитный 5-80=-75 2500-2500=0

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


4.2.2. Вторая задача анализа на чувствительность (увеличение запаса какого из ресурсов наиболее выгодно)


Анализ табл.4.1 показывает, что к улучшению оптимального решения, т.е. к увеличению суточного дохода приводит увеличение дефицитных ресурсов. Для определения выгодности увеличения этих ресурсов используют понятие ценности дополнительной единицы i-го ресурса Решение задачи линейного программирования графическим методом

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

где Решение задачи линейного программирования графическим методом – максимальное приращение оптимального значения ЦФ; Решение задачи линейного программирования графическим методом – максимально допустимый прирост объема i-го ресурса.

Например, из табл.4.1 следует, что увеличение суточного запаса элементов электронных схем (ограничение (1)) на 1 шт позволит получить дополнительный доход, равный 2 $/сутки, в то время как увеличение производительности первой технологической линии (ограничение (2)) на 1 шт принесет 6,7 $/сутки. Недефицитные ресурсы имеют нулевые ценности, поскольку изменение этих ресурсов не приводит к увеличению дохода.

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


4.2.3. Третья задача анализа на чувствительность (в каких пределах допустимо изменение коэффициентов целевой функции)


Изменение цен на продукцию, т.е. изменение коэффициентов ЦФ, представляется на графике вращением целевой прямой вокруг оптимальной точки. Так, при увеличении коэффициента ЦФ Решение задачи линейного программирования графическим методом или уменьшении Решение задачи линейного программирования графическим методом целевая прямая вращается по часовой стрелке. При уменьшении Решение задачи линейного программирования графическим методом или же увеличении Решение задачи линейного программирования графическим методом целевая прямая вращается против часовой стрелки (рис.4.4).

При таких поворотах точка D будет оставаться оптимальной до тех пор, пока наклон целевой прямой не выйдет за пределы, определяемые наклонами прямых ограничений (1) и (2). Так, например, если наклон целевой прямой совпадет с наклоном прямой (1), то оптимальным решением будут точки отрезка СD. При совпадении c прямой (2) оптимальным решением будут точки отрезка DE.

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

Рис.3.4. Анализ изменения цен


Наличие альтернативных оптимумов свидетельствует о том, что одно и то же оптимальное значение может достигаться при различных значениях переменных. Если целевая прямая выйдет за пределы наклона (1), то оптимальной точкой станет точка C. Допустим, что цена на радиоприемники второй модели не меняется, т.е. зафиксируем значение целевого коэффициента Решение задачи линейного программирования графическим методом. Проанализируем графически результаты изменения значения целевого коэффициента Решение задачи линейного программирования графическим методом, т.е. цены на радиоприемники первой модели. Оптимальное решение в точке D не будет меняться при увеличении Решение задачи линейного программирования графическим методом до тех пор, пока целевая прямая не совпадет с прямой (2). Аналогично, оптимальное решение в точке D не будет меняться при уменьшении Решение задачи линейного программирования графическим методом до тех пор, пока целевая прямая не совпадет с прямой (1).

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


Правило №5

Чтобы определить границы допустимого диапазона изменения коэффициента ЦФ, например Решение задачи линейного программирования графическим методом и Решение задачи линейного программирования графическим методом,

необходимо приравнять тангенс угла наклона целевой прямой Решение задачи линейного программирования графическим методом поочередно к тангенсам углов наклона прямых связывающих ограничений, например Решение задачи линейного программирования графическим методоми Решение задачи линейного программирования графическим методом (рис.4.5 и 4.6).

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

Рис.4.5. Определение Решение задачи линейного программирования графическим методом

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

Рис.4.6. Определение Решение задачи линейного программирования графическим методом

Определим, насколько максимально может снизиться цена на радиоприемники первой модели, не изменяя оптимальную точку D. Для этого применим правило №5.

Тангенсы угла наклона для прямых L(x) и (1) соответственно равны:

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

Тогда из равенства Решение задачи линейного программирования графическим методом находим Решение задачи линейного программирования графическим методом [$/шт]

Теперь попробуем определить, насколько максимально может увеличиться цена на радиоприемники первой модели, чтобы не изменилась оптимальная точка D.

На рис 4.6 видно, что значение c1 можно увеличивать беспредельно, так как прямая L(x) при c2 = 20 и Решение задачи линейного программирования графическим методом никогда не совпадает с прямой (2). Следовательно, точка D при всех значениях коэффициента Решение задачи линейного программирования графическим методом будет единствен­ной оптимальной.

Из приведенных выше расчетов и графической их иллюстрации следует, что если цена на радиоприемники первой модели станет меньше 30 $/шт, то наиболее выгодным будет производство радиоприемников в точке C (см. рис.4.5). При этом производительность первой технологической линии будет использоваться не в полном объеме, что приведет к недефицитности данного ресурса (2), а дефицитными будут ресурсы (1) и (3).

Проведем те же самые исследования для радиоприемников второй модели. Для этого зафиксируем значение Решение задачи линейного программирования графическим методом. Ищем Решение задачи линейного программирования графическим методом:

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

Тогда из равенства Решение задачи линейного программирования графическим методом находим Решение задачи линейного программирования графическим методом [$/шт]

На рис 4.6 видно, что значение c2 можно уменьшать до нуля, так как прямая L(x) при c1 = 40 и Решение задачи линейного программирования графическим методом совпадает с прямой (2). Следовательно, точка D при всех значениях коэффициента Решение задачи линейного программирования графическим методом будет оптимальной.

Аналогично делаем вывод, что если цена на радиоприемники второй модели станет выше 26,67 $/шт, то наиболее выгодным будет производство радиоприемников в точке C.

С экономической точки зрения производство радиоприемников в точке С означает, что предприятию станет выгоднее изготовлять радиоприемники второй модели, используя на полную мощность производительность второй технологической линии.


ЗАКЛЮЧЕНИЕ.


В ходе работы над курсовым проектом была рассмотрена задача линейного программирования о производстве радиоприемников. Для решения задачи использовался графический метод. Получены следующие результаты:

Оптимальная прибыль от реализации продукции достигается при следующем суточном производстве радиоприемников: 60 шт радиоприемников первой модели и 5 шт радиоприемников второй модели. При этом прибыль от реализации составит 2500$ в сутки.

Рассмотрев три задачи анализа полученного решения на чувствительность к принятой модели, мы можем ответить на следующие вопросы:

Определите предел увеличения производительности первой линии, превышение которого уже не будет улучшать значения целевой функции.

- предел увеличения производительности первой линии равен 63 радиоприемника в сутки. Дальнейшее увеличение производительности не имеет смысла, т.к. значение ЦФ не улучшится.

Определите предел уменьшения производительности второй линии, при котором полученное оптимальное решение останется неизменным.

- предельный уровень, до которого может уменьшиться производительность второй технологической линии, и при котором не изменится оптимальность полученного ранее решения, равен 5 радиоприемников в сутки.

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

- предел увеличения суточного запаса элементов электронных схем равен 1700 шт в сутки. Дальнейшее увеличение нецелесообразно, потому что это не изменит ОДР и не приведет к другому оптимальному решению.

Определить дефицитный ресурс, который имеет

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

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

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

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