close

Вход

Забыли?

вход по аккаунту

?

билет№7

код для вставкиСкачать
 Билет №7
1. Идея симплекс-метода решения задачи ЛП. Блок-схема процесса.
Основной метод предложен Данцевым это симплекс метод. Его идея - движение в направлении наискорейшего возрастания функции цели по вершинам, направленный перебор вершин в сторону наискорейшего возрастания функции. Теорема 5: - оптимальное реш-е, если оно сущ-ет, б найдено с пом СМ за конечное число шагов fn, в противном случае б обнаружена неразрешимость задачи.(если задача не вырожденная или предприн меры против зацикливания в общем случае).
Возможные исходы при решении задач ЛП 1. нет ни одного решения (это значит что условие 2 и 3 противоречивы). Оказалось что направленный перебор вершин эффективен (по градиенту). Этот метод назван симплекс методом. Оптимальным называется решение лучше которого при заданных условиях не существует. Это решение обознач Х*. F*=F(C,X*)≥F(C,X). 2. Если доп мн-во огранич (замкнуто) реш задачи сущ-ет и на min и на max, т.е сущ-ет оптим реш.
3. Задача на max разрешима, а на min функция целей неограниченна.
4. Реш на min сущ-ет, а на maxФЦ неоганиченна.
Блок схема симплекс метода: 1.Поиск первой доп вершины → если да → 2.хар-ка текущ реш → 3.проверка оптимальности →если да→ то 4.анализ рез-тов, →если нет →то 5. поиск ближайшей лучшей вершины →если нет, →то 6. критерий не огранич, →если да →то 2.хар-ка текущего решения. Один такой шаг называется итерацией. Теорема . Метод является конечным если не возникает зацикливаний из-за потери точности счета. Существуют специальные в т.ч. автоматизированные условия выхода из цикла.
Кол-во столбцов n не влияет не на число шагов, а на трудоемкость каждого отдельного шага. Опр: Решения, соответствующие вершинам называют опорными (базисными). Для оптимального решения так же как для базисного. B(MxM) Матрица В называется базисной. Для каждой вершины она своя. Эта матрица не вырождена, для нее всегда существует обратная, значит ее определитель отличен от нуля, вместо А можем подставить ВХ=b. BX=b|B-1 ;X=B-1*BX =b-1b ;EX=B-1b; X=B-1b Предполагалось что ранг матрицы А равен m. Это значит что все столбцы линейно независимы. Все столбцы не входящие в базисную матрицу могут быть представлены как неотрицательные комбинации столбцов Ak=α1А1+ α2A2+...
Св-ва СМ:
1. конечное число шагов
2. если менять местами столбцы или строки, то реш не изменится.
3. Если к условиям модели добавить одну или несколько строк, являющихся комбинациями уже существующих, то реш задачи не изменится. Доп условия б избыточны.
∆ - оценки рентаб-ти произв-х способов = оценки столбцов.
Предполагаем, что задача приведена в каконическом виде.
∑cjxj→max (j=1,n), Ax=B, x≥0.
2. Общая формулировка стоха-кой модели МП в виде задачи с вероятностными условиями.
Рассматривается задача ЛП, в которой требуется найти максимум линейной формы(искомый вектор)
Входная информация (детерминированная - однозначно задана) не точная, приближенная, характеризуется неопределенностью Экспертная оценка все-равно используется: 1) средне наибольшая вероятность - оценка математического ожидания (все случайные величины - ξ); 2) коэффициент вариации Кв (NPV)
В стохастической модели необходимо оценивать попадание случайной величины в определенный диапазон, чтобы знать значение цели. Для этого используют график кумулятивы:
1
искомое решение
-3ξ ξ ξ1 ξ2 +3ξ
График показывает поведение функции цели как случайной величины не зависимо от количества ресурсов. Вероятностный характер имеет и функция цели (цены) и коэффициенты расхода ресурса (их возможного недостатка). Используется норм. распределение: НОРМРАСПР (заданная точка; ξ; σ; [0,1])
Р - надежность рез-та (попадание ф-ии цели в правый хвост от задан. гр-цы.
Решение: 1) все значения заменяются на мат. ожидание (среднее значение) - максимизация результата при заданной надежности P ≥ Р при F--> max; 2) максимизация надежности при заданном уровне эффекта F ≥ F при maxP(F)
Недостаток - не можем сказать, с какой вер-тью получилась функция цели.
В постановках стох. задач рассматривают:
- математическое ожидание линейной формы (функции цели);
- дисперсия функции цели;
- лин. комбинация (компромисс) мат. ожидания и дисперсии ф-ии цели;
- вероятность превышения функцией цели некоторого фиксированного порога.
Документ
Категория
Разное
Просмотров
27
Размер файла
38 Кб
Теги
билет
1/--страниц
Пожаловаться на содержимое документа