1. Определение задачи математического программирования

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

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

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

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

2. Допустимое решение задачи, одр, оптимальное решение задачи.

Допустимым решением задачи называется любой n-мерный вектор

x (x = (,,…,)), удовлетворяющий системе ограничений и условию неотрицательности.

Множество допустимых решений образует ОДР.

Оптимальным решением задачи называется такое допустимое решение, при котором целевая функция достигает экстремума.

3. Экономико–математические модели задач лп: задача о банке

К экономико-математическим моделям задач ЛП относятся:Задача планирования производства, определения оптимального ассортимента продукции, о диете, о банке, составления жидких смесей, Транспортная задача

Построение экономико – математической модели.

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

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

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

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

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

Кред. Огран.

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

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

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

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

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

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

Суточный спрос на продукцию П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

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

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

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

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