Исследование операций на основе стандартных программ

М Г Г У 

м о с к о в с к и й 

ГОСУДАРСТВЕННЫЙ 
ГОРНЫЙ УНИВЕРСИТЕТ 

РЕДАКЦИОННЫЙ 

С О В Е Т 

Председатель 

Л.А. 
ПУЧКОВ 

Зам. председателя 

Л.Х. 
ГИТИС 

Члены редсовета 

И.В.ДЕМЕНТЬЕВ 

A. П.ДМИТРИЕВ 

Б.А. КАРТОЗИЯ 

В.В. КУРЕХИН 

М.В. КУРЛЕНЯ 

В.И. ОСИПОВ 

э.м. 
СОКОЛОВ 

К.Н. ТРУБЕЦКОЙ 

В.В. ХРОНИН 

B. А. ЧАНТУРИЯ 

Е.И. ШЕМЯКИН 

ИЗДАТЕЛЬСТВО 

МОСКОВСКОГО 

ГОСУДАРСТВЕННОГО 

ГОРНОГО 
УНИВЕРСИТЕТА 

ректор 
МГГУ, 
чл.-корр. 
РАН 

директор 
Издательства 
МГГУ 

академик 
РАЕН 

академик 
РАЕН 

академик 
РАЕН 

академик 
РАЕН 

академик 
РАН 

академик 
РАН 

академик 
МАНВШ 

академик 
РАН 

профессор 

академик 
РАН 

академик 
РАН 

B.C. ЧЕПУРНИЦКИЙ 
А.В. ЧЕСВОКОВ 

«Теории 
экономического 
управления» 

И С С Л Е Д О В А Н И Е 

О П Е Р А Ц И Й Н А О С Н О В Е 

С Т А Н Д А Р Т Н Ы Х 

П Р О Г Р А М М 

Под научной редакцией 
А.Б. 
Хлопотова 

МОСКВА 
ИЗДАТЕЛЬСТВО 
м о с к о в с к о г о 
ГОСУДАРСТВЕННОГО ГОРНОГО 
УНИВЕРСИТЕТА 

Z О О Z 
А 

УДК 622.338 

Международная 
академическая 
ассоциация 

Международная 
академия наук и искусств 

Чепурницкий B.C., Чесноков А.В. 
Исследование операций на основе стандартных программ/ 
Под. ред. А.Б. Хлопотова. — М.: Издательство Московского 
государственного горного университета, 2002. — 121 с. (Теории 
экономического управления) ISBN 5-7418-0237-0 

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

УДК 622.338 

ISBN 5-7418-0237-0 
© B.C. Чепурницкий, А.В. Чесноков, 2002 
© Издательство МГГУ, 2002 

Содержание 

I. Методы и модели оптимального программирования 
6 

II. Распределительные задачи 
9 

1. Задача о назначении 
9 

2. Оптимальное распределение однородных ресурсов 
16 

3. Оптимальное распределение неоднородных ресурсов 
23 

4. Целочисленное программирование 
30 

4.1. Целочисленные линейные задачи оптимизации 
39 

4.2. Целочисленные задачи с бинарными переменными .... 
41 

4.3. Транспортная задача с условием целочисленности ..... 
46 

III. Задачи управления запасами 
49 

I .Задача управления запасами при удовлетворении спроса 
49 

2. Задача управления запасами при неудовлетворении спроса .. 
58 

IV. Задачи массового обслуживания 
67 

1. Задача анализа одноканальной замкнутой системы массового 
обслуживания 
69 

2. Задача оптимизации структуры одноканальной замкнутой СМО 
с ожиданием 
76 

V. Матричные вычисления в экономических задачах 
82 

1. Модель межотраслевого баланса Леонтьева 
82 

I. I. Вычисление совокупного выпуска по заданному спросу . 
82 

1.2. Цены в системе межотраслевых связей 
93 

1.3. Простейшая модель экспорта и импорта 
97 

1.4. Линейная модель международной торговли 
99 

VI. Функции многих переменных в экономических задачах 
103 

1. Производственные функции 
103 

2. Эластичность производственной функции (эластичность выпуска) 
110 

3. Производственная функция Кобба-Дукласа 
112 

4. Производственная функция C E S (функция с постоянной эластичностью замещения) 
117 

Список литературы 
121 

М е т о д ы и модели оптимального 
программирования 

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

В настоящее время наибольшее распространение получило линейное программирование. 

Методика решения экономических задач, которые в последствии названы задачами линейного программирования, 
была разработана и опубликована академиком Л.В. Канторовичем в 1939 г. 

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

В общем случае задача оптимизации имеет следующую 
математическую постановку [8 ]: 

F = f(xj)-> 
max(min); 

aj <Xj<b}\ 
i = l,m; 7=1,л. 

(0 

где gj — ограничения; щ и bj — нижнее и верхнее предельно 
допустимые значения л). 

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

6 

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

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

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

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

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

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

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

Ограничения определяют существующие связи между искомыми переменными. 

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

Значения искомых переменных, удовлетворяющих граничным условиям и ограничениям, называют допустимым 
решением задачи. 

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

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

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

Универсальные методы линейного программирования позволяют решать разнообразные экономические задачи — в 
этом их большое достоинство, но их недостатком является 
громозкость расчетов. Только широкое распространение вычислительной техники и создание математических программ 
(таких как Mathcad) и электронных таблиц {Excel) позволяет 
применять данные методы в производстве. 

и 

Распределительные задачи 

В общем случае математическая модель задачи распределения ресурсов с числом переменных п и ограничений т имеет 
следующий вид [8]: 

л 

F = 'YjCjXj -> max (min); 

л 

Y,ai}Xj<bi\ 
\ 
(2) 

dj <Xj < Dj\ i = \,m\ j = l,n , 

где с, — коэффициенты в целевой функции; ау — норма расхода z'-ro ресурса для выпуска единицы у-й продукции; 
— 
имеющийся ресурс; dt и Д — минимальное и максимальное допустимые значения х}. 

1. Задача о назначении 

Условие 

Порт имеет / количество разных марок кранов. Необходимо разгрузить j разных грузовых судов. Известна стоимость 
разгрузки, выполненной каждым видом кранов. Требуется 
распределить краны по объектам работ так, чтобы обеспечить выполнение всех работ с минимальными суммарными 
затратами. 

Выявление основных особенностей, 
взаимосвязей 
и количественных 
закономерностей 

Введем переменные Ху, которые равны 1, если г'-й кран работает на /-м судне, и 0, если он не работает там [3]. 
Сформулируем ограничения. 

9 

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

=!,(/ = 1,2,..., 
го). 
(3) 

2. На каждом судне может работать только один кран. 
Это ограничение можно записать так: 

£ ^ = I , 0 ' = U,...,ro). 
(4) 

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

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

Обозначим через Yy стоимость разгрузки на у'-м объекте 
/-м кране. Тогда критерий оптимизации Y— суммарная стоимость выполнения всех работ — запишется в таком виде: 

^ = £ £ в д . 
(5) 

i=i j=\ 

Совокупность ограничений и целевой функции образует 
математическую модель типичной экстремальной комбинаторной задачи. Ее решение представляет собой некоторую перестановку чисел, а количество перестановок резко увеличивается с ростом п и принимает значение N = п\. 

Решение задачи с помощью программы Malhcad 

1. На рабочем листе напечатаем название для первой 
формулы. Для этого 
щелкнем указателем мыши па нужное 
место, на листе появится красный крестик, и в меню Вставка 
выберем команду Область текста. Переключим клавиатуру на 
русский язык. В поле Тип шрифта поставим Arial Суг. В появившейся области напечатаем текст: Критерий оптимизации 
— целевая функция. 

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

10 

Y(X11, X12, X13, X21, X22, X23, X31,32, X33) :=20 • X11 + 40 • X12 + ... 

... + 50 X 1 3 + 2 0 X21 + 40 X 2 2 + 1 0 X23 + 10 X31+50 
X 3 2 + . . . 

... + 20- X33 

Первая цифра в переменной X определяет номер крана, а 
вторая — номер судна. 

Знак := является знаком присваивания и вводится следующим образом. 

1. В меню Вид, подменю Панели инструментов щелкнем 
по названию панели Математика (рис. 1), на экране появится 
эта панель. 

& M a t h c a d Professional 
[ с и м п л е к с - м е т о д . m c c l ] 

Панели инструменте© • 

«J Файл Редактирование • &<д(. Ьгтаека Формат математика Символика Ok 

• • 
Ш Строка состояния 

[Normal 
|§|, 
ъюйю 

Ш Стандартны* 
Ш Форматирование 
Математика 

Y(X11,X12,X13.X21,X22. 

Начальные приближен!-. 

XII ^ 0 Х12:=0 Х13 =С 

Х41 ;- 0 
Х42 :- О Х43 То 

Ghren 

Система ограничений 

Области 
Приближение... 
Обновление 
CtrH-R 

Анимация... 
Весгроиэведение... 

Свойства... 

Калькулятор 
График 
Ш Матрица 
Выделение 
Калькуляция 
Ш Ьулевое 

Программирование 
Грек 
Символьный 
Модификатор 

Рис. 1. Окно программы Mathcad и меню Вид 

Название кнопок появляется при приближении указателя 
мышки к ним (рис. 2). 

iMath 
O l |Catcutator 
Kif 

ш
ш 

sm cos tan fn leg n! * 

^Дрифмети» 5ег5йе-янсд2у

ненты1 8 

$-> ~» j «1 j 

x 
+ 
1 2 
3 > 
•v 
П 
nr 

0 2 - 0 
Х23 : x 
+ 
1 2 
3 > 
•v 
П 
nr 

0 2 - 0 
Х23 : 

Панель Математика 

Панель Арифметические инструменты 

К н о п к а панели Арифметические 
инструменты 

Панель инструментов Булерово 

П о д с к а з к а н а з в а н и я к н о п к и 

К н о п к а Присвоить значение 

Рис. 2. Панели Математика и Арифметические инструменты 

II