Лекция 2
.docЛекция 2
Классификация задач математического программирования.
В математическом программировании по признаку «характер информации»
задачи удобно подразделять на детерминированные и стохастические.
Если вся исходная информация, используемая при построении математической модели заранее известна и достоверна, то методы оптимизации таких задач относятся к детерминированным или методам обоснования решения в условиях определенности.
Среди детерминированных задач выделяют следующие:
Линейное программирование (ЛП). В зависимости от особенностей структурных ограничений в математической модели задачи ЛП подразделяются на ОБЩУЮ задачу ЛП и СПЕЦИАЛЬНЫЕ задачи (транспортная и обобщенная транспортная задачи);
Если переменные (неизвестные величины) входят в ЦФ и в структурные ограничения в 1-ой степени, то говорят о задаче линейного программирования.
Решить задачу ЛП – это значит найти такие значения переменных, которые удовлетворяют всем ограничениям задачи, а ЦФ достигает искомого экстремума.
Линейное программирование (ЛП) – один из первых и подробно изученных разделов математического программирования. Именно с раздела линейное программирование и начало развиваться математическое программирование.
(Линейное программирование применяется в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.)
Термин «линейное программирование» возник в результате неточного перевода с английского «linear programming». Одно из значений слова «programming» – составление планов, планирование. Следовательно, правильным переводом английского «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины.
Первые работы по линейному программированию вышли в Ленинградском Университете. Автором был Канторович Леонид Витальевич (1912-1986).
Родился в 1912г.в Санкт-Петербурге. В 14 лет поступил в Ленинградский университет на математическое отделение и окончив его в 1930г, остается на преподавательской работе. КанторовичЛ.В. занимается исследованиями на кафедре математики, и в 1935г (ему 23 года) ему присваивается ученая степень доктора физико-математических наук.
В 1938 году, Канторович привлекается в качестве консультанта на фанерную фабрику и решает задачу эффективного использования оборудования.
Канторович понял, что решение задачи сводится к максимизации линейной функции многих переменных при наличии ограничений в форме равенств и неравенств.
Так впервые была сформулирована задача производственного планирования, как задача ЛП и разработан метод для ее решения. Результаты его труда были опубликованы в 1939 г. в работе «Математические методы организации и планирования производства». К сожалению в это время эти результаты не были должным образом оценены.
Признание пришло позже. В1975г. академик Канторович Л.В. вместе с американским профессором Тьяллингом . Купмансом (1910-1985) (США) были удостоены Нобелевской премии по экономике «за вклад в теорию оптимального распределения ресурсов».
На Западе отцом-основателем этого направления считают американского математика Джорджа Данцига (1914-2005).
Во время 2-ой Мировой войны Данциг работал в командовании военно-воздушных сил и занимался программированием поставок военной техники. Термин «программирование» был сугубо военным и означал составление планов поставок.
Данциг предложил использовать линейную модель, а в конце 40-х годов изобрел универсальный численный метод решения, который называется Симплексный метод.
Большой вклад в развитие оптимизационных методов внесли: Канторович Л.В., Немчинов В.С., Новожилов В.В. В 1965 г. Они были удостоены Ленинской премии за разработку и внедрение оптимизирующих методов.
Значительный вклад в теорию и методы линейного программирования внесли С. Гасс, А. Таккер, Р. Гомори, Г. Кун, Т. Саати, Г. Вагнер, Д.Б. Юдин, Е.Г. Гольштейн и др.
Целочисленное программирование (ЦП) – все или часть переменных должны удовлетворять требованию целочисленности;
Параметрическое программирование (ПП). Матмодели задач могут содержать коэффициенты, которые являются функциями некоторого параметра.
Нелинейное программирование (НП). В задачах этого класса нелинейные целевая функция и (или) ограничения;
Динамическое программирование (ДП). Задачи содержат большое число переменных, и параметры ЦФ и ограничений зависят от времени, а поиск решения проводится последовательно по этапам. Методы ДП используют идеи рекуррентного подхода.
Стохастические задачи МП.
Если параметры, входящие в ЦФ или ограничения имеют случайный характер, недостоверные значения или приходится решать задачи в условиях риска без точного знания информации о сложившейся ситуации, то говорят о проблеме стохастической оптимизации, а раздел называется стохастическим программированием.
Задача производственного планирования (или общая Задача ЛП). Различные формы записи ее модели.
Постановка задачи
Предприятие может выпускать n видов продукции: П1, П2 ., Пj ., Пn (наименование) j – поточный индекс виду продукции j= (1; n)
Для производства продукции предприятие имеет в своем распоряжении m видов производственных факторов ( ресурсов) Ф1, Ф2 ., Фi,, Фm (наименование)
i – поточный индекс производственного фактора (i =1, m)
Известны запасы каждого производственного фактора b1, b2 ., bi ., bm (единицы)
Известен удельный расход i-го ресурса на выпуск одного изделия j-го вида aij.
Предприятие получает доход сj, денежных единиц за выпуск одного изделия j-го вида.
Составить план выпуска продукции, обеспечивающий получение наибольшего дохода.
В качестве искомых неизвестных (параметров управления) примем:
xj– количество единиц выпускаемой продукции j-того вида.
Запишем математическую модель задачи в стандартной форме, т.е. между левой и правой частью ограничений есть знак неравенства).
Развернутая (координатная форма записи):
Целевая функция, экономический смысл, которой – максимизировать доход, получаемый от выпуска всей продукции:
(1)
Структурные ограничения – отражают требование не перерасходовать запасы каждого производственного фактора
– – – – – – – – – – – – – – (2)
– – – – – – – – – – – – – –
Условие неотрицательности параметра управления:
(3)
c1, с2,… сj, сn - называются коэффициентами при неизвестных в целевой функции.
– технологические коэффициенты, произвольные числа, встречаются в ограничениях произвольное число раз, это коэффициенты при неизвестных в левой части структурных ограничений.
Сj ,bi – заданные постоянные величины.
Полученная модель относится к классу задач ЛП, называемой ОБЩЕЙ. Признаки общей задачи : технологические коэффициенты принимают произвольные значения, а каждая переменная входит в ограничение произвольное число раз.
Формы математических моделей общей задачи ЛП
В зависимости от соотношения между левыми и правыми частями ограничений, формы математической модели общей задачи ЛП делятся на:
Стандартную, если между левой и правой частями ограничений стоит знак неравенства. В экономике, при неравенствах вида ≤,как правило, формулируются задачи на максимум, а при неравенствах - ≥, как правило, на минимум.
Каноническая форма, если ограничения заданы знаком равенства, при такой форме возможна и максимизация и минимизация целевой функции.
Смешанная форма, если в ограничениях присутствуют как знак равенства, так и неравенства.
Задачу максимизации целевой функции всегда можно привести к задаче на минимум этой же линейной функции, взятой со знаком «минус», при этом используется соотношение:
maxZ = min (– Z)
т.е. для приведения задачи «на максимум» к задаче «на минимум», достаточно в коэффициентах целевой функции поменять знаки на противоположные, найти минимум полученной функции (– Z). Аналогично, в случае необходимости, можно привести задачу «на минимум» к задаче «на максимум».
Формы записи экономико-математической модели
Запись с помощью знаков суммирования
– max
Векторно-матричная форма записи задачи
Если воспользоваться матричными обозначениями, то задачу ЛП можно записать компактно. Обозначим С=(с1,с2, …, сj, …, сn ) – вектор-строка стоимостей единиц продукции.
x1 b1
x2 b2
. .
X= xj ; – вектор-стовпець змінних; B = bi – вектор-стовпець ;
. (або параметрів управління) . правых xn bm
a11 a12 … a1j a1n
a21 a22 … a2j a2n
A= – – – – – – –матрица условий,
ai1 ai2 … aij ain (матрица технологических коэффициентов)
– – – – – –
am1 am2 … amj amn
0= 0
0 нулевой вектор– столбец
0
Тогда задача (1)-(3) запишется:
Z= CX – max (1’)
AX ≤ B (2’)
X ≥ 0 (3’)
Векторная форма записи
Еще один способ можно получить, если j-ый столбец матрицы А обозначить через Аj , а матрицу А представить как строку длиной n, состоящую из m-мерных векторов-столбцов.
Z=CX- max (1’’)
x1A1+x2A2+ …+xjAj+ …+ xnAn ≤ B (2’’)
X ≥ 0 (3’’)