2. Теоретические основы графического метода линейного программирования. Введение в исследование операций

Исследование операций — научная дисциплина, занимающаяся разработкой и прак­тическим применением методов наиболее эффективного управления различными органи­зационными системами.

Другими словами, исследование операций — научное направление, целевая установ­ка которого - разработка методов анализа целенаправленных действий (операций) и объ­ективная (в частности, количественная) сравнительная оценка решения.

Операция — любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа её проведения, организации, иначе — от выбора не­которых параметров. Всякий определённый выбор параметров называется решением.

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

Эффективность операции — степень её приспособленности к выполнению задачи — количественно выражается в виде критерия эффективности - целевой функции.

Дня применения количественных методов исследования требуется построить мате­матическую модель операции.

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

Этапы исследования операций

Усложнение производства, техники и организационной структуры общества при­водит к тому, что принятие решений и эффективное руководство все больше и больше нуж­даются в широкой, точной и быстрой информации, количественной оценке и прогнозе ре­зультатов, последствий принятых решений. Назначение методов исследования операций — объективно разобраться в каждом явлении, численно оценить предлагаемые целенаправ­ленные действия и, возможно, предложить варианты решений, отличные от тех, которые рассматривали хозяйственные или другие руководители.

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

Как правило, это:

1. Постановка задачи.

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

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

4. Анализ модели или получение решения задачи.

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

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

Реализация полученного решения на практике.

Краткое описание каждого этапа

1,2) Постановка задачи является одним из наиболее важных этапов исследования операций. При постановке задачи исследования операций необходимо определить цель, преследуемую субъектом управления (ЛПР) и установить, значение каких характеристик (управляемых переменных) исследуемой системы (процесса) можно варьировать, а изме­нение значений каких переменных (неуправляемых) не зависит от решений ЛПР. Кроме того, на данном этапе необходимо определить требования, условия и ограничения на ис­следуемую операцию. На этом же этапе должны быть решены проблемы информационно­го обеспечения будущей модели ИО.

3) Построение модели. На этом этапе необходимо выбрать модель, наиболее под­ ходящую для адекватного описания ИО. При построении модели должны быть установле­ны количественные соотношения для выражения целевой функции (ЦФ) и ограничений в виде функций от управляемых переменных. Наиболее важным типом моделей ИО явля­ются математические модели (ММ). В основе их построения лежит допущение о том, что все переменные, ограничения, их связывающие, а также целевая функция количественно измеримы. Поэтому если представляют собой n управляемых переменных, а условия функционирования исследуемой системы (ИС) характеризуются m ограниче­ниями, то ММ может быть записана в следующем виде:

- целевая функция

- ограничения

4. Анализ модели обычно производится с помощью методов математического про­граммирования.

5. Анализ решения или анализ на чувствительность — это процесс, реализуемый по­сле того, как оптимальное решение задачи получено. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели, т.е. фактически рассматривается совокупность моделей, что придает исследуемой опера­ции определенную динамичность.

6. Решение, полученное при помощи анализа модели, не может, однако, не­посредственно быть рекомендовало для практической реализации. Математическая мо­дель, как и любая другая модель, лишь частично отображает действительность, акценти­рует отдельные ее аспекты. Адекватность модели исследуемой операции и, следовательно, качество полученного результата можно проверить, сопоставлял результаты, установлен­ные без использования модели, с результатами, вытекающими из анализа модели.

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

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

Математическое программирование — область математики, разрабатывающая тео­рию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изме­нения этих переменных.

Задача математического программирования (ЗМП) имеет вид:

— целевая функция

—ограничения

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

Прежде всего, задачи математического программирования делятся на задачи ли­нейного и нелинейного программирования. При этом если все функции и линейные, то соответствующая задача является задачей линейного программирования. Бели же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.

Наиболее изученным разделом математического программирования является ли­нейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ.

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

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

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

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

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

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

Выделяют отдельные классы задач стохастического и динамического программи­рования.