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

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

Проверка адекватности модели

Анализ решения

Анализ модели, или решение задачи с помощью выбранного метода

Построение математической модели

Идентификация переменных

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

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

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

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

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

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

¦(x₁, x₂ … x_n) à max, min – целевая функция

g_i(x₁, x₂ … x_n) ≤ b_i, i = 1, m – ограничения.

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

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

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

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

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

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

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

¦(x₁, x₂ … x_n) à max, min – целевая функция

g_i(x₁, x₂ … x_n) ≤ b_i, i = 1, m – ограничения.

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

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

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

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

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

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

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

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

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

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

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

Задача, процесс нахождения решения которой является многоэтапным, относится к задаче динамического программирования.

Рассмотрим несколько примеров проведения операционного исследования.

Пример 1.1. Фабрика выпускает продукцию двух видов: П₁ и П₂. Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта – A, B, C. Максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы сырья A, B, C на 1 тыс. изделий П₁ и П₂ приведены в табл. 1.1.

Таблица 1.1

Исходный продукт	Расход исходных продуктов на 1 тыс. изделий (т)	Максимально возможный запас (т)
П1	П2
A B C		0,8

Изучение рынка сбыта показало, что суточный спрос на изделия П₂ никогда не превышает спроса изделия П₁ более чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П₂ никогда не превышает 2 тыс. шт. в сутки.

Оптовые цены 1 тыс. шт. изделий П₁ равны 3 тыс. руб., 1 тыс. шт. П₂ – 2 тыс. шт.

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

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

В рассматриваемом примере имеем следующее:

Переменные. Так как нужно определить объемы производства каждого вида продукции, переменными являются:

X₁ – суточный объем производства изделия П₁ в тыс. шт.;

X₂ – суточный объем производства изделия П₂ в тыс. шт.

Целевая функция. Так как стоимость 1 тыс. изделий П₁ равна 3 тыс. руб., суточный доход от ее продажи составит 3X₁ тыс. руб. Аналогично доход от реализации X₂ тыс. шт. П₂ составит 2X₂ тыс. руб. в сутки. При допущении независимости объемов сбыта каждого из изделий общий доход равен сумме двух слагаемых – дохода от продажи изделий П₁ и дохода от продажи изделий П₂.

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

, .

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

Расход исходного продукта для производства обоих видов изделия

Максимально возможный запас данного исходного продукта

Это приводит к трем ограничениям:

X₁ + 2X₂ 6 (для А),

2X₁ + X₂ 8 (для В),

X₁ + 0,8X₂ 5 (для С).

Ограничения на величину спроса на продукцию имеют вид:

X₂ - X₁ 1 (соотношение величин спроса на изделия П₁ и П₂),

X₂ 2 (максимальная величина спроса на изделия П₂).

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

X₁ 0 (объем производства П₁),

X₂ 0 (объем производства П₂).

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

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

Определить суточные объемы производства (Х₁ и Х₂) изделий П₁ и П₂ в тыс. шт., при которых достигается

(целевая функция)

при

Х₁ + 2Х₂ 6

2X₁ + X₂ 8

X₁ + 0,8X₂ 5 ограничения (1.1)

-X₁ + Х₂ 1

X₂ 2

X₁ 0, X₂ 0

Пример 1.2. Металлургическому заводу требуется уголь с содержанием фосфора не более 0,03% и с долей зольных примесей не более 3,25%. Завод закупает три сорта угля А, В, С с известным содержанием примесей. В какой пропорции нужно смешивать исходные продукты А, В, С, чтобы смесь удовлетворяла ограничениям на содержание примесей и имела минимальную цену?

Содержание примесей и цена исходных продуктов приведены в табл. 1.2.

Таблица 1.2

Сорт угля	Содержание (%)	Цена 1 т (руб.)
фосфора	золы
А В С	0,06 0,04 0,02	2,0 4,0 3,0

Построим математическую модель.

Обозначим:

Х₁ – количество угля сорта А в тонне смеси

Х₂ – количество угля сорта В в тонне смеси переменные

Х₃ – количество угля сорта С в тонне смеси модели

– стоимость 1 т смеси – целевая функция,

0,06Х₁ + 0,04Х₂ + 0,02Х₃ 0,03 (%) – ограничение на содержание фосфора в смеси,

2Х₁ + 4Х₂ + 3Х₃ 3,25 (%) – ограничение на содержание зольных примесей,

Х₁ + Х₂ + Х₃ = 1 (т) – ограничение на состав 1 т смеси.

Окончательно, математическая модель имеет вид.

Определить количество угля сортов А, В, С (Х₁, Х₂, Х₃) в тонне смеси, при которых достигается

при

0,06Х₁ + 0,04Х₂ + 0,02Х₃ 0,03

2Х₁ + 4Х₂ + 3Х₃ 3,25 (1.2)

Х₁ + Х₂ + Х₃ = 1

Х_1,2,3 0.

Пример 1. 3. (задача составления кормовой смеси (задача о диете).

Бройлерное хозяйство птицеводческой фермы насчитывает 20 000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Недельный расход корма в среднем (за 8 недель) составляет 500 г = 0,5 кг.

Для того чтобы цыплята достигли к 8-й неделе необходимого веса, кормовой рацион должен удовлетворять определенным требованиям по питательности. Этим требованиям могут соответствовать смеси различных видов кормов, или ингредиентов.

В табл. 1.3 приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Смесь должна содержать:

не менее 0,8% кальция

не менее 22% белка от общего веса смеси

не более 5% клетчатки

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

Таблица 1.3

Ингредиент	Содержание питательных веществ	Стоимость (руб./кг)
(кг/ингредиента)
Кальций	Белок	Клетчатка
Известняк Зерно Соевые бобы	0,38 0,001 0,002	- 0,09 0,50	- 0,02 0,08	0,4 0,15 0,40

Математическая формулировка задачи.

Введем следующие обозначения:

Х₁ – содержание известняка в смеси (кг);

Х₂ – содержание зерна в смеси (кг);

Х₃ – содержание соевых бобов в смеси (кг).

Общий вес смеси, еженедельно расходуемый на кормление цыплят:

20 000 ´ 0,5 = 10 000 кг.

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

0,38Х₁ + 0,001Х₂ + 0,002Х₃ 0,008 ´ 10 000,

0,09Х₂ + 0,50Х₃ 0,22 ´ 10 000,

0,02Х₂ + 0,08Х₃ 0,05 ´ 10 000.

Окончательный вид математической формулировки задачи:

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

Х₁ + Х₂ + Х₃ = 10 000

0.38Х₁ + 0.001Х₂ + 0.002Х₃ 80

0.09Х₂ + 0.50Х₃ 2200 (1.3)

0.02Х₂ + 0.08Х₃ 500

Х_j 0, j = 1, 2, 3.

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

Таблица 1.4

Заказ	Ширина рулона (м)	Количество рулонов
	0,5 0,7 0,9

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

Определим переменные: Х_j – количество стандартных рулонов, разрезаемых по варианту j, j = 1, 2,…, 6.

Ограничения непосредственно связаны с требованием обеспечить изготовление требуемого количества нестандартных рулонов. Используя данные табл. 1.5, получим:

Таблица 1.5

Ширина рулона (м)	Варианты раскроя рулона	Минимальное количество рулонов
0,5 0,7 0,9
Отходы (м)	0,4	0,3	0,1		0,1	0,2	-

2Х₂ + 2Х₃ + 4Х₄ + Х₅ = 150 – количество рулонов шириной 0,5 м,

Х₁ + Х₂ + 2Х₅ = 200 – количество рулонов шириной 0,7 м,

Х₁ + Х₃ + 2Х₆ = 300 – количество рулонов шириной 0,9 м.

Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид

0,4Х₁ + 0,3Х₂ + 0,1Х₃ + 0,1Х₅ + 0,2Х₆

Таким образом, математическая модель в общем виде имеет вид:

= 0,4X₁ + 0,3X₂ + 0,1X₃ + 0,1X₅ + 0,2X₆

при ограничениях:

2X₂ + 2X₃ + 4X₄ + X₅ =150

X₁ + X₂ + 2X₅ = 200

X₁ + X₃ + 2X₆ = 300

X_j ≥ 0; X_j – целые; j = 1,..., 6.

Контрольные вопросы

1. Дайте несколько определений термина «исследование операций» и сравните их между собой.

2. Дайте определение термина «операция».

3. В чем состоит цель, которую преследуют в процессе исследования операций?

4. Приведите примеры экономических проблем, решаемых с помощью ММИО.

5. Перечислите этапы ИО.

6. Опишите подробно третий этап ИО.

7. Какие переменные модели ИО называются управляемыми?

8. Какие переменные модели ИО называются неуправляемыми?

9. Запишите формулировку задачи математического программирования.

10. Приведите классификацию ММИО.

Задание №1

1. Завод – производитель высокоточных элементов для автомобилей – выпускает два различных типа деталей Х и Y. Завод располагает фондом рабочего времени в 4000 чел.-ч. в неделю. Для производства одной детали типа Х требуется 1 чел.-ч, а для производства одной детали типа Y – 2 чел.-ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10 000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Составить математическую модель задачи, если необходимо получить информацию, сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю при том, что доход от производства одной детали типа Х составляет
30 ф. ст., а от производства одной детали типа Y– 40 ф. ст.?

2. Завод по производству электронного оборудования выпускает персональные компьютеры и системы подготовки текстов. В настоящее время освоены две модели:

а) «Юпитер» – объем памяти 1 Гб, одинарный дисковод;

б) «Марс» – объем памяти 2 Гб, двойной дисковод.

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

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

Дата добавления: 2014-12-29