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

Оглавление

 

Введение. 3

Основные теоретические сведения по задачам линейного программирования и теории двойственности. 6

Постановка задачи. 15

Математическая модель задачи, математическая модель в канонической форме, модель двойственной задачи и модель двойственной задачи с ограничениями в форме равенства. 16

Решение задачи в Excel с помощью надстройки Поиск решения. 19

Заключение. 21

Список использованных источников. 22

Приложение. 23

 

 

  Введение

 

Премию памяти Нобеля по экономике  в 1975 г. получили ”за вклад в теорию оптимального распределения ресурсов”  Канторович Леонид Витальевич совместно  с Тьяллингом Ч. Купмансом.

Еще в 1938 г. Л.В. Канторович разработал метод распределения ресурсов, (известный  сегодня как метод линейного  программирования Канторовича), произвел максимизацию линейной функции, с учетом большого количества ограничений. Он знал, что максимизация при многочисленных ограничениях – это одна из основных экономических проблем и что  его метод может быть использован  во многих производствах, например, определение  оптимального использования посевных площадей, наиболее эффективного распределения  потоков транспорта и т. д.

По оценкам американских экспертов  около 75% от общего числа применяемых  оптимизационных методов приходится на линейное программирование (ЛП). До четверти машинного времени, затраченного в последние годы на проведение научных  исследований, было отведено решению  задач ЛП и их многочисленных модификаций. Метод линейного программирования в последующие годы нашел широкое  экономическое применение во всем мире.

Формирование исследования операций как самостоятельной научной  дисциплины относится к периоду 40-х и 50-х годов. Последующие полтора  десятилетия были отмечены широким  применением полученных фундаментальных  теоретических результатов к  разнообразным практическим задачам  и связанным с этим переосмыслением  потенциальных возможностей теории. Исследованиями операций в эти годы занимались многие представителями  отечественной научной школы, среди  которых в первую очередь должен быть назван Л. В. Канторович. Среди  других отечественных специалистов, успешно работавших в этой области  должны быть названы Е. С. Вентцель, М. К. Гавурин, Н. Н. Моисеев, Д. Б. Юдин. Важный вклад в данную область внесли такие видные ученые, как Дж. Данциг, Дж. фон Нейман, Г. Кун, Д. Гейл, К. Эрроу, Р. Беллман, Р. Гомори, Т. Саати и др.

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

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

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

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

Среди наиболее важных проблем, с которыми сталкиваются промышленные предприятия, можно выделить:

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

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

3. Низкое качество продукции  и высокий уровень брака. Эти  проблемы вызваны низкой стабильностью  производственного процесса, т.е.  неспособностью предприятия поддерживать  высокие операционные параметры  в течение длительного времени.

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

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

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

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

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

 

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

 

1. Основные теоретические сведения по задачам линейного программирования и теории двойственности

 

Задачи математического  программирования – это задачи определения  наилучшего решения из множества  возможных.

В общем виде математическая формулировка задачи линейного программирования (ЗЛП) следующая: определить значения переменных , при которых достигается максимум или минимум целевой функции:

F ® max (min) целевая функция:

при условиях

_,

,         _{ограничения}                            

…   

  

 

Функция  называется целевой  функцией, а условия – ограничениями  данной задачи. Запись в ограничениях означает, что возможен один из знаков , = или . В данной задаче n обозначает число переменных, а m - число ограничений.

Переменные задачи х₁, х₂, …, х_n могут иметь различный экономический смысл. Например, если предприятие выпускает три вида продукции, и нужно найти оптимальный план производства, то х₁, х₂, х₃ – количество продукции каждого вида, которое необходимо производить. Если в задаче необходимо найти наилучший состав рациона, в которую могут входить несколько составных компонентов (например, сено и силос в рационе коров), то х₁ и х₂ – количество каждого продукта, которое нужно включить в рацион (в данном случае, сена и силоса).

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

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

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

• если целевая функция задачи имеет линейный вид, а ограничения заданы в виде линейных уравнений или неравенств, то это задача линейного программирования. Пример линейного выражения: 5х₁+6х₂.
• если целевая функция и/или ограничения содержат нелинейные функции, то это задача нелинейного программирования. Пример нелинейных функций: х*y, х², , sin x, 1/x и т.д.
• если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Пример: выпуск штучной продукции, назначение работников на работы (нельзя назначить на работу не целое число работников).
• если в задаче математического программирования необходимо учитывать фактор времени, то такая задача является задачей динамического программирования. Обычно решение задач динамического программирования может быть представлено как процесс пошагового принятия решений. На каждом шаге выбирается такое решение, которое не обязательно дает оптимальный результат на этом шаге, но обеспечивает наилучший исход всей операции в целом.

Наиболее разработанными являются методы решения задач линейного  программирования.

В общем виде математическая формулировка задачи линейного программирования (ЗЛП) следующая: найти значения переменных х_i (i = 1, ..., n), при которых достигается максимум (минимум) целевой функции:

F = c₁x₁ + c₂x₂ + ... + с_nх_n ® max (min)

и выполняются ограничения:

а11х1 + а12х2 + … + а1nхn {£, =, ³} b1; а21х1 + а22х2 + … + а2nхn {£, =, ³} b2; аm1х1 + аm2x2 + … + аmnхn {£, =, ³} bm; xj ³ 0, (i = 1, …, n),

 

где а_ij, b_i, c_j — заданные постоянные величины;

m — число уравнений;

n — число переменных.

 

Запись {£, =, ³} в ограничениях означает, что возможен один из знаков (£, = или ³).

Решение Х = (х_1, х_2, …, х_n), при котором выполняются все ограничения, называется допустимым. Допустимое решение, при котором функция F принимает оптимальное значение (максимум или минимум), называется оптимальным.

 

Оптимальное распределение ресурсов анализ отчетов

 

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

Постановка задачи. Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство одной единицы продукции каждого типа заданы матрицей {a_ij}, где a_ij — количество ресурса i-го вида, необходимое для производства одной единицы продукции j-го типа. Известно количество ресурсов (b_i, где i = 1, ..., m) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли (С_j), которую получит предприятие при реализации одной единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т. е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль.

Обозначим через x_j количество продукции j-го типа, которое планируется выпустить (j = 1, ..., n). Тогда математическая модель задачи будет выглядеть следующим образом:

 

Целевая функция задачи представляет собой общую прибыль  от производства всей продукции. Ограничения  выражают условие, при котором потребление  ресурса i-го вида не должно превышать  запаса этого ресурса (b_i). Условия неотрицательности переменных вытекают из смысла переменной x_j: количество продукции не может быть отрицательным.