Шпаргалка по математическим методам в экономике — страница 2

  • Просмотров 2188
  • Скачиваний 268
  • Размер файла 31
    Кб

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

задач с двумя переменными. (1) ai1x1+ai2x2 ≥(≤)bi, i=1,m (2) x1, x2≥0 (3) F=c1x1+c2x2 -> max (min) Нерав-во (1) определяет некоторую полуплоскость с граничными прямыми (4) ai1x1+ai2x2 =bi, i=1,m Чтобы определить полуплоскость соответ-ую (1) , сначала строят прямую (4). Затем, берется любая точка, не лежащая на указанной прямой и подставляется в исходное нерав-во (1). Если точке удовл-ет (1) то (1) определяет полуплоскость, содержащую эту точку. Если не удовлетворяет, то

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

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

Введем след обозначения: Подставим xi в(1) и, сгруппировав получится задача в след виде: <симплекс таблица> Dj – оценки Сб Признак оптимальности доп базисного решения: Если для некот допустимого базисного решении оценки Dj (за исключением D0) ³0 (£0), то такое базисное решение доставляет максимум(миним). Переход к новому базису: Рассмотрим задачу максимума. Если все Dj0>=0, то достигли цели. Пусть сущ-ет x0: сущ номер j0: Dj0<0. тогда

вектор-столбец Аj0 нзв разрешающим, а переменная xj0 – перспективной. Можно увеличить значение ф-ции F засчет увеличения перм xj0. При увеличении xj0 необходимо учитывать неотриц-ть базисных переменных. Так как св прем = 0 и перспективные переменные неотрицательны, то xi=bi-aij0xj0 (i=1,m). Если aij0>0, то при значительном увеличении xj0 можем получить отрицат xi, что недопустимо. Пусть, первые к значений aij0>0. Тогда будем увеличивать xj0 до тех пор,