Студопедия Главная Случайная страница Обратная связь

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

Опр-е нач. базисного решения в симплекс-методе. Признак опт-ти




Имея текущее базисное решение, необходимо выяснить, является ли оно оптимальным. Признак оптимальности позволяет установить статус решения и определить последующие действия. Пусть на k-й итерации получили базисное решение x(k) с критерием L(k). При смещении из этой вершины на: xk+1i=Xki-qair, i=1, 2,…,m. xk+1r=q. Критерий:

или, введя обозначения получаем

Параметр Δr - относительная оценка переменной; показывает, как изменится значение критерия при введении единицы новой переменной (q=1). Поэтому, если есть отрицательные оценки, текущее решение может быть улучшено при введении в число базисных соответствующей переменной. Если все оценки будут >= нулю, ни одна переменная не может улучшить тек. решение, условие "Δj³0 - признак оптимальности. Для базисных переменных относительные оценки равны нулю: Так как базисный вектор не выражается через другие, то только один коэффициент arr=1, остальные =0. zr=Cr-> Δr=0. Достаточно проверять знаки оценок только небазисных переменных.

Интерпретация: задача планирования, в которой Хj – количество продукции j-го вида, Cj – стоимость единицы произведенной продукции. Тогда X(0) – план производства, включающий первые m видов продукции.Включим в него еще один вид продукции r. Так как ресурсы не меняются, это возможно только при одновременном уменьшении продукции, входящей в план X(0). Величина этого изменения определяется коэффициентами air. air показывает, насколько должно измениться производство продукции i-го вида при введении в план единицы продукции r; в экономической литературе - маргинальная норма замещения. Значит, объем выпуска каждого вида продукции сокращается на air , а суммарная стоимость на величину Поэтому Zr - маргинальная цена (снижение стоимости произведенной продукции на каждую единицу продукции r). В то же время, единица продукции r дает прирост стоимости Сr - маргинальный доход. Если Cr>Zr, то есть Δr<0, то это выгодно.

Если несколько переменных имеют отрицательные оценки, то выбирают переменную с наименьшей оценкой. Этапы симплекс-метода:

1. Построение начального неотрицательного базисного решения.

2. Анализ оценок. При этом возможны три ситуации:

а) все оценки неотрицательны, следовательно, вычисления прекращаются, так как выполнился признак оптимальности.

б) имеются отрицательные оценки, но, по крайней мере, одной их них (например, Δj) соответствует вектор, для которого все коэффициенты разложения неположительны ("aij£0). В этом случае q не ограничено сверху икритерий неограниченно возрастает. Решение прекращается.

в) для каждой отрицательной оценки есть aij>0. Решение может быть улучшено выполнением 3 этапа.

3. Переход к новому базисному решению путем введения переменной с минимальной оценкой и выводом переменной.

Этапы 2 и 3 повторяются до выполнения одного из условий останова.







Дата добавления: 2015-04-19; просмотров: 198. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.002 сек.) русская версия | украинская версия