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

Введение

Математическое программирование является большим разделом в исследовании операций. Он состоит из теории и методов решения задач о нахождении экстремумов функций на множествах, определяемых равенствами или неравенствами.
Целью дисциплины является изучение и освоение методов математического программирования наиболее часто используемых при решении оптимизационных задач в области экономики, планирования и проектирования.
Формирование практических навыков, применения методов и алгоритмов оптимизации в инженерной деятельности.
Цель реферативной работы- изучить математическое программирование.
Для реализации цели реферативной работы были поставлены следующие задачи:
1. Рассмотреть понятие математического программирования
2. Изучить понятие линейного программирования. Виды задач линейного программирования
3. Выявить прямую и обратную задачу линейного программирования
4. Проанализировать производственную, транспортную и задачу о смесях
5. Выполнить практическую задачу
1. Понятие математического программирования
Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями[5,c.165].
Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции.
Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.
Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.
Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач[3,c.90].
В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:
1) задачи линейного программирования,
2) задачи нелинейного программирования.
Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования.
Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования[8,c.101].
2. Понятие линейного программирования. Виды задач линейного программирования
Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач[2,c.209].
Термин " линейное программирование " возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены[1,c.109].
Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях[7,c.90].
Общая форма задачи имеет вид: найти  при условиях
(1)
, где
Здесь и далее нам удобнее считать с и аі вектор - строками, а x и b=(b1,...,bm)T - вектор столбцами.
Наряду с общей формой широко используются также каноническая и стандартная формы.
Как в канонической, так и в стандартной форме
(2)
т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается).
Отличие же между этими формами состоит в том, что в одном случае I2 = 0, а в другом - I1 = 0.
Задача ЛП в канонической форме: [8,c.201].
w=cx → min (3)
Ax=b (4)
x≥0 (5)
Задача ЛП в стандартной форме:
Задача ЛП в канонической форме:
w=cx → min
Ax>b
x≥0
В обоих случаях А есть матрица размерности m x n, i -я строка которой совпадает с вектором аi[3,c.70].
Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой "легко" преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной).
Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме[6,c.90].
Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.
3. Прямая и обратная задача линейного программирования
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой.
Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования (таблица 1)[4,c.70].
Таблица 1- Связь прямой и обратной задачи линейного программирования
Правила составления двойственной задачи:
1. Каждому i-му ограничению исходной задачи соответствует переменная  yj двойственной задачи и, наоборот, каждому j-му ограничению двойственной задачи соответствует переменная xj исходной задачи.
 2. Матрицы А ограничений 1 – 2 и А' ограничений 3' – 4' (таблица 1) взаимно транспонированы.
Следовательно, строка коэффициентов aij в j-м ограничении двойственной задачи есть столбец коэффициентов при xj в ограничениях 1 – 2 исходной задачи, и наоборот[9,c.101].
 3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи

. При этом максимизация меняется на минимизацию, и наоборот.
 4. В каждой задаче ограничения-неравенства следует записывать со знаком «≤» при максимизации и со знаком «≥» – при минимизации.
 5. Каждому i-му ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности yij>0, а равенству – переменная yi без ограничения на знак.
Наоборот, неотрицательной переменной xj≥0 соответствует в двойственной задаче j-е ограничение - неравенство, а произвольной переменной – равенство.
Существование зависимости между решениями прямой и двойственной задач характеризуются следующими леммами и теоремами двойственности.
Лемма 11.1 (основное неравенство теории двойственности). Если  – некоторый план исходной задачи, а  – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане  всегда не превосходит значение целевой функции двойственной задачи при плане , т.е. 
Лемма 11.2. Если  и  – допустимые решения взаимно двойственных задач, для которых выполняется равенство , то  – оптимальное решение исходной задачи, а  – оптимальное решение двойственной задачи[2,c.202].
    Теорема 11.1. Первая теорема двойственности (основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план , то и другая имеет оптимальный план  и значения целевых функций задач при их оптимальных планах равны между собой, т. е.
.
Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то область допустимых решений другой задачи пустая.
Из этой теоремы вытекают необходимые и достаточные условия:
a)   разрешимости задач – существование хотя бы одного допустимого плана у каждой задачи;
б) оптимальности допустимых  планов  X  и  Y – выполнение  равенства F(X) = T(Y)[7,c.95].
    Теорема 11.2. Вторая теорема двойственности (теорема о дополнительной нежесткости). Для того чтобы два допустимых решения  и  пары двойственных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений
(*)
(**)
        Данная теорема позволяет:
a) установить оптимальность решения одной задачи по свойствам решения двойственной;
б) найти оптимальное решение одной задачи по решению двойственной.
Теорема верна для симметричной двойственной пары. Для задач в канонической и общей формах соотношения (*) и (**) верны только для ограничений в виде неравенств и для неотрицательных переменных.
Полученные выше результаты непосредственно характеризуют взаимосвязь прямой и двойственной  задач:
1.     В оптимуме
2.     На любой итерации процесса решения прямой задачи
Эти соотношения позволяют дать важную экономическую интерпретацию двойственности и переменным двойственной задачи. Чтобы сделать это с помощью некоторых формальных категорий, рассмотрим прямую задачу как задачу распределения ограниченных ресурсов с целевой функцией, подлежащей максимизации[4,c.80].
Условия прямой задачи можно интерпретировать следующим образом. Коэффициент  представляет собой прибыль, приходящуюся на единицу продукции -го вида производственной деятельности. Расход ресурса , запасы которого ограничены величиной , на единицу продукции -го вида производственной деятельности равен  единицам этого ресурса. Переменные двойственной задачи  представляют ценность единицы ресурса  (в экономической литературе они получили различные названия: неявные, учетные, теневые).
Двойственные оценки могут быть использованы для определения приоритета используемых ресурсов в соответствии с их вкладом в величину целевой функции.
В соответствии с основным неравенством теории двойственности в случае неоптимальных допустимых решений . Формулировка этого неравенства в рамках экономической интерпретации выглядит следующим образом:
(Прибыль) < (Общая ценность ресурсов).
Из этого соотношения следует, что до тех пор, пока прибыль меньше суммарной ценности ресурсов, решение остается неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов.
Чтобы дать представление о соответствующих обозначениях, часто встречающихся в литературе по линейному программированию, введем следующее определение: [6,c.98].
 
– суммарная оценка ресурсов, используемых при производстве единицы продукции  -го вида.
Разность  равна фигурирующему в симплекс-таблице -коэффициенту при переменной  (в наших обозначениях ). Ее часто называют приведенными издержками -го вида производственной деятельности.
Условие оптимальности (в задаче максимизации), используемое в симплекс-методе, состоит в том, что вид производственной деятельности, не представленный в текущем решении (ему соответствует независимая переменная ) должен вводиться в последующее решение с отличным от нуля и положительным уровнем использования () только в том случае, когда -коэффициент при данной переменной отрицателен. Дадим экономическую интерпретацию этому условию. Неиспользованный  вид производственной деятельности  должен быть представлен в решении только в том случае, если , т.е. когда
Таким образом, пока прибыль превышает суммарную оценку ресурсов, уровень использования данного вида производственной деятельности следует увеличивать. Следует заметить, что мы увеличиваем уровень его использования до того значения, при котором -коэффициент при данной переменной станет равным нулю. Это эквивалентно полной реализации всех возможностей, связанных с получением прибыли от данного вида производственной деятельности[3,c.70].
4. Производственная, транспортная и задачи о смесях
Производственная задача.
Существует некоторое предприятие, которое может выпускать некоторые изделия. На то, чтобы их выпустить необходимы различные ресурсы. Задано, сколько и каких ресурсов необходимо для каждого изделия, задано сколько ресурсов у нас имеется, и задано, сколько предприятие выручит за продажу произведенных изделий. Необходимо выбрать, какие изделия и в каком количестве выпускать, чтобы прибыль предприятия была максимальной[5,c.201].
Фабрика выпускает продукцию двух видов: П1 и П2. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта - А, В, С. Максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы сырья А, В, С на 1 тыс. изделий П1 и П2 приведены в табл.
Исходный продукт
Расход исходных продуктов на 1 тыс. изделий (т)
Максимально возможный запас (т)
П1
П2
А
В
С
1
2
1
2
1
0.8
6
8
5
Изучение рынка сбыта показало, что суточный спрос на изделия П2 никогда не превышает спроса на изделия П1 более чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П2 никогда не превышает 2 тыс. шт. в сутки.
Оптовые цены 1 тыс. шт. изделий П1 равны 3 тыс. руб., 1 тыс. шт. П2 - 2 тыс. шт.
Какое количество изделий (в тыс. шт.) каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?
Построение математической модели следует начать с идентификации переменных (искомых величин). После этого определяются целевая функция и ограничения через соответствующие переменные.
В рассматриваемом примере имеем следующее:
Переменные.
Так как нужно определить объёмы производства каждого вида продукции, переменными являются:
X1 - суточный объём производства изделия П1в тыс. шт.;
Х2 - суточный объём производства изделия П2в тыс. шт.
Целевая функция. Так как стоимость 1 тыс. изделий П1 равна 3 тыс. руб., суточный доход от её продажи составит 3Х1тыс. руб. Аналогично доход от реализации Х2 тыс. шт. П2 составит 2Х2 тыс. руб. в сутки. При допущении независимости объёмов сбыта каждого из изделий общий доход равен сумме двух слагаемых - дохода от продажи изделий П1 и дохода от продажи изделий П2.
Обозначив доход (в тыс. руб.) через f(X), можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения X1 и Х2, максимизирующие величину общего дохода:
f(X) = 3X1 + 2X2, Х = (Х1, Х2)
Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход исходных продуктов А, В и С и спрос на изготовляемую продукцию, что можно записать так:
Это приводит к трём ограничениям:
Х1 + 2Х2 ≤ 6 (для А),
2Х1 + Х2 ≤ 8 (для В),
Х1 + 0.8Х2 ≤ 5 (для С).
Ограничения на величину спроса на продукцию имеют вид:
Х2 – X 1 ≤ 1 (соотношение величин спроса на изделия П1 и П2),
Х2 ≤ 2 (максимальная величина спроса на изделия П2).
Вводятся также условия неотрицательности переменных, т.е