Каноническая и стандартная задачи линейного программирования
Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[3]:
Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)
,
.
Задача линейного программирования будет иметь канонический вид, если в общей задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства[4]:
,
Основную задачу можно свести к канонической путём введения дополнительных переменных.
Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств[5].
Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.
Теоремы линейного программирования.
Фото
Постановка задачи об использовании ресурсов
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:
задача об оптимальном использовании ресурсов при производственном планировании;
задача о смесях (планирование состава продукции);
задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или задача о рюкзаке);
транспортные задачи (анализ размещения предприятия, перемещение грузов).
Популяция бактерий численностью x в каждый момент времени имеет скорость, пропорциональную этой численности с коэффициентом пропорциональности k. Получим аналитическую зависимость:
kxx=?
с начальными условиями
.)0(0xx=
Решим поставленную задачу Коши аналитически.
.ln0ktktexxCexktxkdtxdx?====
Математической моделью является аналитическая функция с двумя параметрами и k. Варьируя значения параметров, получаем следующие режимы модели: ktexx?=0 0x
1. При (рождаемость ниже смертности) функция асимптотически стремится к нулю – популяция вырождается, 0
2. При (рождаемость равна смертности) функция имеет постоянное значение – популяция стабильна, 0=k
3. При (рождаемость выше смертности) функция асимптотически стремится к бесконечности – популяция неограниченно растет. 0k
Динамику поведения численности популяции бактерий хорошо иллюстрирует рис. 3. Построенная математическая модель не учитывает многих факторов: ограниченность ресурсов потребления, географическое распределение популяции, конкуренцию с другими видами, влияние
патогенных факторов. Для совершенствования модели составляют другие дифференциальные уравнения, много сложнее исходного. Чем сложнее уравнение, тем сложнее его решить и получить целостную картину исследуемого процесса.
Рис. 3. Режимы модели бактериального роста: рост (сплошная), стабильность (пунктир), вымирание (штриховка)
9Симметричная двойственная задача
Парой симметричных двойственных задач называютсядве, тесно связанные между собой задачи ЛП, которые удобнозаписать схематически в виде (36). Задача ЛП, в которой
целевая функция максимизируется, а все неравенства типа?, называется стандартной задачей максимизации; еслицелевая функция минимизируется, а все неравенства типа
17?— стандартной задачей минимизации. Пара симметричныхдвойственных задач состоит из стандартной задачи максимизациии стандартной задачи минимизации, причем эти задачи обладаютрядом особенностей, которые хорошо видны в схеме (36) ипозволяют сформулировать правила составления двойственныхзадач.
Задача 1
Maxf(X) = c1x1 + c2x2 + c3x3
при условиях:
x1 ? 0,
x2 ? 0,
x3 ? 0,
a11x1 + a12x2 + a13x3 ? b1,
a21x1 + a22x2 + a23x3 ? b2.
Задача 2
Min g(Y ) = b1y1 + b2y2
приусловиях:
a11y1 + a21y2 ? c1,
a12y1 + a22y2 ? c2,
a13y1 + a23y2 ? c3,
y1 ? 0,
y2 ? 0.
(36)
Правила составления пары симметричных двойственных задач
1. Одна из задач является стандартной задачей максимизации,другая — стандартной задачей минимизации.
2. Количество неизвестных в одной из задач равно количествуосновных ограничений в другой задаче.
3. Матрица коэффициентов при неизвестных в неравенствходной задачи получается транспонированием матрицыкоэффициентов другой задачи.
4. Свободные члены неравенств одной задачи совпадают скоэффициентами целевой функции другой задачи.
10Теоремы двойственности
Первая теорема двойственности
Если решить одну из двойственных задач (36), то наосновании теорем двойственности можно сделать вывод осуществовании или отсутствии решения другой задачи.
w(x) = h(y).
вторая теорема двойственности
Допустимые решения xи y соответственно прямой и двойственной задачи оптимальны тогда и только тогда, когда выполняется условие:
yi(aix ? bi) = 0 (i?I),
(cj ? yAj)xj = 0 (j?J)
11Применение теории двойственности при планировании производства
13Таблица 4.2:
Пункты B1 B2 B3 Запасы
Решение. Начинаем с северо-западного угла, то есть определяем перевозку x11 по формуле x11 = minf20; 10g = 10. Тогда в пункте B1 потребностиудовлетворены и, следовательно, x21 = 0 (в табл. 4.2 в клетке A2B1 ставится точка). Первый столбец выбывает из рассмотрения.Продолжаем с северо-западного угла, то есть вычисляем x12 = minf(20¡10); 20g = 10. Тогда запасы в пункте A1 исчерпаны и x13 = 0 (в табл. 3.2ставится точка). При этом первая строка выбывает из рассмотрения.Продолжаем с северо-западного угла, то есть x22 = minf40;(20¡10)g =10. Тем самым потребности в пункте B2 удовлетворены, и второй столбецвыбывает из рассмотрения.Подсчитываем последний элемент, находящийся в северо-западном углу: x23 = minf(40¡10); 30g = 30.
Получаемый методом северо-западного угла начальный план перевозок не зависит от их стоимости и поэтому в общем случае далек от наилучшего. В методе минимального элемента учитываются стоимости перевозок. Вследствие этого, соответствующий начальный план, как правило, позволяет обеспечить меньшую суммарную стоимость, более близкую к оптимальной. В этом методе по формуле (4.14) последовательно заполняются клетки с наименьшей стоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то из них выбирается любая.
14Метод потенциалов
Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определитьотправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).
Общий принцип определения оптимального плана транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.
Составим двойственную задачу
1. , — любые
2.
3. 
Пусть есть план
Теорема (критерий оптимальности): Для того чтобы допустимый план перевозок в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа , , что
если , (6)
если . (7)
числа и называются потенциалами пунктов отправления и назначения соответственно.
Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план. Для этого плана, в котором базисных клеток, можно определить потенциалы и так, чтобы выполнялось условие (6). Поскольку система (2)-(4) содержит уравнений и неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (6) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины . Если оказалось, что , то план оптимален. Если же хотя бы в одной свободной клетке , то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке.
16Метод Гомори целочисленного программирования
симплексным метод находят оптимальное решение задачи. если решение целочисленное, то задача решена. если же оно не целочисленное и содержит хотя бы одну дробную координату, то накладывают дополнительное ограничение по целочисленности и вычисления продолжают до получения нового решения. если и оно является не целочисленным, то вновь накладывают дополнительное ограничение. вычисления продолжаются до тех пор, пока не будет получено целочисленное решение или показано, что задача не имеет целочисленного решения.
1718Метод множителей Лагранжа в нелинейном программировании
Дана задача нелинейного программирования
при ограничениях:
Предположим, что функции f(x1, х2,…, xп) и gi(x1, x2,…, xп) непрерывны вместе
со своими первыми частными производными.
Ограничения заданы в виде уравнений, поэтому для решения задачи
воспользуемся методом отыскания условного экстремума функции нескольких
переменных.
Для решения задачи составляется функция Лагранжа
где ?i — множители Лагранжа.
Затем определяются частные производные:
Приравняв к нулю частные производные, получим систему
19 Чистый приведенный доход проекта
NPV – чистый дисконтированный доход – это настоящая стоимость будущих денежных поступлений дисконтированная по рыночной процентной ставке, минус современная оценка стоимости инвестиций. Можно сказать, что NPV это разность между прогнозным поступлением денежных средств, полученных в результате проектных инвестиций, и ожидаемым оттоком денежных средств.
{module 297}
NetPresentValue (NPV) или метод чистого дисконтированного дохода(ЧДД) применяется для того, что бы оценить эффективность инвестиционных проектов, оценить стоимость имущества и имущественных прав, а также для отражения активов и обязательств в бухучете.
NPV обычно вычисляется по формуле:
Где CFt – чистый денежный поток средств,
rt – ставка дисконта в год t,
n – количество периодов прогнозирования.
Помимо этой классической формулы можно выделить еще три других подхода к оценке чистого приведенного дохода.
20Будущая стоимость — англ. FutureValue, является суммой, в которую на определенную дату в будущем превратится определенная сумма денег, инвестированная сегодня под заранее известную процентную ставку. Она рассчитывается на базе концепции стоимости денег во времени, основываясь на процентных ставках и настоящей стоимости. Будущая стоимость инвестиций зависит от того, каким методом начисляются проценты: простые проценты , сложные проценты
или аннуитет 
.
21Внутренняя норма доходности (IRR)
Внутренняя норма доходности — норма прибыли, порожденная инвестицией. Это та норма прибыли (барьерная ставка, ставка дисконтирования), при которой чистая текущая стоимость инвестиции равна нулю, или это та ставка дисконта, при которой дисконтированные доходы от проекта равны инвестиционным затратам. Внутренняя норма доходности определяет максимально приемлемую ставку дисконта, при которой можно инвестировать средства без каких-либо потерь для собственника.
IRR = r, при котором NPV = f(r) = 0,
Ее значение находят из следующего уравнения:
NPV(IRR) — чистая текущая стоимость, рассчитанная по ставке IRR,
CFt — приток денежных средств в период t;
It — сумма инвестиций (затраты) в t-ом периоде;
n — суммарное число периодов (интервалов, шагов) t = 0, 1, 2, …, n.
22Метод расчета срока окупаемости. (PP)
Этот метод, являющийся одним из самых простых и широко распространенных в мировой учетно-аналитической практике, не предполагает временной упорядоченности денежных поступлений. Алгоритм расчета срока окупаемости (РР) зависит от равномерности распределения прогнозируемых доходов от инвестиции. Если доход распределен по годам равномерно, то срок окупаемости рассчитывается делением единовременных затрат на величину годового дохода, обусловленного ими. При получении дробного числа оно округляется в сторону увеличения до ближайшего целого. Если прибыль распределена неравномерно, то срок окупаемости рассчитывается прямым подсчетом числа лет, в течение которых инвестиция будет погашена кумулятивным доходом. Общая формула расчета показателя РР имеет вид:
РР = min n, при котором
(4.9)
Нередко показатель РР рассчитывается более точно, т.е. рассматривается и дробная часть года; при этом делается молчаливое предположение, что денежные потоки распределены равномерно в течение каждого года. Так, для проекта с денежным потоком (млн руб.): -100 40 40 40 30 20 значение показателя РР равно 3 годам, если расчет ведется с точностью до целого года, или 2,5 года в случае точного расчета.
Некоторые специалисты при расчете показателя РР все же рекомендуют учитывать временной аспект. Соответствующая формула для расчета дисконтированного срока окупаемости, DPP, имеет вид:
(4.10)
DPP = min n, при котором удовлетворяется (4.10)
Необходимо отметить, что в оценке инвестиционных проектов критерии РР и DPP могут использоваться двояко: а) проект принимается, если окупаемость имеет место; б) проект принимается только в том случае, если срок окупаемости не превышает установленного в компании некоторого лимита.
23Индекс рентабельности (Pl)
Индекс рентабельности (прибыльности, доходности) инвестиций (PI)рассчитывается как отношение чистой текущей стоимости денежного притока к чистой текущей стоимости денежного оттока (включая первоначальные инвестиции):
если PI 1, то проект следует принять,
если PI = 1, то проект является не прибыльным, не убыточным,
если РI 1, то проект следует отвергнуть.
Индекс рентабельности, в отличие от чистого приведенного дохода, является относительным показателем, характеризующим уровень доходов на единицу затрат. Чем он выше, тем больше отдача инвестиций в данный проект. Благодаря этому критерий PI очень удобен при выборе одного проекта из ряда альтернативных, имеющих примерно одинаковые значения NPV , либо при комплектовании портфеля инвестиций с целью максимизации суммарного значения NPV.
К недостаткам метода можно отнести его неоднозначность при дисконтировании отдельно денежных притоков и оттоков.
25Математическая модель инфляции
Индексы и темпы роста инфляции.Инфляция является очень сложным и важным финансово-экономическим явлением современного мира. Она зависит от многих факторов и является предметом изучения ряда разделов экономической теории, в которых широко применяются методы теории вероятностей и математической статистики. Поскольку инфляция проявляется в падении реальной покупательской способности денег и общей повышении уровня цен внутри страны, то ее необходимо учитывать при проведении среднесрочных и особенно долгосрочных финансовых операций. Поэтому рассмотрим простейшие способы ее учета.
Темпы инфляции измеряются с помощью системы индексов инфляции, которые характеризуют среднее изменение уровня цен для некоторого фиксированного набора (корзины) товаров и услуг за определенный период времени. Состав этих товаров зависит от цели исследования. Например, в российских газетах регулярно печатается индекс инфляции (роста цен) за некоторый календарный период, рассчитанный на основе продовольственной потребительской корзины для различных регионов страны.
Рассмотрим для определенности потребительскую корзину из k названий и примем, что товар или услуга s входит в количестве qsсоответствующих единиц, а цена за эту единицу в момент t составляет xs(t) денежных единиц товара s, s=1,2,…,k. Тогда стоимость корзины в момент t равна
?==ksssqtxtX1)()(
Определение. Индексом инфляции(ростом потребительских цен) за время от t1 до t2 называется безразмерная величина
121221,)()(),(tttXtXttH=
а темпом инфляцииза этот период называется
. 1),()()()()(211122,1?=?=ttHtXtXtXtth
Из определения следует, что H(t1,t2)=1+h(t1,t2).
Индекс инфляции H показывает, во сколько раз, а темп h (после умножения на 100) – на сколько процентов выросли цены за рассматриваемый период.
