Студопедия

КАТЕГОРИИ:


Архитектура-(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. I. Международная торговая практика широко использует такие понятия как мировые деньги, мировые рынки, мировые цены
  2. I. Основные задачи
  3. I. Основные категории страхования.
  4. I. Основные показатели вариации
  5. I. Основные положения
  6. I. Основные этапы развития знаний об эндокринных железах.
  7. I. Сущность и основные функции перестрахования.
  8. I.3. Основные принципы психологии.
  9. II. Основные задачи и функции
  10. II. Основные направления реформы
  11. II. Основные направления улучшения использования ОФ и производственных мощностей.
  12. II. Основные направления улучшения использования ОФ и производственных мощностей.



 

Задачи линейного программирования самые простые => самые изученные. Они используются для детерминированных моделей, то есть:

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; Просмотров: 329; Нарушение авторских прав?;


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



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


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



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