48А Правила пересчёта с-т
1) Поиск возможных переходов. Рассмотрим посл. строку табл:
а) В строке нет отрицат. чисел, кроме f0. Задача решена, значения оптим. плана содержатся в столбце «Р0». Оптим.знач.целевой ф-и= f0.
б) Среди всех Δj в последн.строке есть отриц. Выбираем любое из них Δk<0. Соотв. столбец Рk объявляется разрешающим столбцом.
2) Определение путей перехода. Рассм. эл-ты разрешающего столбца:
а) Все эл-ты столбца «Pk» не положительны. Решения нет. Целев. ф-ция неограниченна сверху.
б) Среди эл-тов столбца «Pk» есть положительные αik>0. Для каждого находим значение γi = bi/aik , как отношение соотв. компонент столбцов Р0 и Рк. Среди всех γi выбираем миним. Пусть минимум достигается при i = r, тогда соотв. эл-т разрешающего столбца ark объявляется разрешающим, а строка, его содержащая - разрешающей. если минимум достигается сразу для неск. эл-тов, то разрешающим выбирается любой.
3) Переход к новой вершине. Заполняется новая таблица. На месте эл-тов разрешающей строки в новой табл. записываются эл-ты старой, поделённые на разрешающий эл-т. На месте разреш. столбца в новой табл. записывается единичный вектор, с единицей на месте разрешающего эл та. Остальные эл-ты табл. включая послед. строку пересчитываются также, как при реализации метода исключения Гаусса.
49 Метод искусственного базиса (м-метод). Назначение м-метода
Реализация процедуры перехода от в-ны к в-не, описанная в алгебре С-метода, требует сущ-ния опорного плана. В том сл-е, когда исходная сис-ма Ур-ний - огр-ний канон-ой формы исходной з-чи требует обяз-ного предварительного р-ия методом Гаусса для достижения опорного плана, поскольку в расш-ной м-це данной сис-мы нет достаточного кол-ва ед-ных векторов, образующих базис, искомый опрный план можно получить путем введения доп-ных искусственных пер-ных и р-ие з-чи обеспечит движение к опт-ному плану, начиная с искусственного опрного плана.
Метод предназначен для реш0ия ЗЛП в кан-ой форме:
f(x)→max
Σj=1n xjРj=P0
x>=0
(выражение Σ xjРj=P0 представляет собой векторную форму записи СЛУ Ур-ний - огр-ний Ах=b, в кот-ой Рj есть j-тый столбец м-цы А)
50 Схема реализации м-метода
1) В рассмотрение вводится m «искусственных» переем. xn+1, …, xn+m и формулируется расширенная ЗЛП:
F = Σi=1n ci xi – M Σj=n+1n+mхj → max (1)
Σi=1n xi Pi + Σj=n+1n+m xiPi = P0 xk ≥ 0, k = 1, n+m (2)
Здесь М – очень
большое положит. число. М>>0 – штрафной
множитель. Pj,
j
= n+1,
n+m
– единичный вектора, составляющие ИБ
в
и
определяющие опорный план:
хт (1) = (0, …, 0, b1, …, bm), в кот. все истинные перем. равны 0 являются точкой опорного плана расширенной задачи.
Шаг 2: сформированная задача (3)-(4) решается обычным СМ и оптим. план исходной задачи, если он существ., присутствует как составная часть в оптим. плане расширенной задачи.
51.Сим.-т для реализации метода искусств.Базиса.
Для решения расширенной ЗЛП применяются таблицы, имеющие на 1 строку больше, чем обычные. Послед. строка обычной табл. как бы разбивается на 2. В предпослед. строку записывают составляющие f0 и Δj, не зависящие от штрафа М, а в последнюю строку –составляющие этих величин, зависящие от М или просто коэф-ты при М. Пересчёт эл-тов ведут сначала по последней строке. Выбираем в качестве разрешающих столбцы, соотв. наименьшему из чисел этой строки, до тех пор, пока: либо все искусств. перем. не будут исключены из базиса, либо последняя строка не будет содержать отрицат. эл-тов, кроме Р0. Далее пересчёт ведут по предпослед. строке, убрав из рассмотрения все эл-ты табл., соотв. искусственным перем., покинувшим базис.
Замечание: Если исход. задача содержит несколько векторов Pj, то их следует включить в ИБ,снизив тем самым число искусств.перем.