1

    Дисциплина: Экономика
    Тип работы: Реферат
    Тема: 1

    1. Примеры построения мат модели и канонич задачи ЛП.

    Пример:

    Предположим, что предприятие выпускает 2 вида продукции P1 P2. используя, при этом 3 вида ресурса S1, S2, S3. Запас ресурса, а также кол-во ед ресурса затрачиваемое на

    изготовление ед продукции приводится в след таблице . Реализация одной ед прод P1 приносит прибыль в 5уе. P2 – 7уе. Необходимо выяснить в каком кол-ве необходимо

    вып-ть прод P1 P2, чтобы прибыль была наибольшей. Необходио составить экономико-мат модель этой задачи. X1 – кол-во ед продукции P1, кот необходимо выпустить. X2 – P2. Тогда для

    изготовления указанных обоих видов продукции необходимо ресурсов в кол-ве: (1) В силу ограниченности запасов ресурсов должна выполняться эта сис-ма. (2)

    x1>=0 x2>=0 Суммарная прибыль которой может быть получена при реализации всей продукции F=…

    Таким образом, задача свелась к нахождению x1 x2, удовлетворяющих нерав-вам (1) (2) при кот фция F принимает наиб значение.

    Общая постановка задачи ЛП:

    Общей задачей ЛП нзв задача нахождения X=(x1, …, xn), удовлетворяющего (1) (2) (3) при кот (4) приним оптимальное значение.

    Канонич задача ЛП нзв задача нахождения X=(x1, …, xn), удовлетворяющего (1) (3) при кот (4) оптимальна.

    Стандартная задача ЛП нзв задача нахождения X=(x1, …, xn), удовлетворяющего (2) (3) при кот (4) оптимальна.

    X=(x1, …, xn), удовлетворяющий (1) (2) (3) нзв допустимым решением.

    ///Необходимо найти максимальную прибыль или минимальные затраты при наличии некоторых реальных экономич, временных, трудовых ограничений. С мат точки зрения выше сказанное

    означает нахождение максимума и минимума функции многих переменных. (1) f(x1, …, xn) - max (min) когда на эти переменные накладываются некоторые ограничения (2) j(x1, …, xn)

    =, =)bi, i=(i, m). (1)-целевая функция (2)-ограничение.

    Задачи подобного рода решаются с помощью экономико-мат методов в экономике.

    Если фции, входящие в (1) и (2) имеют лин характер, то применяются методы так называемого лин программирования. Если же хотя бы одна из ф-ций имеют не лин вид, то прим-ся

    методы не лин программ. Если решение требуется в целых числах, то прим-ся методы целочисленного программирования. ///

    2.Теорема о доп базисном решении в угловых точках.

    Если сис-ма векторов А1, …, Аn содержит m лин независимых векторов А1, …, Аm, то допустимое базисное решение X=(x1, …, xn, 0, …,0) явл угловой точкой многоугольника решений. И

    наоборот: в каждой угловой точке многоуг-ка решений соответ-ет допустимое базисное решение

    Точка нзв

    угловой, если она не явл внутр ни для какого отрезка целиком принадлежащего данному множ-ву.

    4.Решение задач ЛП геометрическим методом.

    Геметрич метод применяется лишь для задач с двумя переменными.

    (1) a

    2 >=(=0

    (3) F=c

    2 - max (min)

    Нерав-во (1) определяет некоторую полуплоскость с граничными прямыми

    (4) a

    2 =b

    i, i=1,m

    Чтобы определить полуплоскость соответ-ую (1) , сначала строят прямую (4). Затем, берется любая точка, не лежащая на указанной прямой и подставляется в исходное нерав-во (1).

    Если точке удовл-ет (1) то (1) определяет полуплоскость, содержащую эту точку. Если не удовлетворяет, то определяет полупл-ть не содержащую эту точку.

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

    решение так: Строят градиент ф-ции F. N=gradn(dF/dx1, dF/dx2)=(c1, c2). Этот вектор показывает направление возрастающей функции F, а обратное направление – убывание. Затем,

    строится линия уровня ф-ции F (прямая перпенд-ая градиенту). Передвигая линию уровня вдость градиента можно получить один из след случаев: единств реш, альтернативн, неогр,

    несовместности ограничений(нет реш)

    5.Симплексная таблица, нахождение нового базисного решения, признак оптимальности.

    Для решения задачи, не имеющей предпочтительный вид необходимо составить М-задачу и получить предпочтит вид. Таким образом, любую задачу ЛП можно представить в след виде:

    Выразим из (2) xi:

    Введем след обозначения:

    Подставим xi в(1) и, сгруппировав получится задача в след виде:

    Dj – оценки Сб

    Признак оптимальности доп базисного решения:

    Если для некот допустимого базисного решении оценки Dj (за исключением D0) ^30 (lb0), то такое базисное решение доставляет максимум(миним).

    Переход к новому базису:

    Рассмотрим задачу максимума. Если все D

    00. тогда вектор-столбец А

    0 нзв разрешающим, а переменная xj0 – перспективной. Можно увеличить значение ф-ции F засчет увеличения перм x

    0. При увеличении x

    0 необходимо учитывать неотриц-ть базисных переменных. Так как св прем = 0 и перспективные переменные неотрицательны, то x

    0 (i=1,m). Если a

    00, то при значительном увеличении x

    0 можем получить отрицат x

    i, что недопустимо. Пусть, первые к значений a

    00. Тогда будем увеличивать x

    0 до тех пор, пока x

    i=0, т.е b

    0 {x

    0= b

    i/ a

    0, a

    00. Выберем среди правых частей наим долю. Пусть она достигается в строке i0, тогда эта строка – разрешающая, а элемент a

    0 разреш-м элементом. Переведем базисную пременную xi0 в своб переем, а своб переем xj0 в базисную. Получаем новое допустимое базисное решение X1. Для этого выполняется

    D0-Dj0xi0=F(x0)-Dj0xi0=F(x0)

    3.Теорема о достижении экстремума значения целевой ф-ции в угловой точке.

    Если задача ЛП имеет решение, то целевая ф-ция достигает экстемального значения хотя бы в одной из угловых

    точек многоугольника решений; если же целевая ф-ция достигает оптимального значения более, чем в одной угловой точке, то она достигает того же самого значения в любой точке,

    являющейся их выпуклой лин комбинацией.

    6.Сходимость симплексного метода.

    Канонич задача ЛП нзв невырожденной, если все ее базисные решения невырождены, т.е ни одно из базисных переменных не имеет нулевого значения. Если среди базисных решений есть

    хотя бы одно вырожденное, то задача ЛП нзв вырожденной.

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

    итерациях связаны формулой D

    +1=D

    (1) b

    0=0, D

    0=0, a

    jo0. Если задача невырождена, то b

    00, D

    +1=D

    k, Т.е ф-ция F монотонно возрастает.

    Теорема: Если все допустимые базисные решения задачи ЛП невырождены, то симплексным методом за конечное число итераций будет найдено либо оптимальное решение, либо будет

    установлена неограниченность целевой ф-ции.

    7.Зацикливание, выход из цикла.

    Если задача ЛП вырождена, то b

    0=0 = D

    +1=D

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

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

    Т.о. получили зацикливание. Зацикливание можно избежать изменением правила выбора завершающего столбца и строки.

    К строке Qi симпл таблицы будем присваивать но...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены