Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Пример 1. Общая задача линейного программирования




Общая задача линейного программирования

Классификация задач исследования операций

1. Если критерий эффективности является линейной функцией, и функции в системе ограничений также линейны, то задача является задачей линейного программирования.

2. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то имеем задачу целочисленного линейного программирования.

3. Если критерий эффективности или система ограничений задаются нелинейными функциями, то это задача нелинейного программирования.

4. Если указанные функции обладают свойствами выпуклости, то задача является задачей выпуклого программирования.

5. Если в задаче математического программирования имеется переменная времени и критерий эффективности выражается через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.

6. Если функции f и (или) φ i зависят от параметров, то получаем задачу параметрического программирования.

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

8. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее с точки зрения практики решение.

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. Его методы применимы для широкого круга задач.

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

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

Дана система m линейных уравнений и неравенств с n переменными

(2.1)

и линейная функция

(2.2)

Необходимо найти такое решение системы , где

(2.3)

при котором линейная функция (2.2) принимает оптимальное (максимальное или минимальное) значение.

Найденное решение называется оптимальным решением (или оптимальным планом) задачи линейного программирования.

Система (2.1) называется системой ограничений, а функция (2.2) — линейной или целевой функцией.

Если система ограничений (2.1) состоит лишь из одних неравенств, то такая задача линейного программирования называется стандартной.

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

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

Например, стандартную задачу можно привести к каноническому виду. С этой целью в каждое из m неравенств системы ограничений следует ввести дополнительные неотрицательные переменные хn+ 1, хn+ 2, … хn+m.

Если в задаче все неравенства вида "£", то дополнительные неотрицательные переменные вводятся со знаком "+". В случае неравенства вида "³" соответствующие дополнительные переменные следует ввести со знаком "-".

Дана стандартная задача линейного программирования: найти значения переменных x1, x2, удовлетворяющие условиям:

, (2.4)

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

Приведем систему к каноническому виду введением дополнительных переменных: ,

(2.5)




Поделиться с друзьями:


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


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



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




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