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

Научная электронная библиотека

Оразбаев Б. Б., Курмангазиева Л. Т., Коданова Ш. К.,

4.1. Модели операций. Задачи математического программирования

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

2. Линейное программирование. Интерпретация задач линейного программирования.

3. Задача распределения ресурсов. Аксиомы линейности.

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

Основная задача математического программирования. Рассмотрим множество:

(4.1)

Пусть скалярная функция f(x) определена на множестве Х. Задачу минимизации функции f(x) на множестве Х будем называть основной задачей математического программирования.

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

(4.2)

или, ей эквивалентный запись:

означает, что ставится задача:

1) либо найти оптимальную точку x* ∈ X:

2) либо, если существует такая х*, то найти

где inf f(x) – нижняя граница функции f(x).

3) либо: убедиться в том, что Х = ∅.

Если множества Х выпукло и выпукла функция f(x), то задачу (4.2) называют задачей выпуклого программирования.

Множество Х в задаче (4.2) называют допустимым множеством, точки этого множества – допустимыми точками; множество – исходным множеством альтернатив; неравенство ϕj(x) ≥ 0, , определяющие допустимое множество – ограничениями. Точку
называют решением или оптимальной точкой. Точку х, в которой выполняется необходимые условия, локального минимума функции f(x) на множестве Х, будем называть стационарной.

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

Общая задача математического программирования состоит в определении вектора х* с координатами , которой является решением задачи:

при

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

– линейного программирования f(x), ϕj(x), hj(x) – линейны;

– нелинейного программирования – хотя одна из функций f(x), ϕj(x), hj(x) нелинейные;

– квадратичного программирования – f(x), является квадратичной функцией, ограничения (ϕj(x), hj(x)) нелинейные;

– сепарабельного программирования f(x) – представляет собой сумму функций, различных для каждой переменной, условия – ограничения могут быть как линейными, так и нелинейными;

– целочисленного программирования функция f(x) – выпукла, ϕj(x), hj(x) – вогнутые, решения представляют собой целочисленные значения.

2. Линейное программирование. Интерпретация задач линейного программирования

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

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

(4.3)

(4.4)

(4.5)

и минимизирует (максимизирует) линейную функцию:

(4.6)

Это общая задача линейного программирования.

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

Очевидно, задача максимизации целевой функции (с, х) при каких-либо ограничениях эквивалентна задаче минимизации –(с, х). При этом

Естественным ответом на вопрос о том, как решать сформулированную задачу ЛП (4.3)–(4.6), кажется следующий метод простого перебора: найти произвольное решение х1 системы (4.3)–(4.5), вычислить (с, х1), затем найти другое решение х2, вычислить (с, х2) и т.д. и среди полученного спектра значений целевой функции (с, х), выбрать наименьшее. Значение х, реализующее минимум целевой функции, будет решением задачи ЛП. Но этот путь перебора оказывается труднореализуемым или даже нереализуемым в силу сложности поиска допустимых решений задачи ЛП. Допустимая область имеет, вообще говоря, бесконечное множество точек и может являться многогранным множеством. Это, в частности, означает, что если D принадлежат две какие-либо точки, то D принадлежат и все точки, соединяющего эти точки.

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

Для простоты рассуждений рассмотрим задачу ЛП в двумерном пространстве.

Пусть ограничения задачи имеют следующий вид:

(4.7)

Требуется найти минимум целевой функции

Допустим, что система (4.7) совместно и соответствующее ей многогранное множество ограничено, т.е. является многоугольником. Очевидно, что каждое из неравенств (11.7) определяет полуплоскость соответственно с граничной прямой

и целевая функция принимает одно и то же значение f во всех точках прямой

где f – некоторая константа.

При изменении (уменьшение или увеличение) получаем семейство параллельных прямых, называемых линиями уровня функции c1x1 + c2x2. Предположим, что многоугольник и линии уровня имеют вид, представленной на рис. 4.1. Нас интересуют те точки многоугольника D, которые принадлежат линии уровня с наименьшим значением f. Известно, что если перемещать прямую c1x1 + c2x2 = f в направлении ее нормали с, то значение f будет убывать.

Выберем достаточно большое f и будем перемещать прямую c1x1 + c2x2 = f в направлении –с. При этом линии уровня (с, х) = f вначале впервые коснется многоугольника, потом пересчет его и, наконец наступит момент, когда она коснется многоугольника в последний раз. Из рис. 4.1 следует, что прямая будет соприкасаться с многоугольником в точках А и В, причем в А значение целевой функции минимально.

Если же многоугольник не ограничен, то может быть два случая:

1) прямая, передвигаясь в направлении –с, все время пересекает многоугольник D; в этом случае линейная форма не ограничена на допустимой области и ее минимум равен –∞;

2) в результате передвижения вдоль направления –с прямая становится опорной к многоугольнику D.

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

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

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

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

(4.8)

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

Двойственной задаче (4.8), т.е.:

и переменным можно придать следующий смысл.

Пусть ui ≥ 0 – удельная оценка i-го ингредиента, измеренная в тех же единицах, в которых измеряется доход (убыток) каждой технологии. Тогда представляет собой суммарную оценку всех затрат предприятия, связанных с работой по j-й технологии с единичной интенсивностью. Ограничения же двойственной задачи

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

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

3. Задача распределения ресурсов. Аксиомы линейности

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

заданных линейными соотношениями.

В рамках этих ограничений необходимо оптимизировать целевую функцию.

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

Допустим, фирма реализует 1–4 технологических процессов. Технологические процессы 1 и 2 ориентированы на выпуск продукции А, 3 и 4 ориентированы на выпуск продукта В.

Расходы каждого технологического процесса определяются трудозатратами (в человеко-неделях), недельным потреблением материала Y и Z.

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

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

1. Делимость. Для каждого технологического процесса (Т.П.) суммарное потребление каждого из потребляемых ресурсов и прибыль пропорциональны объему выпускаемой продукции.

а) Т.е. все показатели Т.П. могут быть увеличены или уменьшены при сохранении их взаимной пропорциональности.

Для выпуска 10 единиц продукции x1 необходимо 10 человеко-недель, 70 единиц материала Y, 30 единиц материала Z. Доход составит 40 единиц.

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

При составлении производственного плана на неделю примем следующие производственно-экономические показатели и ограничения:

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

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

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

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

4×1 + 5×2 + 9×3 + 11х4 ≡ max; (4.10)

1×1 + 1×2 + 1×3 + 1×4 ≤ 15 (колич. человеко-недель);

7×1 + 5×2 + 3×3 + 2×4 ≤ 120 (ед. материала Y); (4.12)

3×1 + 5×2 + 10×3 + 15×4 ≤ 100 (ед. материала Z).

Уравнение (4.11) определяет суммарную прибыль производственно-технологического процесса из табл. 4.1.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача ЛП в канонической форме:

( 2.1)

( 2.2)

( 2.3)

Задача ЛП в стандартной форме:

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

Источник

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

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

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

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

2. Допустимое решение задачи, одр, оптимальное решение задачи.

Допустимым решением задачи называется любой n-мерный вектор

x (x = (,,…,)), удовлетворяющий системе ограничений и условию неотрицательности.

Множество допустимых решений образует ОДР.

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

3. Экономико–математические модели задач лп: задача о банке

К экономико-математическим моделям задач ЛП относятся:Задача планирования производства, определения оптимального ассортимента продукции, о диете, о банке, составления жидких смесей, Транспортная задача

Построение экономико – математической модели.

Источник

Классификация задач математического программирования

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

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

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

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

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

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

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

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

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

1.2. Общая задача математического программирования.

Сформулируем общую задачу математического программирования.

Дадим количественную, математическую постановку этой задачи.

X_i 0, i=1,2,…,n

удовлетворяют «m» ограничениям:

и максимизируют функцию:

Z=F(X₁,X₂,…,X_n) MAX

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

Классификация задач математического программирования

В основе той или иной классификации лежит признак, по которому объекты разделяются или объединяются в классы.

Если функция цели и ограничения являются линейными:

Z=F(X₁,X₂,…,X_n)=C₁X₁+C₂X₂+…C_nX_n MAX;

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

Частным случаем задач нелинейного программирования являются задачи целочисленного программирования. От задач линейного программирования они отличаются только наличием условия целочисленности переменных X1, X2. Хn.

Если целевая функция задачи математического программирования квадратичная, но все её ограничения линейны, то такую задачу называют задачей квадратичного программирования. Линейные ограниче­ния, для данной задачи записываются так же как для задачи линейного программирования, а целевая функция имеет вид:

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

Z=F(X₁,X₂)=X₁*X₂ MAX;

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

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

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

— задача управления запасами;

— задачи замены оборудования;

— задача выбора оптимальных режимов движения;

— задача выбора оптимальной структуры.

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

Примерами распределительных задач являются:

— транспортная задача, в которой рассматривается вопрос об оптимальном прикреплении пунктов производства и пунктам потребления;

— задача о назначении, в которой рассматривается вопрос об опти­мальном прикреплении производителя работ к объекту производст­ва;

— задача o выборе рациона;

— задача выбора применения ресурсов;

— задача выбора типажа и другие задачи.

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

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

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

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

В заключение еще раз подчеркнем большой экономический эффект от применения методов математического программирования на практике.

Рис.1.: Задачи математического программирования.

1.4.Контрольные задания.

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

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

Источник