Признак оптимальности решения задачи ЛП, его обоснование и экономическая интерпретация
Содержание двух этапов симплекс-процесса и основные характеристик соответствующих процедур.
На предприятии производят два вида продукции - А и Б. Для выпуска единицы продукции А требуется 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-Cj≥0, В-1 заменяется на Е –един матрицу.
Первая итерация - определяется вектор А1 - кандидат на ввод в базис - имеющий максимальную по модулю отрицательную оценку (-М); кандидат на вывод из базиса - вектор W1 определился из минимума отношения компонент текущего решения к положительным элементам столбца А1 (направляющий элемент преобразования). Преобразования плана осуществляется по правилу "четырёхугольника".
Вторая итерация - определяется вектор А2 - кандидат на ввод в базис и вектор А3, удаляемый из базиса.
2 этап:
Третья итерация - определяется вектор А0 - кандидат на ввод в базис и вектор W2, удаляемый из базиса. Это уже идёт оптимизация допустимого решения - первый этап завершился на второй итерации.
На четвёртой итерации выясняется, что полученное решение оптимально - все оценки столбцов матрицы условий неотрицательны.
Признак оптимальности решения задачи ЛП, его обоснование и экономическая интерпретация.
Эффективной признается такая технология для которой выполняется строгое равенство, когда значимость равна цене.
Теорема: Условие оптимальности решения: ∆j =∑yiaij-Ci≥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-Cj≥0, СбазВ-1=Y, Сбаз=1, m – рыночные цены в базисной матрице, Aj – столбец если левая граница, то правая <0, если не на границе, то 0,если правая граница то >0.
Реш-е оптимально, если лучшего при заданных условиях не существует. Х* - оптимальное. 