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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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) математическая формулировка задачи как задачи отыскания экстремума целевой функции при условии выполнения ограничений, накладываемых на переменные. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач, блочного программирования и др.

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

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

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

U = f(x) → max; x ∈ M,

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

g (x) = b,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\min сх$

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

$& a_i x - b_i \geq 0, \quad i \in I_1, \\ & a_i x - b_i = 0, \quad i \in I_2, \\ & x_j \geq 0, \quad j \in J_1$

$I_1 \cup I_2 & = \< 1 , \ldots , m \> , \; I_1 \cap I_2 = \emptyset , \; J_1 \subset \ < 1, \ldots , n \>, \; x = ( x_1 , \ldots , x_n )^T , \\ c & = ( c_1 , \ldots , c_n ) , \; a_i = (a_ , \ldots , a_) , \; i = 1 , \ldots , m» /> Здесь и далее нам удобнее считать с и аі вектор — строками, а x и b=(b1. bm) T — вектор столбцами. Наряду с общей формой широко используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме <img decoding=$ $w = cx \rightarrow \min$ ( 2.1)

( 2.2)

$x \geq 0.$

( 2.3)

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

$w & = cx \rightarrow \min \\ Ax & \geq b \\ x & \geq 0$

В обоих случаях А есть матрица размерности m x n , i -я строка которой совпадает с вектором а_i .

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

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