Курс лекций по теме Управление в МИСО (1996) (1264200), страница 7
Текст из файла (страница 7)
Допустим, что отрицательная ij в строке есть. Тогда его столбец - разрешающий. Теперь в этом столбце выделяем все элементы, совпадающие по знаку со свободным членом. Разрешающим среди них будет тот, для которого отношение к нему свободного члена минимально. Выбор такой минимальности связан с некоторым градиентным стремлением к табличному.Страница 35Это не единственный путь выхода на границу ОДР.
Но по нему мы всегдавыйдем на границу. В нашем примере (-1/-1; -3/-0.5; 0/0) т.е. есть еще один путьвыхода на границу ОДР.Пример.св.членy1 = 1 − ( −x1 − 2x 2 + x 3 )y = −5 − ( −2x + x − x ) 2123y 3 = 2 − ( x1 + x 2 )y 4 = 1 − ( −x 2 + x 3 )y1x11-12y2-5-22Недопустимое решение:(1, -5, 2, 1, 0, 0, 0), т.к. в нем существует -5.Разрешающий столбец для x1.Разрешающая строка:-5/-2 = 2.52/1 = 2Разрешающий столбец:(3, -1, 4, 1, 0, 0, 0)3/1 = 2-1/-1 = 14 /0 =1/1 = 1y4В результате получаем таблицу:(2, 1, 2, 0, 0, 0, 0) - решение стало нетолько допустимым, но и опорным. Этоттабличный алгоритм нахождения опорного решения легко реализовать наЭВМ.y1x3x1y40-121100y1y2x1y41111122x3-214y3x2001-100100св.членy3x2x33-1411-210-131-11-101св.членy3x2y221203-2122-3121-101Отыскание оптимального решенияПосле отыскания опорного решения показатель принимает вид:I = c 0 − ( 1y 3 + 2 x 2 + 3 y 2 )Далее существуют 2 исхода:1.
Если все i < 0, то решение будет оптимальным (все y и x нужно брать =0).2. Если существует i > 0 (например 2), то для продолжения оптимизации нужно сделать замену x2, тогда появляется разрешающий столбец для x2 и по известному правилу отыскиваем разрешающую строку.Замечание.Если в строке для I есть положительный элемент, например а в столбцеx2, соответствующему ему, нет ни одного положительного элемента, то оптимальное решение не существует, т.к. I не ограничен снизу. Действительно, еслиСтраница 36все коэффициенты столбца x2 меньше 0, то при увеличении x2 (x2 перестает бытьсвободным), ни одна из базовых переменных не обнуляется и не может статьсвободной вместо x2.Таким образом, возвращаясь к формуле для непрерывное увеличение x2приводит к неограниченному уменьшению I.
Если в столбце для x2 существуетхотя бы один положительный элемент, то применяется табличный алгоритм.Решение транспортной задачи по критерию стоимостираспределительным методомСистема ограничений:nI = c i jx i j - критерий x = a i i = 1‚m j=1 i jm x = bj = 1‚n a i = b j - уравнение балансаijji=1Имеем n + m - 1 уравнений. Учитывая уравнение баланса: r = n + m - 1 число базовых переменных, то число свободных переменных: k = n m - r.Рассмотрим «метод северо-западного угла». Этим методом находитсяопорный «план», который затем улучшается до оптимального решения.cij - стоимость перевозки;a - ресурсы;b - заявки.И1И2Ранг r = m + n-1 = 9 - 1 = 8m n = 4 5 = 20k = m n - r = 12И3И4Число пустых клеток в таблицеk (свободных переменных), азаполненных r.П1П2П31085182736783087109754П46П5a9486530871266272020261258b18274212Способ дает следующий опорный план.
Он не оптимальный, т.к. при егосоставлении мы не учитываем стоимости cij. Улучшение опорного плана до оптимального имеет место, если производить циклические изменения в плане сотрицательной ценой цикла. Один из таких циклов обозначается стрелками. 18единиц дешевле перевозить не по схеме И1→П1, а И2→П1. Вместо И2→П3 дешевле И1→П3. Для источников ресурсов это взаимное перемещение.Выигрыш в стоимости: 18 (-4) + 18 (-3) = -126.
Опорный план не изменился (8 и 12), а показатель потерь уменьшился на 126 единиц. Если учесть всевозможные циклы, приводим опорный план к оптимальному.Литература: Лесдон «Большие системы» Москва, Мир 1972г.Страница 37Динамическое программирование в задачах распределенияресурсов (РР). Основное уравнение метода динамическогопрограммирования в дискретной форме.Как известно, дискретное программирование основано на принципе оптимальности, который формулируется следующим образом:если процесс управления может быть расчленен на последовательность шагов, то в соответствии с принципом оптимальности ищется управление, котороеобеспечивает оптимальное течение процесса относительно конца шага.Ii (S)- условный оптимальный выигрыш, полученный на всех шагах.S- начальное (к этому шагу) состояние.Ui (S)- условное оптимальное управление к этому шагу, которое вместе соптимальным управлением на всех последующих шагах обеспечивает максимумкритерия Ii.Требуется определить функции Ii (S) и Ui (S) для всех шагов.Рассмотрим i-ый шаг процесса управления, показатель эффективности наэтом шаге i(Ui , S).
Система к концу шага переходит в состояние S= i (S, Ui).Значение показателей эффективности для всех шагов, начиная с i-го имеет вид:I i ( S, U i ) = i ( U i , S ) + I i+1( S ) = i ( U i , S ) + I i+1( i ( S, U i ))В соответствии с принципом оптимальности необходимо оптимизировать:I i (S) = max[ i ( U i , S) + I i+1( i )] - уравнение Беллмана.UiДалее уравнение Беллмана применяется от конца к началу (1 стадия задачи).
Для m-го шага:I m (S) = max[ m ( U m , S)] → U m (S)UmНачальное состояние для m-го шага неизвестно, поэтому получаем неединственное, а несколько управлений (находим для всех возможных начальныхсостояний для m-го шага). Тоже самое повторяем для m-1 шага:I m −1(S) = max[ m −1( U m −1, S) + I m ( m −1(S, U m −1 ))] → U m −1(S) и т.д.Um −1Вторая стадия задачи (от начала к концу) - оптимизация заключается вполучении безусловного оптимального управления и в получении общего показателя эффективности (все Ii k известны уже в конце первой стадии).max I = I 0 ( S0 ) , при этом S0 - точно известно.UЕсли начальное положение точно не известно, то проводим оптимизациюпо S0.Безусловное оптимальное управление определяется по цепочке:S0 → U1 (S0 ) → ( U1 ,S0 ) → S1 → U2 (S1 ) → ( U2 ,S1 ) → S2 → S3 →Страница 38вторая стадияSnS0первая стадия01m-1mnИз сказанного следует алгоритм:I.заданно описание процесса.
Производим расчленение на этом этапе.II. задаем Si для n-го шага.III. задаем Si для n-1 шага.IV. записываем основное уравнение.V. находим In(S), Un(S), In-1(S), Un-1(S), . . . , I1(S), U1(S)VI. если S0 задано, то находим Iopt = I(S0)VII. далее по цепочке в прямом направлении.Решение задачи распределения ресурсов методом динамическогопрограммирования.Постановка задачи:Имеется начальное количество средств K0 , которые распределяются стечение m лет (налетов противника) между 2-мя потребителями, отраслями производства (секторами обороны I и II). Средства вложены в каждую отрасль иприносят определенный доход (эффективность поражения), зависящий от объема вложения. Если x средств вложено в отрасль I, то доход f(X).
При этом вложенные средства частично амортизируются (уничтожаются противником или непопадают в цель). К концу года (очередного налета) остается (X) < X, аналогично и для сектора обороны 2 (отрасли производства 2).( x) X - I отрасль X i , f ( x) ( y) Y - II отрасльYi , q ( y)По истечении года оставшиеся от K0 средства перераспределяются заново между I и II и полностью вкладываются в производство (в отражение налета).Требуется найти способ управления ресурсами, при котором суммарныйдоход за m лет наибольший.Величины x, y зависят от 2-х факторов:• перераспределение средств в начале каждого года между отраслями;• трата средств в течении года.Страница 39Ui - количество средств, вложенных в отрасль I-II на i-м шаге.1) Требуется выбрать U = (U1 ...
Um) при котором суммарный доход был бы максимален.2) Состояние S перед этим шагом характеризуется параметром K - количествосредств, которые не использованы на предыдущем шаге.Ui = (Xi, K–Xi)i = f (Xi) + q (K-Xi)3) Переходы от Si →Si+1 и Ki →Ki+1 и - функции трат.Ki+1 = (Xi) + (Ki – Xi)4) Основное уравнение имеет вид:I i ( Si ) = max [f ( X i ) + q ( K i − X i ) + I i+1( ( X i ) + ( K i − X i ))]0U i K i5) На последнем шагеI m ( Sm ) = max[f ( X m ) + q ( K m − X m )]Ui6) Получим условное оптимальное управление на всех шагах.
Т.к. ресурсы накаждом шаге неизвестны, то необходимо формировать сеть для несколькихвозможных состояний ресурсов.7) S0 = K0 Iopt = I (S0)8) Далее находим полное управление по цепочкеK0 → U1(K0) → K1 = (X0) + (X0 –Y1) → U2(K1) → K2 ...Таким образом получаемU(X1, X2, ... Xm,Y1, ...
, Yn)Обобщение задачи1. Распределение между n отраслями (секторами) тогда будет2. Распределение ресурсов на разных шагах по разному.Самостоятельно:1. Распределение ресурсов по порядковому номеру объекта.2. Распределение ресурсов с мультиплексными критериями.3. Венцель стр. 157-1594. Акоргл.7 стр.
212-235 Понятие о задачах управления запасами.Методы программирования в сетевых задачахвыбора маршрута.1. Определение сети. Виды сетевых задач. Выбор пути.Сеть - линейный граф, состоящий из множества узлов (вершин) и дуг (ребер). На каждой дуге задана ориентация (ориентированный граф).Страница 40• Непрерывная последовательность ребер, связывающих узел i с узлом j называется маршрутом.• Движение по ребрам может быть в одном или двух направлениях.• Сеть называется связанной, если найдется путь, связывающий любой i-й узелс любым j-м узлом.• Если существует ориентированный путь, начинающийся и заканчивающийсяв одном узле, то этот путь называется циклом.• Ациклические сети - сети без циклов.• Cij - характеристика сети (вес ребра).• Сеть может иметь матричную интерпретацию.К сетевым задачам можно отнести задачи выбора маршрута.Существуют 2 типичные схемы:1.
задача коммивояжера;2. задача выбора маршрута в незамкнутых цепях.Практическое применение задач:• транспортные задачи;• задачи оптимального обхода периферийных средств;• задачи дискретного линейного программирования и др.2. Задача коммивояжера и ее решение методом ветвей и границ.Коммивояжер должен побывать в ряде городов. Известно расстояние(время, стоимость) между городами и коммивояжер должен выбрать самыйкратчайший (быстрый, дешевый) замкнутый маршрут (ориентированный цикл).Этот цикл начинается в городе, где живет он сам, проходит один и только одинраз через каждый узел и заканчивается в исходном узле.n - число узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
