Тема 2 Поставка задач линейного программирования

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

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

В общем виде:

L()=++….-> max (min)

++…+=

++…+=

++…+=

=const

Алгоритм решения ЗЛП графическим методом:

1. Находим область дополнительных решений и систему ограничений задачи

2. Строим вектор ЦФ

3. Определяем положение перпендикуляра к ЦФ (линия уровня)

4. Смещаем линию уровня (для двумерности варианта в доль оси вектора) в направлении возрастания

5. Перемещение линии или поверхности уровня в доль вектора производиться до тех пор пока у нее не окажется одна общая точка с ОДЗ эта точка и будет решением задачи (частный случай-возможна ситуация когда решением является отрезок границей области определения или сегмент поверхности перпендикулярный вектору ЦФ в этом случае задача имеет бесконечное множество решений в пределах ограничения

6. Для определения результата находим координаты точки экстремума и значение ЦФ в этой точке координат в этой точке будут означать значениям аргументам значения ЦФ соответствует max или min зависимо от задачи.

L==++…

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

Фирма выпускает два вида мороженного: сливочное и шоколадное.

Таблица 1.

Материалы	Расход на 1 кг упаковки		Запасы (кг)
	Сливочное	Шоколадное
Молоко	0,8	0,5	400
Наполнитель	0,4	0,8	365
Цена за единицу	16	14

1. Спрос на сливочное >спрос на шоколадное но не больше чем100 единиц

2. Спрос на шоколадное ≤ 350 единиц в сутки

шоколадное

3. Производство ≥0

сливочное

P->max P=+

-> производство сливочного мороженого

-> производство шоколадного мороженого

=16

=14

4. Молоко=0,8+0,5≤400

5. Наполнитель = 0,4 +0,85≤365

≥0, ≥0

6. ≤+100

7. ≤350

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

Анализируя полученный график можно оценить какие меры можно предпринять для дополнительного улучшения возможных результатов.

Научная составляющая ио

ИО первоначально сформировалась как прикладная дисциплина –набор практических методик по формализации задач из различных направлений человеческой деятельности и вычисление результата (западная концепция) . По мере накопления материала и развитие науки стал проявлять научные компоненты в 50х-60х прошлого столетия активное развитие ИО как науки происходило в СССР. Постепенно сформировался подход к ИО как к разделу системного анализа . Сегодня определяют следующие методы подхода:

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

-аналитическая дедукция и логика- утверждают что целое можно объяснить рассматривая его части , следовательно целое можно разделить на составляющие и изучать их по отдельности;

Дедуктивный подход не применим при анализе сложных систем (компьютерные системы, социальные структуры) и на современном этапе его роль в качестве объединяющих концепций выполняет системный подход.

-индуктивный подход обобщает отдельные факты на основе чего создается общая теория объекта или явления.

Необходимость в применении системного анализа исследования операций возникает если:

-решается новая проблема, которую необходимо сначала сформулировать, определить значимые параметры и их соотношение;

-решение предполагаемых сопоставимых целей и различных способов их достижения;

-проблема имеет разветвление связи вызывающие отдаленные последствия в различных направлениях следовательно есть необходимость оценки суммарной эффективности и затрат;

-если существуют варианты решения которые невозможно сравнить;

-при создании новых сложных систем;

-при реконструкции действующего производства, при реинжиниринга действующих процессов;

- при создании информационной системы и компьютеризированных систем управления;

-когда важное решение необходимо принимать в условиях неопределенности либо на отдельную перспективу.

Система –совокупность компонентов, взаимосвязей и свойств.

l=(..…) x- компонентов

l=(..…)

i=(1,…,n)

Математика рассматривает систему как подмножество проявлений и атрибутов данной системы.

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

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

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

Среда функционирования системы- совокупность всех объектов не являющихся частью системы, изменения которой влияют на систему или которая меняется под ее воздействием.

Связи между системой и средой могут быть принципиального характера (совместима ли система с характером среды) или конструктивного характера.

Назначение системы – очень важное при анализе системы, и одна из наиболее сложных , которая отображает то что необходимо достигнуть или то что должно возникнуть (прообраз бедующий системы). Назначение системы не является фиксированным и может манятся в процессе функционирования оно конкретизирует с помощью целей которых может быть одна, две или много.

Назначение системы может быть различным в зависимости от наблюдения. Назначение системы может восприниматься по разному ее создателем, ее владельцем, тем кто обеспечивает ее функционирование и потребители ее продуктов.

Цели могут быть:

-тактические –желаемые результаты, достижения которых происходит за определенный достаточно короткий период времени;

-стратегические (макро цены)-достигаются за более длительный период и предполагают реализацию нескольких или больше количество тактических целей;

-идеалы-цели которые никогда не могут быть достигнуты но к которым система может постоянно приближаются последовательно реализуя макро- и тактические цели;

-функциональная-цель которая уже известна системе и возможно ранее уже достигнута в любой точке времени и пространства;

-цель-аналог- цель которая не достигалась системой в текущих условиях но достигалась другой системой но при других характеристиках среды функционирования.

Определение и базовые понятия

1. Декомпозиция-разделение объекта на части, что бы облегчить его осмысление и анализ, при изучении системы, декомпозиция производится следующим образом:

-создается упрощенная модель системы, отображаемая общие принципы ее функционирования;

-для сегментов которые нужно изучить более подробно разрабатывая модели низшего порядка;

2) Элемент-некоторый объект (материальный, энергетический,экономический,социальный, информационный)имеющий ряд особенностей внутри структура которой несущественна, то есть он декомпозиции не подлежит;

3) Функция системы- все что система выполняет или сможет выполнить согласно своего назначения;

4) Множество функций системы-это воплощение предназначения системы в действия, а также совокупность возможных составляющих системы во времени, пространстве либо плоскости других характеристик системы;

5) Форма-внешний вид объекта без относительных его содержаний;

6) Совокупность-объединение в одно множество параметров или объектов независимо от их формы, места и назначения;

7) Структура-совокупность частей и элементов находящихся во взаимодействии в строго переделённом порядке, обеспечив реализацию функций системы.

Изменение структуры может происходить:

- в зависимости от цели создателя системы;

-в следствии создания новых вариантов ее организации;

-как результата эволюции системы над воздействием внешних возмущений;

-модификация с целью повышения устойчивости системы;

8) Планирование – определение бедующего, поведения объекта в детерминированном виде;

9) Регулирование и управление- обеспечении функционирования системы в рамках заданных параметров;

10) Учет- определение фактического состояния объекта в конкретные моменты времени;

11) Контроль- определение отклонений между запланированными и фактическими значениями параметра объекта, в дискретные моменты времени;

12) Анализ –подведение итогов функционирования объекта за определенный временной период оценка влияющих факторов и их значимости;

13) Прогнозирование- определение бедующих характеристик уже функционирующей системы с учетом коррекции на взаимодействии с окружением.