2 Этап:

Третья итерация - определяется вектор А0 - кандидат на ввод в базис и вектор W2, удаляемый из базиса. Это уже идёт оптимизация допустимого решения - первый этап завершился на второй итерации.

На четвёртой итерации выясняется, что полученное решение оптимально - все оценки столбцов матрицы условий неотрицательны.

Билет 12

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

(C,X) – max (1), Ax≤b (2), x≥0 (3); C1X1→(C’1+tC1’’)X1, C2X3→(C’2+tC2’’)X2, C’1 – исходная цена, t – время, C1’’-новая цена. ∑(C’j+C’’jt)Xj→max, t-параметр. (1). Это параметрическая задача 1. Св-ва модели: F*(X,t)= ∑(C’j+C’’jt)Xj*-решающая функция. Теорема 1: Область разрешимости разбивается на конечное число интервалов и лучей; на каждом из них решающая ф-ция линейна относительно параметра t, угловые коэффициенты монотонно возрастают при переходе через границы, тюею не имеют выколотых точек. Примечание: Лучей может и не быть. Теорема 2. Каждой области устойчивости соответствует некоторое решение, оптимальное внутри этой области, включая ее граничные точки. Область неразрешимости если она есть всегда представляет левуй луч(-∞; о). Теорема 3. Задача 1 может быть исследована за конечное число шагов с помощью специальных процедур симплексного типа, однако вероятность образования циклов существенно выше чем в обычных задачах. Приближенные методы исследования этой задачи: 0≤t≤е”Сначала решим когда t=0, потом t1 и т.д. Такой метод называют методом последовательной оптимизации. Решения внутри областей устойчивости от параметра t не зависят, а вот оценки в области устойчивости зависят от параметра t линейно. y¹+y₀²+ty¹_B. Прим: угловой коэффициент не обязательно изменяется строго монотонно. Задача 2: (C,X) – max, Ax≤b, x≥0, a11x1+a_1nx_n≤b1+tb1; для этой задачи решающая функция будет t. F(x,A,b(t)), F(X,t), 0≤t≤t” . Теорема 2 сохраняется, но ф-ция будет выпукла вверх. Это значит что угловые коэффициенты убывают, хотя и не строго монотонно. Оценки ресурсов не зависят от параметра t. Это полунепрерывная сверху функция. Компоненты решений зависят линейно.x¹=(x¹₁,x¹₂,x¹_n), x¹=(x¹_1б+tx¹_1∆) Задача 3. Общий случай. F(C(t), b(t),X) имеет место теорема 1, но решающая функция не является линейной, внутри каждой области устойчивости это функция второго порядка F(t)=Fл+tF¹+t²F” Оценки все будут линейными фун-иями от параметра t.

Билет 13

Признак оптимальности решения задачи ЛП, его обоснование и экономическая интерпретация.

Эффективной признается такая технология для которой выполняется строгое равенство, когда значимость равна цене.

Теорема: Условие оптимальности решения: ∆j =∑y_ia_ij-C_i≥0, j=1,n т

Теорема 3. Если задача ЛП разрешима, т.е. м найти max или min, то оптим множ-во содержит хотя одну вершину. (Оптим реш Х* =(х*1, …х*n), F(x*) ≥F(x), x принадл D, F – функция целей. Если реш оптим, то улучшить его при заданном условии и по задан критериям невозможно. Сов-ть оптим реш – оптим множ-во).Если решение оптимально, то условие выполняется для всех столбцов:

Признак оптимальности:

Ax=B, x≥0 м записать Вх=b, х=В^-1 b – текущее решение.

С баз = (с1, с2…с m).

(5) ∆j =Сбаз В^-1 Аj - Сj≥0 – требования оптим.

Эконом смысл: Сбаз В^-1 Аj – значимость используемых рес-сов на ед объема прод-ции; Сj –эффект от ед объема..

Суммарная значимость испол рес-сов не м б ниже эффекта, полученного от их использования.

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

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

Если условие (5) не выполняется, то решение не оптимально.

∆j=С_базВ^-1А_j-C_j≥0, С_базВ^-1=Y, С_баз=1, m – рыночные цены в базисной матрице, A_j – столбец если левая граница, то правая <0, если не на границе, то 0,если правая граница то >0. Реш-е оптимально, если лучшего при заданных условиях не существует. Х* - оптимальное.

Билет 14

Схема преобразования стохастической задачи МП к эквивалентному детерминированному виду. Содержательное истолкование детерминированной задачи.

Рассматривается задача ЛП, в которой требуется найти максимум линейной формы L=(C,X)MAX при условиях AX≤B и X≥0, причем элементы вектора ограничений, элементы матрицы условий и коэффициенты функции цели могут быть случайными числами как с известными характеристиками (случай риска), так и неизвестными (случай неопред-ности).

Если задача полностью стохастическая, то необходимо уточнить исходную постановку задачи: определить, что понимается под допустимым решением (планом), а также смысловое содержание показателя качества решений. Исходной задаче может соответствовать различные определения (модели) стохастической задачи: 

Если случайны не только вектор С, но и другая информация: вектор В и матрица условий А, то необходимо уточнить исходную постановку задачи: определить, что понимается под допустимым решением (планом), а также смысловое содержание показателя качества решений.

Решение задачи Х рассматривается как детерминированный (фиксированный) вектор; допустимым решением (планом) считается такой вектор Х, который удовлетворяет ограничениям задачи при всех возможных сочетаниях значений А и В, имеющих положительную вероятность; это жесткая постановка задачи, не использующая дополнительных сведений относительно статистических характеристик условий в модели.

A(q)*X<=B(q) для всех q@Q,X>=0 Здесь q‑случайные параметры, от которых зависят значения А и В (состояния природы), их набор обычно считается конечным;

Р(SUM Aij*Xj <= Bi) >= Pi; i=1,...,m; 0 =< Pi <= 1 при этом часто матрица А предполагается фиксированной и случаен только вектор ограничений В; если множество возможных состояний природы конечно и известны характеристики (оценки значений и их вероятностей) для каждого элемента Вi (т.е. Bki и Hki для k=1,...,s), то можно определить значения ~Bi, которые удовлетворяют условию P(Bi(q)>=~Bi)>=Pi; действительно, для этого необходимо упорядочить значения Bki в порядке убывания и выбрать наименьшую группу, удовлетворяющую условию: вероятность попадания значения Bi в данную группу больше или равна Pi (для этого суммарная вероятность группы должна быть больше или равна Pi). Тогда задача будет сведена к детерминированной: (^C,X)MAX AX<=~B, где ~B=(~B1,~B2,...,~Bm) при условии жесткой постановки (одноэтапной);

Нахождение решения стохастической задачи в жесткой постановке может быть организовано следующим образом:

- если X - допустимый план (перманентное решение) задачи, то он удовлетворяет соотношению A^X<=B^ для любой допустимой (возможной) пары [A^,B^].

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

Билет 15