Задача о банке

Собственные средства банка в сумме с депозитами составляют 100 млн. $. Не менее 35 млн. $ из этой суммы размещена в кредитах (не ликвид). Ликвидное ограничение ценных бумаг должны составлять не менее 30 %, размещенных в кредитах и ликвидных активах.

Пусть - средства, размещенные в кредитах, – средства, размещенные в ликвидных активах.

Банк. Огран. (1)

Кред. Огран.

Ликвид. Огран.

Условие неопределенности , ≥0 (4)

- доходность кредитов, - доходность ликвидных активов

F = при услов. (1) – (4).

4. Экономико – математические модели задач ЛП: задача определения оптимального ассортимента продукции.

Сырье	П1	П2	Запас
А
В

Суточный спрос на продукцию П1 < П2 на 1 ед. Спрос на продукцию П2 < 2 ед. в сутки. Оптовые цены ед. прод. 3 д. е. для П1 и 4 для П2

- П1, - П2

F = 3

2

3

5. Задача ЛП, стандартная форма, каноническая форма.

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

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

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

В общем виде модель записывается следующим образом:

Целевая функция: F (x)= c1x1 + c2x2 +... + cnxn → max(min)

ограничения: a11x1 + a12x2 +... + a1nxn {≤ = ≥} b1,

a21x1 + a22x2 +... + a2nxn {≤ = ≥} b2,

...

am1x1 + am2x2 +... + amnxn {≤ = ≥} bm;

требование неотрицательности: xj ≥ 0,

Задача имеет каноническую форму, если является задачей на максимум (минимум) линейной функции F и ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х1, х2,..., хn являются неотрицательными:

F (x) =

, i= 1,2…m

, j = 1,2…n

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной функции f и система ограничений ее состоит из одних линейных неравенств типа «<=». Все переменные задачи неотрицательны.

F (x) =

, i= 1,2…m

, j = 1,2…n

Свойства задачи ЛП.

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

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

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

6. Целевая функция, градиент

Целевая функция - функция, связывающая цель (оптимизируемую переменную, т.е. найти max или min) с управляемыми переменными в задаче.

Это функция, минимум или максимум которой требуется найти.

Целевая функция: F (x)= c1x1 + c2x2 +... + cnxn → max(min)

Градиент функции – вектор, координаты которого равны частным производным первого порядка

Градиент линейной функции f (x1,x2) = c1x1+c2x2 равен вектору коэффициентов функции. С = (c1, C2)

Градиент функции в точке определяет направление наискорейшего возрастания функции в этой точке.

7. Двойственная задача и ее свойства

Двойственная задача - это вспомогательная задача ЛП, формулируемая с помощью опред-ых правил непосредственно из условий исходной (прямой) задачи.

F (x)= c1x1 + c2x2 +... + cnxn → max;

a11x1 + a12x2 +... + a1nxn ≤ b1,

a21x1 + a22x2 +... + a2nxn ≤ b2,

am1x1 + am2x2 +... + amnxn ≤ bm;

xj ≥ 0

g (y)= b1y1 + b2y2 +... + bmym → min;

a11y1 + a21y2 +... + am1ym ≥ c1,

a12y1 + a22y2 +... + am2ym ≥ c2,

a1ny1 + a2ny2 +... + amny ≥ cn;

yi ≥ 0

Если в исходной задаче ищется маx целевой функции, то в двойственной ей - мин.

В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

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

Условие неотрицательности переменных сохраняется в обеих задачах.

Переменных у двойственной задачи сколько ограничений у исходной задачи

Ограничений у двойственной задачи столько, сколько переменных.

8. Первая теорема двойственности и ее следствия

Теорема. Двойственные задачи одновременно разрешимы или не разрешимы и в случае их разрешимости оптимальные значения целевых функций совпадают.

Следствие 1. Если исходная задача является задачей в канонической форме и ее оптимальная симплекс таблица известна, то оптимальное решение двойственной задачи есть (, ) =

Следствие 2. Если исходная задача является задачей в стандартной форме и ее оптимальная симплекс таблица известна, то оптимальное решение двойственной задачи есть =

94. Экономическая интерпретация двойственной задачи.

F =

i = 1,2…m

j = 1,2…n

n- число технологий произведенной продукции

– цена одной ед. продукта, произведенной по j технологии

F = – прибыль

А – технологическая матрица

– кол – во ресурса вида i необходимого для производства продукта j технологии

- кол-во ресурса вида i использующегося в производстве

– запас ресурса вида i.

10. Транспортная задача, математическая модель и ее свойства.

Транспортная задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения

Число пунктов производства – m

i= 1,2…m – количество продукта, произведенного на i пункте.

Количество пунктов потребителя – n

j = 1,2…n – потребность j пункта потребления.

- цена перевозки ед. продукции из i пункта в j.

Классическая постановка задачи

Требуется организовать перевозку продукции из пункта производства в пункт потребления так, чтобы весь товар из пунктов производства был вывезен, удовлетворяя потребность пунктов потребления и минимизировать стоимость перевозки

Математическая модель задачи:

- кол-во ед. продукта, перевозимого с i пункта производства в j пункт.

Кол – во продукта, вывезенного с i пункта произв.:

i = 1,2..m

Кол-во ед. продукта:

j = 1,2..n

Критерий – суммарные затраты:

F =

Свойства транспортной задачи:

Транспортная задача разрешима тогда, когда выполняемы условия баланса:

- закрытая тр. Зад.

Ранг матрицы ограничений тр. Зад. = m+n-1.

11. Метод минимального элемента, метод северо-западного угла.

Выбрали клетку с координатами (i j) – свободная северо – запад.

то ставим прочерки во всех свободных клетках i строки.

то ставим прочерки во всех свободных клетках j столбца.

то ставим прочерки во всех свободных клетках i строки или j столбца.

Пересчитываем:

До тех пор пока везде не будут числа или прочерки. Клетки, в которых числа – базисные. Клетки с прочерками – не базисные. Кол-во базисных = m+n-1.

Дата добавления: 2015-08-09