Студопедия

Главная страница Случайная страница

Разделы сайта

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






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Особые случаи решения ЗЛП графическим методом






    Методы получения оптимальных решений ЗЛП

    Графический метод решения ЗЛП

    Алгоритм решения графическим методом

    X
    ЗЛП имеет решение, если область определения D является выпуклым множеством точек. Множество M называется выпуклым, если X1, X2 M → X M.

    а) б)

    Рис. 3.1. Выпуклое (а) и невыпуклое (б) множества

    Для выпуклых множеств, справедливо утверждение, что пересечение выпуклых множеств есть выпуклое множество. Если X1 (x 11, x 21), X2 (x 12, x 22), то для выпуклого множества справедливо:

    Установлено, что выпуклый n -мерный многогранник является выпуклой линейной комбинацией своих угловых точек. В теории линейного программирования доказывается, что оптимальный план, если он существует, соответствует координатам одной из угловых точек выпуклой области определения D.

    Исходя из этого, и учитывая, что любая полуплоскость есть выпуклое множество, алгоритм графического метода решения ЗЛП для двух переменных x 1 и х 2 состоит в следующем:

    1. Записывается ЗЛП для двух переменных x 1 и х 2.

    (3.1)
    ,

    (3.1)
    (3.2)

    . (3.3)

    2. По ограничениям (3.2) и (3.3) строится множество всех допустимых решений D.

    3. По целевой функции определяем градиент направления перемещения линии уровня = с 1 х 1 + с 2 х 2, которая перпендикулярна вектору :

    4. Перемещаем линию уровня параллельно самой себе в направлении вектора . Первая точка встречи линии уровня с областью D соответствует точке min, а последняя – точке max. Если D Ø, то решений нет. Если линия уровня параллельна одной из сторон области допустимых решений D, то экстремум достигается во всех точках соответствующей стороны.

     

    Пример. 3.1. Задача о диете и смесях.

    Область ограничения представляет собой неограниченную многоугольную область. Её границы представлены уравнениями прямых:

     

    Рис. 3.2. Графическое решение задачи о диете и смесях

    Определяем

    α = 4 х 1 + 6 х 2,

    и

    .

    Перемещаем в направлении вектора и определяем, что точкой входа в область допустимых решений является точка В, координаты которой определяем из условия:

    Откуда х 1 В = 2; х 2 В = 3

     

    Пример 3.2. Задача об использовании ресурсов

     

     

    Рис. 3.3. Графическое решение задачи об использовании ресурсов

    С (312, 5; 300).

    Пример 3.3. Задача о банке

    Рис. 3.4. Графическое решение задачи о банке

    x 1c = 70; x 2c = 30.

    .

    Если r 1=18 %, r 2=12 %, то

     

    Особые случаи решения ЗЛП графическим методом

     

    1) max f (x1, x2)= 3 x1 + 5 x2,

    x1, 2 0.

    Рис. 3.5 Случай отсутствия области решений D

    2) max f (x1, x2)= 3 x1 + 2 x2,

    x1, 2 0.

    Рис. 3.6 Значение целевой функции не ограниченно возрастает

    3)max f (x1, x2)= 8 x1 + 10 x2,

    x1 0.

     

     

    Рис. 3.7. Случай неединственности оптимального решения

    Неединственность решения: множество точек отрезка ВС (ВС׀ ׀ α).

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.