Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Экономический анализ задачи линейного программирования

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

1. Понятие математического программирования

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

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

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

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

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

  • задачи линейного программирования,
  • задачи нелинейного программирования .

Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования .

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина » математическое программирование «. Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина » линейное программирование » возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин » линейное программирование » возник в результате неточного перевода английского » linear programming «. Одно из значений слова «programming» — составление планов, планирование. Следовательно, правильным переводом английского » linear programming » было бы не » линейное программирование «, а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термины линейное программирование , нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти при условиях

Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме

VIII Международная студенческая научная конференция Студенческий научный форум — 2016

МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

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

Читать еще:  Программирование с нуля паскаль

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

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

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

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

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

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

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

Рассмотрим данный метод на примере решения следующей задачи.

Предприятие ООО «Пшеница» предполагает выпускать два вида продукции: печенье и пряники, для производства которых используется сырьё трех видов: мука, сахар, дрожжи. Производство обеспечено сырьем каждого вида в количествах: 750, 807, 840 кг. На изготовление печенья требуется затратить сырья каждого вида 5, 4, 1 кг, соответственно, а для пряников — 2, 5, 7 кг. Прибыль от реализации печенья составляет 30 ден. ед., для пряников — 49 ден. ед.

Занесём необходимые нам данные во вспомогательную таблицу:

Вопрос 19. Экономический анализ решения задач линейного программирования

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

Чувствительность экономико-математической модели – это зависимость оптимального решения от изменения параметров исходной задачи.

Выделяют следующие три основные задачи анализа оптимального решения на чувствительность.

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

Читать еще:  Транспортная задача линейного программирования онлайн решение

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

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

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

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

Двойственные оценки являются:

1) показателем дефицитности ресурсов и продукции. Чем больше значение оценки уi i-го ресурсатем выше дефицитность ресурса. Для недефицитного ресурса уi = 0;

2) показателем влияния изменения правой части ограничений (запасов ресурсов) на значение целевой функции. Практический интерес представляют пределы (нижний и верхний) изменения ресурсов, в которых величины оценок остают­ся неизменными.

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

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

Пусть задача имеет следующую математическую модель Модель двойственной задачи

Пусть данные на листе Excel размещены следующим образом

Решение ДЗ получают с помощью надстройки ПОИСК РЕШЕНИЯ автоматически, при решении прямой задачи путем формирования трех отчетов: по результатам, по устойчивости, по пределам.

Не нашли, что искали? Воспользуйтесь поиском:

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

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

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

На самом же деле результирующая симплекс-таблица содержит весьма важные данные, лишь небольшую часть которых составляют оптимальные значения переменных. Из симплекс-таблицы можно получить информацию относительно:

1. Оптимального решения;

2. Статуса ресурсов;

3. Ценности каждого вида ресурсов;

4. Чувствительности оптимального решения к изменению запасов ресурсов, вариациям коэффициентов целевой функции и интенсивности потребления ресурсов.

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

С точки зрения практического использования результатов решения задач линейного программирования классификация переменных на базисные и небазисные не имеет значения и при анализе оптимального решения может не учитываться. Переменные, отсутствующие в симплекс таблице в столбце «базисные переменные», обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце «свободные члены».

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

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

Ценность ресурса характеризуется величиной улучшения оптимального значения Z, приходящегося на единицу прироста объема данного ресурса. Ценность ресурса нельзя отождествлять с действительной ценой ресурса, по которой возможна его закупка, так как ценность ресурса – это некоторая экономическая мера, количественно характеризующая ресурс относительно полученного оптимального значения Z.

Читать еще:  Технологии визуального программирования

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

Экономический анализ задачи линейного программирования

Итак, для нахождения оптимальной производственной программы необходимо такое решение системы многих уравнений с многими неизвестными, при котором критерий (целевая функция) достигает оптимума. Система уравнений и неравенств (24.1) — (24.5), (24.7) обладает следующим свойством она линейна относительно неизвестных. Это означает, что неизвестные входят в уравнения, неравенства и критерий лишь в первой степени и что отсутствуют произведения неизвестных. Методом решения подобных задач, которые носят название задач линейного программирования, служит так называемый симплекс-метод. Симплекс-метод изложен в целом ряде книг. Ограничимся лишь его технико-экономической интерпретацией. [c.413]

Один из видов решения имеет особое значение для экономической интерпретации задачи линейного программирования. Оказывается, каждой прямой задаче линейного программирования соответствует другая, симметричная ей задача. Если прямой можно называть задачу максимизации выпуска продукции ( ли объема реализации , прибыли и т. д.), то двойственная заключается, наоборот, в минимизации затрат ресурсов. Ее целевая функция — сумма произведений цепы каждого ресурса на его количество — равна целевой функции прямой задачи. Сот в этой цене — коренной смысл задачи линейного программирования как оптимизационной. Именно ее называют объективно обусловленной оценкой., или оптимальной оценкой, или разрешающим множителе. . [c.124]

Интересной и очень широко используемой особенностью задач линейного программирования является то, что каждой из них соответствует определенная, тесно связанная с ней другая задача линейного программирования, получившая название двойственной. Оказывается, что упоминавшиеся выше объективно обусловленные оценки единицы каждого вида продукции и затрачиваемых производственных факторов сами являются решениями некоторой задачи на максимум — двойственной задачи. Поясним теперь, как естественным образом возникает задача, двойственная к задаче раскроя, и дадим ее экономическую и геометрическую интерпретации. [c.15]

Метод линейного программирования, наиболее распространенный в прикладных экономических исследованиях ввиду его достаточно наглядной интерпретации, позволяет хозяйствующему субъекту дать обоснование наилучшему (по формальным признакам) решению Е условиях более или менее жестких ограничений относительно доступных для предприятия ресурсов. С помощью линейного программирования в анализе финансово-хозяйственной деятельности решается ряд задач, в первую очередь относящихся к процессу планирования деятельности — он позволяет отыскивать оптимальные параметры выпуска и способы наилучшего использования имеющихся ресурсов. [c.141]

В теории линейного программирования доказывается, что независимо от экономической интерпретации исходной и двойственной задач, а также от характера ограничений ( ), если решение ЛП-задачи на максимум или на минимум существует, то оптимальное (максимальное или минимальное) значение целевой функции в исходной задаче должно быть в точности равно оптимальному (минимальному или максимальному) значению целевой функции двойственной задачи. [c.72]

Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига—Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию. Метод предусматривает разложение исходной задачи (5.6)—(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи). [c.179]

Ссылка на основную публикацию
Adblock
detector