Методы решения многокритер-х задач

Парето -Пусть в составе множ-ва возможных решений есть два решения х1и х2 такие, что все критерии W1, W2,…, Wк для первого реш-я больше или равны соответствующим критериям для второго реш-я, причем хотя бы один из них действит-но больше. Очевидно что в составе множества Х нет смысла сохранять решение х2, оно вытесняется решением х1. Выбросим решение х2, как не конкурентно спос-е и перейдем к сравнению других по всем критериям. В результате отбрасыв-ся не выгодные решения, множество Х сильно уменьшается. В нем сохраняются только эффективные(паретовские) реш-я. Линейная свертка – здесь участвуют человек и ПК. Указывается вес события:а1,а2,…,а3.Машина производит расчеты и выдает показатели эффективности(как бы в ряд): W1, W2… Wn, а человек может критически оценить ситуацию и внести измен-я в весовые коэфф-ты(или иные параметры управляющего алгоритма). В конечном итоге решение все равно принимает человек. наложение ограничений на показ-ли эффективности – надо выделить один(главный) показатель W1 и стремиться его обратить в максимум, а на все остальные W2, W3,....(# чтобы прибыль была максим-я, план по ассортименту выполнен, а себестоимость прод-и не выше заданной). При таком подходе все показ-ли, кроме одного – главного перев-ся в разряд заданных условий а(альфа). метод последовательных уступок – Предположим что показатели W1, W2… Wn, расположены в порядке убывающей важности. Сначала ищется решение, обращающее в максимум первый(важнейший) показатель W1= W1*. Затем назначается, исходя из практических соображений, с учетом малой точности, с которой нам известны входные данные, некоторая уступка и ΔW1, которую мы согласны сделать для того чтобы максим-вать второй показатель W2. Наложим на показатель W1 ограничение: чтобы он был меньше, чем W1*- ΔW1, и при этом ограничении ищем решение, обращающее в максимум W2. Далее снова назначаем уступку в W2, ценой которой можно максимизировать W3, и т.д. Такой способ построения компромиссного хорош тем, что здесь сразу видно, ценой какой уступки, в одном показателе приобретается выигрыш в другом и какова величина этого выигрыша.

Осн-я задача лин-го программир-я (ОЗЛП) и сведение произв-й задачи лин-го программир-я к осн-й задаче лин-го прогр-я.

Любую задачу ЛП можно свести к стандарт.форме (ОЗЛП), ктр формулир-ся так: найти неотриц.знач-я переменных х₁, х₂, …, х_n, ктр удовлетворяли бы условиям-рав-вам

и обращали бы в мах лин.f-ю этих переменных: .

Назовем допустимым решением ОЗЛП всякую совок-ть неотриц.знач-й х₁, х₂, …, х_n, удовлетворяющую условиям системы. Оптимальным назовем то из допустимых решений, ктр обращает в мах f-ю L. Требуется найти оптим.решение. Задачи ЛП сводятся к ОЗЛП, где необх-мо найти неотриц.знач-я пер-ных х1, х2, …, х_n, удовлетворяющие сис-ме m-лин.нерав-в и ур-й, и обращающие в max (min) лин.f-ю этих пер-ных. F=c1x1+c2x2+…+c_nx_n→max (min). Назовем допустимым решением ОЗЛП всякую совок-ть неотриц.знач-й х1, х2, …, х_n, удовлетвор.сис-ме огранич-й. Оптимальным назовем то из допустим.реш-й, ктр обращает в max(min) цел.f-ю. Рассмотрим задачу ЛП с 2мя пер-ными (n=2). Пусть геом.изображ-ем сис-мы огранич-й явл-ся многоуг-к. Необх-мо среди точек этого мног-ка найти такую точку (вершину), в ктр лин.f-я принимает max (min) знач-е. Рассмотрим так наз-мую линию уровня лин.f-и F, т.е. линию, вдоль ктр эта f-я принимает одно и тоже фиксирован.знач-е а, т.е. с1х1+с2х2=а. На мног-ке реш-й следует найти точку, через ктр проходит линия уровня f-и F с наибольшим (если f-я max-ется) или наим.(если f-я min-ется) уровнем. Ур-е линии уровня f-и есть ур-е прямой линии. При различ.уровнях а линии уровня //, т.к. их угловые коэф-ты опр-ся только соотнош-ем между коэф-тами с1 и с2, и след-но, =. Т.о., линии уровня f-и F – это своеобразные параллели, расположенные обычно под углом к осям корд-т. Важн.св-во линии уровня лин.f-и состоит в том, что при // смещении линии в одну сторону уровень только возрастает, а при смещ-и в др.сторону – только убывает.

9. Симплекс–метод при решении ОЗЛП.

Симплекс-метод явл-ся одним из способов решения ЗЛП. Идея последоват.улучшения решения легла в основу универсал.метода решения ЗЛП – с-м. Геометрич.смысл с-м состоит в последоват.переходе от одной вершины (первоначальной) многогранника огранич-й к соседней, в ктр лин.f-я принимает лучшее (не худшее) знач-е (по отношению к цели задачи) до тех пор, пока не будет найдено оптим.реш-е – вершина, где достиг-ся оптим.знач-е f-и цели (если задача имеет конечный оптимум). С-м – это вычислит.процедура, основанная на принципе последоват.улучшения решений при переходе от одной базисной точки (базисного решения) к др. При этом знач-е цел.f-и улучшается. Базисным реш-ем явл-ся одно из допустимых реш-й, нах-щихся в вершинах области допустимых знач-й. Проверяя на оптим-ть вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан с-м. С-м может быть найден на мах и min. 1.MAX. (Задача об использ-и ресурсов): имеются 2вида продукции P1 и P2, использ-ся 4вида ресурсов S1, S2, S3, S4. Необх-мо составить такой план произв-ва продукции, при ктр прибыль от ее реализации будет мах. 1) Необх-мо из сис-мы огранич-й, ктр выглядит в виде сис-мы нерав-в, сделать сис-му ур-ий (если «£», то осн.пер-ные со знаком +, если «³», то -). Д/этого придется ввести дополнит.неотриц.переменные. Опр-м, какие из переменных явл-ся осн., а какие – неосн. Пр-ло: в кач-ве осн.пер-ных на I шаге следует выбрать (если возможно) такие m-пер-ных, каждая из ктр входит только в 1 из m-ур-ий сис-мы огранич-й, при этом нет таких ур-ий сис-мы, в ктр не входит ни одна из этих пер-ных. Далее выражаем осн.пер-ные через неосн. Положив, неосн.пер-ные = 0, получим I базисное реш-е. 2) Составим сим.таблицу: а) исх.расширен.сис-му (в ктр выражали осн.пер-ные через неосн.) заносим в I сим.таблицу. Послед.строка таблицы, в ктр приведено ур-ие д/лин.f-и цели, наз-ся оценочной. В ней указыв-ся коэф-ты цел.f-и с противополож.знаком. В лев.столбце таблицы записываем осн.пер-ные (базис), в I строке таблицы – все пер-ные (отмечая при этом осн.), во II столбце – свобод.члены расширен.сис-мы

.

Последний столбец – д/оц.отнош-й, необх-мых при расчете наибольшего знач-я пер-ной. В рабоч.часть таблицы занесены коэф-ты

при пер-ных из расширен.сис-мы. Далее

таблица преобраз-ся по опр.правилам. б) Проверяем выполн-е критерия оптим-ти. При реш-и задачи на мах – наличие в послед.строке отриц.коэф-тов. Если таких коэф-тов нет, то реш-е оптимально, т.е. достигнут мах. При этом

, осн.пер-ные принимают значение (II

столбец). Осн.пер-ные = 0, т.е. получено оптим.реш-е. Иначе, переходим к след.шагу. в) Если критерий оптим-ти не выполнен, то наибольший по модулю отриц.коэф-т в послед.строке таблицы опр-ет разрешающий столбец S. Составляем оц.отнош-я

кажд.строки по след.правилам: а) если и имеют разные знаки; б) и ; в) ; г)0, если и ; д) , если и имеют одинак.знаки. Опр-ем min . Если конечного min нет, то задача не имеет конечного оптимума, т.е. . Если min конечен, то выбираем строку q, на ктр он достиг-ся (если их неск-ко, то выбираем любую) и назовем ее разрешающей строкой. На пересечении разреш.столбца и разреш.строки нах-ся разрешающий элемент . г) Переходим к

след.таблице по след.правилам: а)в лев.столбце записываем новый базис: вместо осн.пер-ных х_q записываем х_s; б)в столбцах, соотв-щих осн.пер-ным, проставляем: 1 – против «своей» осн.пер-ной, 0 – против «чужой» осн.пер-ной, 0 – в послед.строке д/всех осн.пер-ных; в)нов.строку с № q получаем из старой строки делением на разреш.столбец

;

г)все остальные пер-ные пересчитываем по правилу прямоугольника. Далее переходим к пункту 2.

2.MIN. Сначала также преобраз-ся сис-ма нерав-в в сис-му ур-ий, выражаем осн.пер-ные через неосн. Критерий оптим-ти при отыскании min лин.f-и: если в выраж-и лин.f-и через неосн.пер-ные отсутствуют отриц.коэф-ты при неосн.пер-ных, то реш-е оптимально. Смотрим, есть ли в итог.столбце (свобод.членов) отриц.знаки. Если да, то это явл-ся свидетельством того, что дан.план нельзя считать допустимым. Ликвидация отриц.чисел в итог.столбце начин-ся с наибольшего по абсолют.величине (это будет ключевая строка). Найдем ключ.столбец. Д/этого нужно эл-ты цел.строки разделить на эл-ты ключ.строки (оц.отнош-я) д/столбцов. Из получен.отнош-й выбираем наименьшее. На пересеч-и ключ.строки и столбца нах-ся ключ.эл-т. Далее все происходит также.

Транспортная задача.

# Имеется m пунктов отправления (пунктов произв-ва) А_i …, А_m, в ктр сосредоточены запасы однород.продуктов в кол-ве a₁,..., а_m ед-ц. Имеется n пунктов назнач-я (пунктов потребления) В₁,..., В_n, потреб-ть ктр в указанных продуктах составляет b₁,..., b_n ед-ц. Известны также транспорт.расходы С_ij, связанные с перевозкой ед-цы продукта из пункта A_i в пункт В_j, (i 1, …, m; j 1,..., n). Постановка задачи: Найти V перевозок д/кажд.пары «поставщ.-потреб.» так, чтобы: 1)мощ-ти всех пост-ков были реализованы; 2)спросы всех потреб-лей были удовлетворены; 3)затраты на перевозку были min. Особен-ти эк.-мат.модели ТЗ: 1)сис-мы огранич-й – есть сис-мы ур-ий; 2)коэф-ты при неизвестных в сис-мах огранич-й = 1 или 0; 3)кажд.переменная входит в сис-му огранич-й 2раза – 1раз в I сис-му и 1раз во II. Всякое неотриц.реш-е сис-мы лин.ур-й, опр-мое матрицей X=(x_ij) (i=1, …, m; j=1,..., n), наз-ся планом ТЗ. План X=(x_ij)(i=1, …, m; j=1,..., n), при ктр f-я принимает свое min значение, наз-ся оптимал.планом ТЗ. Если мощ-ть всех пост-ков=сум.мощ-ти потреб-лей, то такие задачи наз-ся закрытыми, в против.случае – открытого типа. Т: число r осн.(базисных) переменных закрытой ТЗ = m+n-1 (m-число пост-ков, n-потреб-лей). Кажд.разбиению переменных x_ij задачи на осн.(базисные) и неосн.(свобод.) соотв-ет базис.реш-е и, как следствие, заполнение таблицы поставок, ктр также наз-ся базисным. Др.словами, распред-е поставок наз-ся базисным, если переменные, соотв-щие заполненным клеткам, можно принять за осн.переменные. Клетки, отвечающие базис.переменным, наз-ся базисными, а клетки, соотв-щие свобод.перемен., свободными или пустыми.