Математическое программирование

План: 
 

Введение 

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

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

3. Понятие нелинейного  программирования 

4. Динамическое программирование 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

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

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

В общем виде математическая постановка экстремальной задачи состоит  в определении наибольшего или  наименьшего значения целевой функции f(x1, х2,.........., xn) при условиях gi(x1, х2,.........., xn) ≤ bi, где f и gi — заданные функции, a bi — некоторые действительные числа. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует несколько  методов решения задач ЛП. В  данной работе будут рассмотрены  некоторые из них, в частности: 

Графический метод  решения задачи ЛП; 

Симплексный метод; 

Решение задачи ЛП средствами табличного процессора Excel; 

3. Понятие нелинейного  программирования 

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

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

В данной работе будет  рассматриваться такой метод  решения задач НП, как метод  множителей Лагранжа. 

Метод множителей Лагранжа позволяет отыскивать максимум (или  минимум) функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к  задаче отыскания безусловного экстремума некоторой построенной функции  Лагранжа.  

4. Динамическое программирование 

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

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

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

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

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

Пусть процесс оптимизации  разбит на n шагов. На каждом шаге необходимо определить два типа переменных –  переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться  система на данном k-м шаге. В зависимости  от S на этом шаге можно применить  некоторые управления, которые характеризуются  переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S. 

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

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

В общем виде задача динамического программирования формулируется  следующим образом: требуется определить такое управление X*, переводящее  систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение. 

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

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

целевая функция  является аддитивной и равна сумме целевых функций каждого шага; 

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи); 

состояние системы  Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния: 

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных; 

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных  пошаговых управлений:

X*=(X*1, X*2, …, X*k, …, X*n),

число которых и определяет количество шагов задачи. 

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для  всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное  управление X*n и значение функции  Беллмана Fn(S) не сложно, так как

Fn(S)=max{Wn(S,Xn)},

где максимум ищется по всем возможным значениям Xn. 

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

Fk(S)=max{Wk(S,Xk)+Fk+1(S'(S,Xk))}. (1) 

Этот максимум (или  минимум) определяется по всем возможным  для k и S значениям переменной управления X. 

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные  управления найдены для всех шагов  с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага. 

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

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

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

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

 Основные формы  задачи ЛП.

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

 Стандартная задача  ЛП.

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

 Каноническая  задача ЛП.

Основные вычислительные схемы решения задач ЛП разработаны  именно для канонической задачи.

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

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

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

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

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

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

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

Математическое программирование возникло в 30-е годы XX века. Венгерский математик Б.Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Куй обобщил этот метод, после чего он получил название венгерского метода. В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. Большой вклад в развитие математического программирования внесли американские ученые. В 1949 году американский ученый Дж. Данциг опубликовал один из основных методов решения задач линейного программирования, получивший название симплексный.

Составление математической модели экономической задачи включает следующие этапы: 1) выбор переменных задачи; 2) составление системы ограничений; 3) выбор целевой функции.

Переменными задачи называются величины x1, x2, х3,..., xn, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора X=(x1, x2, x3,…., xn)

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

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

Таким образом, общая  задача математического программирования формулируется следующим образом: найти экстремум целевой функции  задачи

Z(X) = f (x1, x2, x3,…., xn)max(min)             (6.4.13)

и соответствующие  ему переменные при условии, что  эти переменные удовлетворяют системе  ограничений

(x1, x2, x3,…., xn ) =0, i=1,2,..,l                          (6.4.14)

(x1, x2, x3,…., xn ) >(<) 0, i = l +1, l+2,…,m     (6.4.15)

Если целевая функция (6.4.13)и система ограничений (6.4.14), (6.4.15) являются линейными, то задача математического  программирования называется задачей  линейного программирования,

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

Это позволяет найти  экстремум целевой функции задачи (6.4.16) и соответствующие ему переменные X=(x1, x2, x3,…., xn) при условии, что эти переменные удовлетворяют системе ограничений (6.4.17) и условиям неотрицательности (6.4.18).

Допустимым решением (планом) задачи линейного программирования называется любой п-мерный вектор X=(x1, x2, x3,…., xn), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

i=1, 2,…,n .

Но если все сi = 0, то и Z = 0, т.е. экстремум функции не обнаруживается. Связано это с тем, что производную можно использовать для определения экстремума только во внутренних точках области решений, а в данном случае экстремум, как будет показано ниже, находится на границах области. Отсюда и возникает необходимость разработки специальных методов поиска экстремума.