Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Задачи линейного программирования

 

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

Оптимизационная задача – это математическая задача, заключающаяся в нахождении оптимального (т.е. максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений (ОДЗ).

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

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

В общем виде задача ЛП имеет следующий вид:

, (5.1)

, , (5.2)

, , (5.3)

(5.4)

где , , – заданные постоянные величины.

Функцию (5.1) называют целевой функцией; системы (5.2), (5.3) – системой ограничений; условие (5.4) – условием неотрицательности проектных параметров.

Совокупность проектных параметров , удовлетворяющих ограничениям (5.2), (5.3) и (5.4), называют допустимым решением или планом.

Оптимальным решением или оптимальным планом задачи ЛП называется допустимое решение , при котором целевая функция (5.1) принимает оптимальное (максимальное или минимальное) значение.

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

,

, , (5.5)

.

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

,

, , (5.6)

.

 

Каноническую задачу ЛП можно также записать в матричной и векторной форме.

 

 

Матричная форма канонической задачи ЛП имеет следующий вид:

,

, (5.7)

,

где

,

,

.

Векторная форма канонической задачи ЛП:

,

, (5.8)

,

где С, X, Ai, B – векторы:

,

,

, (),

,

– скалярное произведение векторов C и X.

Векторное неравенство означает, что все компоненты вектора Х неотрицательны, т.е. .

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

1. Задачу минимизации функции можно свести к задаче максимизации и наоборот путем замены знаков коэффициентов на противоположные, поскольку .

2. Ограничения-неравенства (5.2) можно заменить эквивалентными ограничениями-равенствами путем введения дополнительных неотрицательных переменных.

Теорема 5.1. Любому решению неравенства

(5.9)

соответствует определенное решение уравнения

(5.10)

в котором

(5.11)

и, наоборот, каждому решению уравнения (5.10) и неравенства (5.11) соответствует определенное решение неравенства (5.9).

Таким образом, если ограничения-неравенства вида , то можно преобразовать в ограничение-равенство вида .

При ограничении-неравенстве вида , то можно преобразовать в ограничение-равенство вида .

При переходе от ограничения-равенства к ограничению-неравенству необходимо выразить одну из переменных через остальные, затем исключить ее с переходом к неравенству, при этом, если коэффициент при данной переменной +1, то переходим к неравенству вида , а если –1, то .

3. Каждое ограничение-равенство вида можно записать в виде двух неравенств:

, . (5.12)

4. Переменная , не ограниченная условием неотрицательности можно заменить разностью двух дополнительных неотрицательных переменных:

. (5.13)

 

<== предыдущая лекция | следующая лекция ==>
Табличная форма представления системы линейных уравнений | Свойства задач ЛП
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 408; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.02 сек.