Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Обоснование симплекс-метода. ⇐ ПредыдущаяСтр 3 из 3
Имеется ЗЛП, представленная в форме с ограничениями-равенствами: Пусть имеется набор переменных, который является допустимым:
В этом случае можно использовать симплекс-таблицу для получения оптимального решения. Выполним обоснование симплекс-метода. Определение. Основная ЗЛП является невырожденной, если в любом ее допустимом базисном решении, значения всех ее базисных переменных строго положительны. Введем предположения:
(Существует такое с, что при любом допустимом решении, .) При введенных предположениях справедлива следующая теорема: Теорема. При выполнении предположений (1)-(3) основная ЗЛП имеет, по крайней мере, одно оптимальное базисное решение. Это решение может быть достигнуто симплекс-процессом, исходя из любого допустимого базисного решения за конечное число шагов. Замечания по реализации симплекс-процесса. Рассмотрим 2 случая.
а) в строке F нет положительных коэффициентов. В этом случае получено минимальное значение линейной формы F. б) в F есть , но в выбранном столбце для поиска генерального элемента нет положительных коэффициентов . Это означает, что F не ограничена снизу. То есть, при все базисные переменные останутся положительными. Пример.
Рекомендация: Сменить столбец или строку, то есть выбрать другой генеральный элемент. Получение допустимого решения ЗЛП методом введения искусственного базиса. Метод позволяет: 1. Разбить множество переменных ЗЛП на подмножества базисных и свободных переменных, при этом обеспечивая допустимое решение ЗЛП. 2. Установить, совместна ли система линейных ограничений в области неотрицательных значений переменных. Пусть задана система линейных ограничений в виде: Будем считать, что все . Введем вспомогательную переменную , связанную с переменными соотношением
Соотношение (**) будет справедливо, если В силу неотрицательности очевидно, что , причем равенство нулю достигается лишь тогда, когда все . Имеем множество переменных ЗЛП, причем - базисные переменные, - свободные переменные. Для решения этой задачи можно применить симплекс-метод, так как имеем допустимое решение. При этом необходимым и достаточным условием существования допустимого решения системы (*) является равенство нулю формы f. Если min f =0, это означает, что существует множество неотрицательных значений , которые обращают в нуль все . Сформулируем правило: Для отыскания допустимого решения системы (*) минимизируем линейную форму f при ограничениях (**). При этом в качестве свободных переменных используются , а в качестве базисных - .
Могут представиться два случая:
2. В этом случае система (*) не имеет допустимых решений. Пример. Введем вспомогательные переменные и представим ЗЛП в основной форме: Далее заполняется симплекс-таблица и преобразовывается согласно алгоритму, рассмотренному в лекции 2.
Двойственность в ЗЛП Понятие двойственности имеет значение - Теоретического характера. Позволяет анализировать изменение оптимального решения ЗЛП в зависимости от варьирования параметров задачи (Анализ устойчивости решения); - Практического характера. Позволяет осуществлять совершенствование методов планирования и управления. Пример 1. Задача об использовании сырья Оценим стоимость сырья в зависимости от доходов, которое оно приносит предприятию. Каждый i -й ресурс имеет стоимость - . Стоимость используемых ресурсов при производстве единицы j-го продукта будет составлять: Стоимость используемых ресурсов не может быть меньше дохода - . Стоимость ресурсов для производителя должна быть минимальной: Таким образом, требуется среди всех неотрицательных решений найти такое, при котором целевая функция достигала бы своего минимума. Рассмотренные постановки ЗЛП называются взаимодвойственными.
I. Прямая задача II. Двойственная к ней Матрицы коэффициентов Знаки неравенств
Условия задачи max min Свободные коэффициенты в системе линейных ограничений Коэффициенты в линейной форме
Правила построения двойственной задачи 1. Если прямая задача имеет целью , то двойственная имеет целью , и наоборот. 2. Каждому ограничению прямой задачи соответствует двойственная переменная, и наоборот. 3. Матрицы ограничений прямой и двойственной задач взаимно транспонированы. 4. Коэффициенты при неизвестных в линейной форме прямой задачи являются свободными членами в ограничениях двойственной, а коэффициенты при неизвестных в линейной форме двойственной задачи являются свободными членами в ограничениях прямой. 5. Каждой неотрицательной переменной прямой задачи соответствует ограничение в виде неравенства в двойственной; переменной, которая может принимать как положительные, так и отрицательные значения, соответствует ограничение типа равенство и наоборот. 6. Перед построением двойственной задачи необходимо привести знаки всех ограничений в соответствие с линейной формой. Если в прямой задаче , то знаки в ограничениях должны быть ≤. Если в прямой задаче , то знаки в ограничениях должны быть ≥.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-25; просмотров: 549; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.221.26.137 (0.013 с.) |