 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Математическое программирование - раздел математики, исследующий математические модели и методы решения экстремальных задач с ограничениями
Лабораторная работа №3
Принятие решений с помощью метода линейного программирования
Цель работы: изучение формальных методов принятия решений, приобретение навыков работы с методами математического программирования
Краткие теоретические сведения
Математическая формулировка задачи принятия решения часто эквивалентна задаче отыскания экстремума (оптимума) целевой функции одной или многих переменных. Формальные методы позволяют решать так называемые задачи оптимального выбора. Для таких задач множество возможных альтернатив и планов выбора строго определено и известен аналитический вид зависимости оптимизируемой функции от независимых переменных.
Все задачи оптимального выбора имеют общую структуру. Их можно классифицировать как задачи минимизации (максимизации) M-векторного векторного показателя эффективности Fm(x), m=1,2,...,M от N-мерного векторного аргумента x=(x1,x2,...,xN), компоненты которого удовлетворяют:
hk(x) =0, k=1,2...K - системе ограничений-равенств,
gj(x) >0, j=1,2,...J – системе ограничений-неравенств,
xli<xi<xui, i=1,2...N - областным ограничениям.
Наиболее разработан и широко используется на практике аппарат одноцелевого принятия решений в условиях определенности, который получил название математического программирования.
Математическое программирование - раздел математики, исследующий математические модели и методы решения экстремальных задач с ограничениями.
Выделяют:
- задачи линейного программирования (F(x), hk(x), gj(x) - линейны);
- нелинейного программирования (F(x), hk(x), gj(x) - нелинейны);
- дискретного (в том числе целочисленного) программирования (x – дискретны, в том числе целочисленны);
- динамического программирования (x – вычисляются на каждом шаге решения задачи).
Общей задачей линейного программирования (ЛП) называется задача, которая состоит в определении максимального (минимального) значения функции
где с - коэффициенты целевой функции, ai,j, - коэффициенты системы ограничений, b - свободные члены, которые считаются неотрицательными.
Функция (1) называется целевой функцией (ЦФ) или линейной формой задачи, а условия (2)-(4) - ограничениями данной задачи. Задача ЛП может быть представлена в разных формах.
Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при выполнении условий (3) и (4), где k=m и l=n.
Основной (или канонической) задачей линейного программирования называется задача, которая состоит в определении экстремального значения функции (1) при выполнении условий (3) и (4), где k=0 и l=n.
Любое множество значений (х1*, х2*,..., хn*), которое удовлетворяет ограничениям задачи линейного программирования, является допустимым решением данной задачи (или планом). План X*=(x1*, x2*,..., xn*), при котором целевая функция задачи принимает свое максимальное (или минимальное) значение, называется оптимальным.
Простые задачи ЛП в стандартной форме допускают геометрическую интерпретацию, позволяющую непосредственно из графика получить решение. При графическом представлении двухмерной задачи ЛП область допустимых решений называют многоугольником допустимых решений. Если задача трехмерная (используется три аргумента x1, x2, x3), то область допустимых решений выглядит в виде объемной трехмерной фигуры, ограниченной с разных сторон плоскостями. С увеличением размерности задачи ЛП свыше трех переменных представить графически область допустимых решений нельзя. При n ≥ 3 многомерную область допустимых решений называют гиперполигоном или симплексом.
Операции, которые необходимо выполнить для графического решения задачи ЛП.
1. Построить прямые линии на основании ограничений (2), в которых знаки неравенств заменить знаками равенств.
2. Найти полуплоскости, которые определяются каждым из ограничений (2). В результате получается многоугольник допустимых решений.
3. На основании уравнения, описывающего ЦФ (1), построить вектор-градиент D (d1; d2), определяющий направление возрастания целевой функции.
4. Выбрав некоторое постоянное значение h, построить график ЦФ d1x1 + d2x2 = h, который должен пересекать многоугольник допустимых решений. График ЦФ будет обязательно перпендикулярен вектору D (d1; d2). Такой график иногда называют линией уровня.
5. Увеличивать значение h до тех пор, пока график ЦФ имеет хотя бы одну общую точку с полигоном допустимых решений. При увеличении h график ЦФ смещается параллельно самому себе в направлении возрастания вектора D (d1; d2).
6. Определить точку (или отрезок), где целевая функция принимает максимальное значение. В этой точке (на этом отрезке) переменные xi имеют оптимальные значения.
На рис. 1 показан типичный случай оптимального решения двумерной задачи ЛП. Из рисунка видно, что график целевой функции имеет одну единственную точку соприкосновения с полигоном допустимых решений. Причем в этой точке целевая функция имеет наибольшее значение. Оптимальное решение задачи ЛП всегда достигается в одной из вершин многоугольника допустимых решений. Именно к подобной ситуации следует стремиться при решении задачи ЛП. В показанном на рис. 1 случае число ограничений (сторон многоугольника) равно шести (m = 6). Стороны многоугольника описываются прямыми, уравнения которых берутся из ограничений (2). При построении многоугольника допустимых решений знаки неравенств в ограничениях заменяются знаками равенств. Таким образом, точки внутри многоугольника допустимых решений удовлетворяют сразу всем неравенствам (2).
Рис.1 Пример графического решения двумерной задачи ЛП
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной по отношению к исходной. Задача, состоящая в определении минимального значения функции
F=b1y1+b2y2+...+bnyn
при условиях
называется двойственной по отношения к задаче, заданной выражениями (1)-(4).
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной - на минимум.
2. Матрица
составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица
в двойственной задаче получаются друг из друга транспонированием.
3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной являются свободные члены в системе условий исходной задачи, а правыми частями в ограничениях системы условий двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная xj исходной задачи может принимать только лишь неотрицательные значения, то j-е ограничение в системе условий двойственной задачи является неравенством вида >=. Если же переменная xj может принимать как положительные, так и отрицательные значения, то j-е ограничение в системе условий двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i-е ограничение в системе условий исходной задачи является неравенством, то i-я переменная двойственной задачи yi>=0. Если же i-е ограничение есть уравнение, то переменная yi может принимать как положительные, так и отрицательные значения.
Поиск по сайту: