Студопедия

КАТЕГОРИИ:


Загрузка...

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

2) ограничения, которые накладываются на элементы решения, имеют вид линейных равенств или неравенств относительно х1..хn.

Определение линейного программирования: метод математического программирования, разработанный для оптимизации использования ограниченных ресурсов.

Задачи линейного программирования включают в себя три основных этапа:

1. определение переменных, которые заданы в условиях задачи;

2. определение целевой функции, которую будет оптимизировать;

3. определение ограничений, которым должны удовлетворять переменные.

Пример. Есть сотрудник некой фирмы, которому надо в течение 5 недель 5 раз посетить город Б. Сам он находится в городе А. В первый раз он должен быть в городе Б в понедельник первой недели, последний – в среду пятой недели. Билет из А в Б туда и обратно стоит 400$, но если вылет приходится на конец недели, то на 20% дешевле. Если брать билет в одну сторону, то это будет 75% от стоимости билета. Задача – минимизировать затраты.

Решение (3 этапа)

1. Определить альтернативное решение, которое существует.

2. Определить, какие накладываются ограничения.

3. Выбрать критерий отбора из альтернативных решений.

 

I. Решение

1. Первое возможное решение – купить пять билетов туда и обратно, но фирма не согласна.

2. Первый билет из А в Б, далее 4 билета туда и обратно на конец недели из А в б и один билет из Б в А на нужную дату.

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

II. Ограничения

Дни недели.

III. Критерий отбора

Цена.

 

1) 5x400$=2000$

2) 2x0,75x400$+4x0,8x400$=1800$

3) 5x(0,8x400$)=1600$

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

 

4.3. Основная задача линейного программирования (ОЗЛП)

как правило, даётся в виде неравенства:

max

h=c1x1+c2x2+c3x3 => оптимизируем целевую функцию

min

x1..xn – элементы решения

 

Пример. Есть сырьё, из которого должно быть изготовлено несколько видов изделия, i=1..3, то есть 3 изделия, а сырья 4. x1..x3 – элементы решения, тогда aij , где i – вид изделия, а j – вид сырья, - расход сырья на изделие, с1, с2, с3 – прибыль (в

Ограниченияγ1...γn выражаются в наличии на складе сырья (запасов). Задача тогда сводится к след: найти такие неотрицательные значения х1...х3, чтобы они удовлетворяли неравенствам с ограничениями γ1...γn, и обращали линейную функцию этих переменных в max or min. Количество изделий не должно быть больше определенного в хз где: х1≤β1, x2≤β 2, x3≤β 3.



 

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

 

a11x1 + ... + an1xn = b1

- - - - - - - - - - (*)

a1mx1 + ... + anmxn = bm

α = c1x1 + ... + сnxn => max min (**)

переход от неравенств к равенствам:

дано:

3x1 + 2x2 - x3 ≥ 4

x1 – 2x2 + 3x3 ≤ 10 │×(-1)

 

α = 4x1 – x2 + 2x3 → max

 

3x1 + 2x2 – x3 – 4 ≥ 0

-x1 + 2x2 – 3x3 + 10 ≥ 0

 

Введем новые неотрицательные переменные y1,y2

 

3x1 + 2x2 – x3 = y1

-x1 + 2x2 – 3x3 =y2

 

Найти такие неотрицательные значения x1…xn и y1,y2, чтобы они удовлетворяли равенствам и обращали целевую функцию в max и min.

Основные критерии, которым должно удовлетворять решение озлп:

1.Допустимость

2.Оптимальность

 

1.Допсутимое решение - всякая совокупность неотрицательных значений x1…xn, удовлетворяющих условию (*)

2. Оптимальное – то из допустимых, которое преобразует функцию (**) в max or min.

 

Задача может не иметь решений в следующих случаях:

­1.Уравнения (*) могут быть несовместимыми, т.е. противоречить друг другу

2.Положительных значений решений x1…xn может не существовать

3.Решение существует, но оно не оптимально

 





Дата добавления: 2014-01-14; Просмотров: 309; Нарушение авторских прав?;


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



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.198.244.0
Генерация страницы за: 1.678 сек.