рефераты конспекты курсовые дипломные лекции шпоры

Раздел Программирование
/
Свойства задач ЛП

Реферат Курсовая Конспект

Выберите учебное заведение

Свойства задач ЛП

Свойства задач ЛП - раздел Программирование, Линейное программирование Выше В Лекции По Лп Было Показано, Что Любая Задача Лп М.б. Представлена В Ви...

Выше в лекции по ЛП было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой.

Будем рассматривать каноническую задачу, в которой система ограничений – система уравнений.

Теорема 4. Множество всех допустимых решений системы ограничений ЗЛП (задачи линейного программирования)является выпуклым, т.е. является выпуклым многогранником (или выпуклой многогранной областью). Будем называть в дальнейшем – многогранником решений.

Теорема 5. Если задача ЛП имеет оптимальное решение, то линейная функция принимает макс (мин) значение в одной из угловых точек многогранника решений.

Эта теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений.

Теорема 6. Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Из теорем 5 и 6 вытекает следствие: если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.

Итак, оптимум линейной функции ЗЛП следует искать среди конечного числа ее допустимых базисных решений.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Линейное программирование

А х а х a nxn b... при n является плоскостью а при n gt ее обобщением в n мерном...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Свойства задач ЛП

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Линейное программирование
Оптимизационная задача была сформулирована в общем виде: найти переменные х1, х2, …, хп, удовлетворяющие системе неравенств (уравнений) φi

Понятие экономико-математической модели
Существует много различных определений понятия «модель», отличающихся друг от друга. Но это понятие знакомо каждому: игрушечный корабль – модель корабля, фотоснимок пейзажа, географическая карта –

Задача об использовании ресурсов (задача планирования производства).
Для изготовления двух видов продукции П1 и П2 используют три вида ресурсов Р1, Р2 и Р3. Известны запасы этих ресурсов В1, В2 и В3 и число единиц ресурсов, затрачиваемых на изготовление единицы кажд

Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного образца в количестве А единиц. Требуется изготовить из него L разных комплектующих изделий в количествах, пропорциональных числам b1, b2, …

Система m линейных уравнений с n переменными
Система m линейных уравнений с n переменными имеет вид: а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn =

Геометрический смысл решений неравенств, уравнений и их систем
Теорема 1. Множество решений неравенства с двумя переменными а11х1 + а12х2 <= b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой а11х1 + а12х2 = b1, вкл

Является выпуклым многоугольником (или выпуклой многоугольной областью).
Каждое из неравенств в соответствии с теоремой 1 определяет одну из полуплоскостей, являющуюся выпуклым множеством точек (из математики: выпуклое множество точек – если оно вместе с любыми двумя св

Геометрический метод решения задач ЛП
Итак, выше было доказано, что множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи нахо

Симплексный метод
Выше были рассмотрены основные теоремы ЛП. Из них следует, что если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной точке многогранника решений и совпадает хотя бы с одним из допу

Нахождение оптимума линейной функции
Пример: Решим симплексным методом задачу: F=2x1 + 3х2 à maxпри ограничениях: х1 + 3х2 &l

Особые случаи симплексного метода
Неединственность оптимального решения (альтернативный оптимум): Решим симплексным методом задачу: F=3x1 + 3х2 à max

Симплексные таблицы
Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум. I. После введения добавочных перемен