Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




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

На предприятии производят два вида продукции - А и Б. Для выпуска единицы продукции А требуется 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.

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

 





Поделиться с друзьями:


Дата добавления: 2015-09-20; Мы поможем в написании ваших работ!; просмотров: 537 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Лучшая месть – огромный успех. © Фрэнк Синатра
==> читать все изречения...

2293 - | 2174 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.013 с.