Что такое математическое программирование линейное программирование
Перейти к содержимому

Что такое математическое программирование линейное программирование

  • автор:

Что такое математическое программирование линейное программирование

На этом шаге мы рассмотрим некоторые понятия линейного программирования .

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

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода ).

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

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

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

(1)

где X = (x1, x2 , . , xn) ; W – область допустимых значений переменных x1, x2 , . , xn ; f(Х) – целевая функция.

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

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

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

  • показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2, . , xn) ;
  • ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

(2)
(3)
(4)
(5)

При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W , называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности .

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность . Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j -й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной xj . Т.е. в разных ситуациях одна единица j -го товара будет приносить разный доход. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.

Допустимое решение – это совокупность чисел ( план ) X = (x1, x2, . , xn) , удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

На следующем шаге рассмотрим построение модели линейного программирования на примере .

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

Математическое программирование [mathematical prog­ramming] — (см. также Оптимальное программирование) — раздел математики, который «… изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств»[1]. Оно объединяет различные математические методы и дисциплины исследования операций: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др.

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

U = f(x) → max; xM,

Частный случай задачи М.п. — «классическая задача«. В ней область M представлена равенствами:

g (x) = b,

где g (x) — вектор функций ограничений, b — вектор констант ограничений.

Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции f(x) и области М. Например, если f(x) и M — линейны, имеем задачу линейного программирования; если же дополнительно ставится условие, чтобы переменные были целочисленны, — имеем задачу целочисленного программирования; если зависимость U от x (т.е. форма f) носит нелинейный характер — задачу нелинейного программирования.

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

[1] Математический аппарат экономического моделирования. М.: “Наука”, 1983, стр 8.

Экономико-математический словарь: Словарь современной экономической науки. — М.: Дело . Л. И. Лопатников . 2003 .

2. Что такое математическое и линейное программирование?

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

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

Линейное программирование – частный случай математического программирования.

3. Какова общая форма записи модели лп?

4. Что такое допустимое и оптимальное решения?

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

5. Каковы основные этапы построения математической модели лп?

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

Для составления математической модели необходимо:

1. выбрать переменные задачи;

2. составить систему ограничений;

3. задать целевую функцию.

Переменные задачи – это x1,x2,…,xn.

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

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

6. В чем заключаются особенность задач лп?

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

7. Какого вида бывают целевая функция?

Целевая функция – это количественный показатель предпочтительности или эффективности решений.

Используются следующие четыре формы целевой функции.

1) Наиболее часто используется целевая функция одного внешнего параметра

2) Вторая форма целевой функции – это сумма параметров одной размерности или сумма функций от этих параметров

3) Третья форма целевой функции – ранжированная форма – представляет собой упорядоченную совокупность целевых функций первой формы с приоритетами

4) Четвертая – наиболее общая – форма целевой функции представляет собой произвольную зависимость от всех или части (но не меньше двух) разнородных внешних параметров

8. Что такое область допустимых решений?

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

9. Может ли у задачи ЛП не быть решения?

ЗЛП не разрешима (не имеет оптимального решения), если:

1) Система ограничений не совместна(не имеет решений)

2) Целевая функция не ограничена на множестве решений(Другими словами, при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min – к минус бесконечности.)

10. В чем особенность задачи ОЗЛП?

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

11. Как привести задачу ЛП к каноническому виду?

12. Может ли в области допустимых решений быть одна точка?

Да, может. Эта единственная точка и будет оптимальным решением.

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

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

1) необходимо выбрать наилучшее решение (оптимальный план) из множества возможных;

2) решение можно выразить как набор значений некоторых переменных величин;

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

4) цель выражается в форме линейной функции основных переменных.

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

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

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

3) количественное выражение выбранного критерия оптимальности в форме целевой функции;

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

Что такое математическое программирование линейное программирование

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

Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

математические модели очень большого числа экономических задач линейны относительно искомых переменных;

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

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

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

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

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

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

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

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

Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х1 , х2 , … хn
б) область G определяется системой линейных равенств или неравенств.

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

  • максимум или минимум целевой функции (критерий оптимальности);
  • систему ограничений в форме линейных уравнений и неравенств;
  • требование неотрицательности переменных.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *