Студопедия — Постановка задачи. Задача, модель которой содержит только линейные функции искомых переменных, - задача линейного программирования(ЛП)
Студопедия Главная Случайная страница Обратная связь

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

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






Задача, модель которой содержит только линейные функции искомых переменных, - задача линейного программирования (ЛП). В общем случае:

где L – критерий (целевая функция); n - количество переменных;

Ci – параметры (коэффициенты) критерия, не все Ci =0;

– параметры условий (могут быть любыми действительными числами, но одновременно все не могут равняться нулю при i=const).

b i – параметры (свободные члены), отражающие возможности по ресурсам, допустимые/требуемые значения показателей (любые действительные числа).

На часть или все переменные накладывается условие неотрицательности.

Задача состоит в определении таких значений переменных, удовлетворяющих условиям, которые доставляют максимум/ минимум линейной форме.

Основные понятия ЛП. Свойства задач ЛП

Множество D={xÎRn| AX£B, X³0} - допустимое множество задач ЛП; это множество всех решений, удовлетворяющих всем ограничениям задачи. Любое решение Х Î D - допустимое решение задачи ЛП. Допустимое решение Х* является оптимальным для задачи максимизации, если выполняется неравенство

L (X *) ³ L (X), " X Î D.

Множество называется замкнутым, если оно содержит и свою границу, в противном случае оно открытое. Множество может быть ограниченным, если на нем все переменные ограничены снизу и сверху, и неограниченным, если хотя бы одна переменная на нем не ограничена. Непрерывное множество выпукло, если вместе с любыми двумя точками оно содержит и весь соединяющий их отрезок, иначе множество будет невыпуклым.

Пусть условия задачи записаны в стандартной форме

å aijxj£ bi,

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

Пересечение выпуклых множеств выпукло (если оно не пустое). В задаче ЛП число неравенств, а, значит, число полупространств, конечно. Их пересечение и дает допустимое множество D.

Пересечение конечного числа выпуклых полупространств, если оно не пустое, называется выпуклым многогранным множеством.

Ограниченное выпуклое многогранное множество называется выпуклым многогранником (пример: пирамиды, призмы).

Таким образом, допустимое множество задачи ЛП может быть или выпуклым многогранным множеством, или выпуклым многогранником, или пустым. Других вариантов быть не может.

Критерий LCjXj – линейная функция и поэтому удовлетворяет условиям как выпуклости, так и и вогнутости одновременно.

Максимум вогнутой функции или минимум выпуклой функции на выпуклом множестве может достигаться только на границе.

Аналогичный вывод следует из рассмотрения критических точек целевой функции. Так как производная

= Const,

то точек, в которых она равна нулю или терпит разрыв, нет. Поэтому, если оптимум существует, то он может быть только на границе.

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

При решении задач ЛП возможны только три случая:

1) Условия задачи противоречивы (несовместны), допустимое множество пустое и, следовательно, задача неразрешима.

2) Условия задачи совместны, но допустимое множество неограниченно. Тогда возможны два исхода:

а) если критерий неограничен на этом множестве, то задача неразрешима;

б) если критерий ограничен, то задача разрешима.

3) Условия непротиворечивы и множество является выпуклым многогранником. В этом случае задача всегда разрешима.

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








Дата добавления: 2015-04-19; просмотров: 569. Нарушение авторских прав; Мы поможем в написании вашей работы!



Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

ФАКТОРЫ, ВЛИЯЮЩИЕ НА ИЗНОС ДЕТАЛЕЙ, И МЕТОДЫ СНИЖЕНИИ СКОРОСТИ ИЗНАШИВАНИЯ Кроме названных причин разрушений и износов, знание которых можно использовать в системе технического обслуживания и ремонта машин для повышения их долговечности, немаловажное значение имеют знания о причинах разрушения деталей в результате старения...

Различие эмпиризма и рационализма Родоначальником эмпиризма стал английский философ Ф. Бэкон. Основной тезис эмпиризма гласит: в разуме нет ничего такого...

Индекс гингивита (PMA) (Schour, Massler, 1948) Для оценки тяжести гингивита (а в последующем и ре­гистрации динамики процесса) используют папиллярно-маргинально-альвеолярный индекс (РМА)...

Решение Постоянные издержки (FC) не зависят от изменения объёма производства, существуют постоянно...

ТРАНСПОРТНАЯ ИММОБИЛИЗАЦИЯ   Под транспортной иммобилизацией понимают мероприятия, направленные на обеспечение покоя в поврежденном участке тела и близлежащих к нему суставах на период перевозки пострадавшего в лечебное учреждение...

Кишечный шов (Ламбера, Альберта, Шмидена, Матешука) Кишечный шов– это способ соединения кишечной стенки. В основе кишечного шва лежит принцип футлярного строения кишечной стенки...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия