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

Содержание двух этапов симплекс-процесса и основные характеристик соответствующих процедур.

На предприятии производят два вида продукции - А и Б. Для выпуска единицы продукции А требуется 0.2 ед. труда; Б - 0.4 ед. труда и 0.1 ед. продукции а.

Формализация задачи в виде модели ЛП:

Найти максимум Х0 при условиях

X1 - 0.1X2 = 0.75X0

X2 = 0.25X0

0.2X1 + 0.4X2 + X3 = 100

X=(X1,X2,X3)>=0

Здесь Х0 - валовый выпуск продукции в стоимостном выражении; Х1 и Х2 выпуск продукции А и Б соответственно; Х3 - дополнительная переменна имеющая смысл неизрасходованного труда (резерв рабочего времени). Расширенная задача с включением искусственных переменных для создания единич исходного базиса:

Найти максимум Х0-МW1-MW2 при условиях

X1 - 0.1X2 - 0.75X0 + W1 = 0

X2 - 0.25X0 + W2 = 0

0.2X1 + 0.4X2 + X3 = 100

X = (X1,X2,X3) >= 0

Смысл условий: первое условие есть баланс выпуска и расхода продукции А; второе условие учитывает при выпуске продукции Б расход промежуточного продукта А; третье условие есть баланс рабочего времени (труда). Коэффициенты разложения по базису W1, W2, X3 векторов-столбцов матрицы услов совпадают с самой матрицей, ибо базис - единичная матрица.

1 этап: в соответствии с алгоритмом осущ-ся исключение искусств переменных W1 и W2 из базиса, заменив их на настоящие. При успешном вып-нии получаем 1е допустимое решение, если нет - о ни одного доп реш нет.

Сбаз А1

W1 | –М | –М

W2 | - М | 0

х3 | 0 |

Проверяется признак оптим, т.е считается оценки столбцов ∆1, ∆2,.. ∆4≥0

∆1= -М*1 + (-М)*0 +0*0,2 –С1=0-М,

∆j=С_базВ^-1А_j-C_j≥0, В^-1 заменяется на Е –един матрицу.

Первая итерация - определяется вектор А1 - кандидат на ввод в базис - имеющий максимальную по модулю отрицательную оценку (-М); кандидат на вывод из базиса - вектор W1 определился из минимума отношения компонент текущего решения к положительным элементам столбца А1 (направляющий элемент преобразования). Преобразования плана осуществляется по правилу "четырёхугольника".

Вторая итерация - определяется вектор А2 - кандидат на ввод в базис и вектор А3, удаляемый из базиса.

2 этап:

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

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

 

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

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

Теорема: Условие оптимальности решения: ∆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.

Реш-е оптимально, если лучшего при заданных условиях не существует. Х* - оптимальное.