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

Общая постановка задачи линейного программирования (ЗЛП)

Читайте также:
  1. Data Mining и Business Intelligence. Многомерные представления Data Mining. Data Mining: общая классификация. Функциональные возможности Data Mining.
  2. I Психологические принципы, задачи и функции социальной работы
  3. I. 1.1. Пример разработки модели задачи технического контроля
  4. I. 1.2. Общая постановка задачи линейного программирования
  5. I. 2.1. Графический метод решения задачи ЛП
  6. I. 3.1. Двойственная задача линейного программирования
  7. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  8. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  9. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  10. I. Общая установка сознания
  11. I. Общая характеристика.
  12. I. Ситуационные задачи и тестовые задания.

Найти вектор пространства En который максимизирует (минимизирует) функцию цели

(1)

при следующих условиях

(2)

x1,x2,…,xp≤0, (p≤n) (3)



  1. - функция цели

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

  3. - прямые ограничения задачи


Условимся относительно терминологии, которую будем использовать в дальнейшем.

Вектор пространства En, координаты которого удовлетворяют всем ограничниям (2) и (3) общей задачи линейного программирования называется планом (допустимым планом) ЗЛП.

Множество всех планов ЗЛП называется областью допустимых планов ЗЛП и обозначается ОДП. Решение ЗЛП находится на границе области ОДП.

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

 

2. Задача о диете.

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

Имеется n видов продуктов питания и m химических элементов, необходимых для суточного потребления.
aij – содержание i-го (i=1,2,…,m) химического элемента в одной единице j-го (j=1,2,…,n) продукта питания.
bi – минимальное суточное потребление i-го химического элемента.
cj – стоимость одной единицы j-го продукта питания.
Требуется составить суточный рацион питания – сколько продуктов каждого вида нужно приобрести, чтобы рацион имел минимальную стоимость, и питание было разнообразным.
В задаче о диете стоимость можно заменить на калорийность продуктов питания, и сформулировать задачу в следующем виде: питание должно быть низкокалорийным, но содержать все необходимые для суточного потребления химические элементы.

^ Строим экономико-математическую модель.

Управляемая переменная xj – количество продукта j-го вида, которое будем приобретать (j=1,2,…,n).

Функция цели – суммарная стоимость продуктов питания

(1)

Ограничения

(2)

xj 0, j=1,2,…,n (3)³

Решить задачу – значит найти вектор , такой, что при условиях (2) и (3).

Эта задача также является задачей линейного программирования.

 

 

3. Задача планирования производства

Задача планирования производства содержательно ставится следующим образом.

Пусть имеется некоторый экономический объект (предприятие, цех, артель и т. п.). Необходимо спланировать производство n видов продукции, если известно:

 


  1. на производство всех видов продукции используется m видов ресурсов, причем запасы каждого из них ограничены, и пусть bi (i=1,2,…,m) – это количество ресурса i-го вида, которое имеется в наличии;

  2. известна величина aij – количество i-го ресурса (i=1,2,…,m), которое затрачивается на производство одной единицы j-го продукта (j=1,2,…,n);

  3. известна стоимость cj (j=1,2,…,n) реализации одной единицы j-го продукта.


Требуется составить оптимальный план производства продукции, то есть такой план, который максимизирует суммарную прибыль от реализации всей произведенной продукции и при этом не происходит перерасхода ресурсов.

^ Строим экономико-математическую модель задачи.

 


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


Введем переменную xj (j=1,2,…n) – количество выпускаемой продукции j-го вида.



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


В нашем случае такой функцией является суммарная прибыль .

(1)

Мы будем максимизировать функцию цели.



  1. Введем ограничения на управляемые переменные – количество ресурсов каждого вида ограничено величиной bi (i=1,2,…,m).
    (2)
    К системе (2) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:
    xj 0, j=1,2,…,n (3)³
    ^ Решить задачу – значит найти такой вектор ,который будет удовлетворять всем ограничениям (2), (3) и максимизировать функцию цели.

    Легко заметить, что функция - линейная, так как все переменные используются в ней только в первой степени. Ограничения (2) представляют собой систему линейных неравенств, (3) – также линейное неравенство. Такую задачу называют задачей линейного программирования (ЗЛП).
    Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задачи (1)-(3), ее решение является далеко не тривиальным и во многом стало практически возможным только после разработки специального математического аппарата. Существенным достоинством используемых здесь методов решения является их универсальность, поскольку к модели (1)-(3) могут быть сведены очень многие как экономические, так и неэкономические проблемы.

 

4. Задача о раскрое

Постановка задачи. На раскрой поступает s различных материалов, требуется изготовить n различных видов изделий, причем продукция выпускается комплектами и в комплект входит bk изделий k -го вида. Каждая единица j -го материала может быть раскроена p различными способами так, что при использовании i -го способа получается aijk единиц изделий k -го вида. Известно, что материала j -го вида имеется cj единиц. Найти план раскроя, обеспечивающий максимальное число комплектов при заданных ограничениях на материал.

Модель.

Пусть xij – число заготовок j -го материала, раскроенных i -м способом.

5.

Это задача нелинейного программирования. Размерность задачи s x p*s. Но ее можно привести к линейному виду. Введем еще одну переменную y – количество комплектов. Тогда получим модель:

6.

Полученная модель относится к классу ЛП (ЦЛП). Размерность задачи (s+n) x (p*s+1).

Методы решения: в зависимости от необходимости наложения условия целочисленности на переменные задачи либо методы ЛП, либо ЦЛП: метод Гомори, метод ветвей и границ для ЦЛП.

5. Графический метод решения задач линейного программирования

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

Найти минимальное значение функции

при ограничениях вида

и


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

Линейная функция (1) при фиксированных значениях является уравнением прямой линии: .

Пример графического решения задачи линейного программирования с 6 условиями.

Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при . Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию:

Найти точку многоугольника решений, в которой прямая опорная и функция при этом достигает минимума.

Значения уменьшаются в направлении вектора , поэтому прямую передвигаем параллельно самой себе в направлении вектора .

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

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

Случай 1. Прямая , передвигаясь в направлении вектора или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случаелинейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

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


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)