Содержание.
1. Основные теоретические сведения 6
1.1 Динамическое программирование 6
1.2 Нелинейное программирование 9
1.3 Сетевые модели 11
1.3.1 Основные понятия сетевой модели 11
1.3.2 Расчет временных параметров сетевого графика 14
1.3.3 Сетевые методы 16
1.4 Решение игр (аij) с помощью линейного программирования. 16
2. Решение типовых примеров. 18
3. Задание для самостоятельной работы 31
1. Основные теоретические сведения
1.1 Динамическое программирование
Оптимальная стратегия замены оборудования.
Старение оборудования включает его физический и моральный износ, в результате чего растут производственные затраты по выпуску продукции на старом оборудовании, увеличиваются затраты на его ремонт, снижаются производительность и ликвидная стоимость.
Наступает время, когда старое оборудование выгоднее продать, заменить новым, чем эксплуатировать ценой больших затрат, причем его можно заме-нить новым оборудованием того же вида или новым, более современным.
Оптимальная стратегия замены оборудования состоит в определении оп-тимальных сроков его замены. Критерием оптимальности при этом может служить прибыль от эксплуатации оборудования, которую следует оптими-зировать, ли суммарные затраты на эксплуатацию в течении рассматриваемо-го промежутка времени, подлежащие минимизации.
Введем обозначения: r(t) – стоимость продукции , производимой за один год на единице оборудования возраста t лет.
u(t) – ежегодные затраты на обслуживание обо-рудования возраста t лет.
S(t) – остаточная стоимость оборудования воз-раста t лет.
P – покупная цена оборудования.
Рассмотрим период N лет, в пределах которого требуется определить оп-тимальный цикл замены оборудования. Обозначим через fN(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии.
Возраст оборудования отсчитывается в направлении течения процесса. Так, t=0 соответствует случаю использования нового оборудования. Времен-ные же стадии процесса нумеруются в обратном направлении по отношению к ходу процесса. Так, N=1 относится к одной временной стадии, остающейся до завершения процесса., а N=N – к началу процесса (рис. 1).
Рисунок 1.1
На каждом этапе N – стадийного процесса должно быть принято реше-ние о сохранении или замене оборудования. Выбранный вариант должен обеспечивать получение максимальной прибыли.
Функциональные уравнения, основанные на принципе оптимальности Беллмана , имеют вид:
(1.1)
(1.2)
Уравнение (1.1) описывает N-стадийный процесс, а (1.2) - одностадий-ный. Оба уравнения состоят из двух частей: верхняя строка определяет до-ход, получаемый при сохранении оборудования, нижняя – доход, получае-мый при замене оборудования и продолжение процесса работы на новом оборудовании.
В уравнении (1.1) функция r(t)-u(t) – есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N-ой стадии процесса.
Функция характеризует суммарную прибыль от (N-1)оставшихся стадий для оборудования, возраст которого в начале осуществ-ления этих стадий составляет (t+1) лет.
Нижняя строка (1.1) характеризуется следующим образом: функция
s(t)-P представляет чистые издержки при замене оборудования, возраст кото-рого t лет.
Функция r(0) выражает доход, получаемый от нового оборудования воз-раста 0 лет. Предполагается, что за переход от работы на оборудовании t лет работе на новом оборудовании совершается мгновенно., т.е. период замены старого оборудования и переход на работу на новом оборудовании уклады-вается в одну и ту же стадию.
Последняя функция в (1.1) представляет собой доход от остав-шихся (N-1) стадий , до начала осуществления которых возраст оборудова-ния составляет один год.
Аналогичная интерпретация может быть дана равнению (1.2). здесь нет слагаемого вида , т.к. N принимает значения 1,2,3,. . . ,N. Равенство следует из определения функции
Уравнения (1.1) и (1.2) являются рекуррентными соотношениями, кото-рые позволяют определить величину в зависимости от . Структура этих уравнений показывает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t+1) лет, а число оставшихся стадий уменьшается с N до (N-1).
Расчет начинают с использования уравнения (1.1). Уравнения (1.1) и (1.2) позволяют оценить варианты замены и сохранения оборудования с тем, чтобы принять тот из них, который предполагает больший доход. Эти соот-ношения дают возможность не только выбрать линию поведения при реше-нии вопроса о сохранении или замене оборудования, но и определить при-быль, полученную при принятии каждого из этих решений.
1.2 Нелинейное программирование
Задача дробно-линейного программирования.
В общем виде задача дробно-линейного программирования записывает-ся следующем образом:
(1.3)
при ограничениях
где сj, dj, bi, aij – постоянные коэффициенты и .
Рассмотрим задачу дробно-линейного программирования в виде:
(1.4)
при ограничениях (1.5)
будем считать, что .
Для решения этой задачи найдем область допустимых решений, опреде-ляемую ограничениями (1.5). пусть эта область не является пустым множест-вом. Из выражения (1. 4) найдем х2:
Прямая проходит через начало координат. При некотором фик-сированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное положение. При изменении значений L прямая будет поворачиваться вокруг начала координат (рис. 1.2).
Рисунок 1.2
Установим, как будет вести себя угловой коэффициент k при монотон-ном возрастании L. Найдем производную от k по L:
Знаменатель производной всегда положительный, а числитель от L не зависит. Следовательно, производная имеет постоянный знак и при увеличе-нии L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если угловой коэффициент прямой > 0, то прямая вращается против часовой стрелки, при отрицательном значении k – по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max (min) значение, либо устанавливаем неограниченность задачи.
Метод множителей Лагранжа.
Дана задача нелинейного программирования:
при ограничениях:
Предположим, что функция и непрерывны вместе со своими первыми частными производными. Ограничения заданы в виде уравнений, поэтому для решения задачи воспользуемся методом оты-скания условного экстремума функции нескольких переменных.
Для решения задачи составляется функция Лагранжа:
где - множитель Лагранжа.
Затем определяются частные производные:
Приравняв частные производные к нулю, получим систему:
Решая систему, получим множество точек, в которых целевая функция L может иметь экстремальные значения. Следует отметить, что условия рас-смотренной системы являются необходимыми, но недостаточными. Поэтому не всякое полученное решение определяет точку экстремума целевой функ-ции. Применение метода бывает оправданным, когда заранее предполагается существование глобального экстремума, совпадающего с единственным ло-кальным максимумом или минимумом целевой функции.
1.3 Сетевые модели
1.3.1 Основные понятия сетевой модели
Сетевая модель – графическое изображение плана выполнения ком-плекса работ, состоящего из нитей (работ)и узлов (событий), которые отра-жают логическую взаимосвязь всех операций.
В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа.
Граф – схема, состоящая из заданных точек (вершин), соединенных сис-темой линий. Отрезки соединяющие вершины графа называются – ребрами (дугами) графа.
Ориентированным называется такой граф, на котором стрелкой указаны направления всех его ребер (дуг), что позволяет определить, какая из двух его граничных вершин является начальной, а какая – конечной. Исследова-ние таких сетей проводится методами теории графов.
Теория графов отрирует понятие пути, объединяющем последователь-ность ребер.
Контур – путь, у которого начальная вершина совпадает с конечной.
Сетевой график – это орграф без контуров.
Работа – это активный процесс, требующий затрат ресурсов, либо пас-сивный (ожидание), приводящий к достижению намеченного результата.
Фиктивная работа – это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.
Событие – результат (промежуточный или конечный) выполнения од-ной или нескольких предшествующих работ.
Путь - любая непрерывная последовательность (цепь) работ и событий.
Критический путь – путь, не имеющий резервов и включающий самые напряженные работы комплекса. Работы, расположенные на критическом пу-ти – критические. Все остальные работы – ненапряженные и обладают резер-вами времени, которые позволяют передвигать сроки их выполнения, не вли-яя на общую продолжительность выполнения всего комплекса работ.
Правила построения сетевой модели
1. Сеть изображается слева на право, и каждое событие с большим по-рядковым номером изображается правее предыдущего. Общее на-правление стрелок, изображающих работы, также в основном должно быть расположено слева на право, при этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером.
2. Два соседних события могут объединятся лишь работой. Для изобра-жения параллельных работ вводятся промежуточное событие и фик-тивную работу (рисунок 1.3)
Рисунок 1.3. Рисунок 1.4
3. В сети не должно быть тупиков, т.е. промежуточных событий, из ко-торых не выходит ни одна работа (рисунок 1.4).
4. В сети не должно быть промежуточных событий, которым не предше-ствуют хотя бы одна работа (рисунок 1.5).
Рисунок 1.5 Рисунок 1.6
5. В сети не должно быть замкнутых контуров, состоящих из взаимосвя-занных работ, создающих замкнутую цепь (рисунок 1.6). Для пра-вильной нумерации событий поступают следующим образом: нумера-ция событий начинается с исходного события, которому дается №1. из исходного события №1 вычеркиваются все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа - №2 и т.д. до завершающего события (рисунок 1.7).
Рисунок 1.7
Продолжительность выполнения работ устанавливается на основании действующих нормативов или по экспертным оценкам специалистов. В пер-вом случае временные оценки являются детерминированными (однозначны-ми), во втором – стохастическими (вероятностными).
1.3.2 Расчет временных параметров сетевого графика
Основным временным параметром сетевого графика является продол-жительность критического пути. Его расчет включает два этапа:
1) прямой подход – вычисления начинают с исходного события и продол-жают до тех пор, пока не будет достигнуто завершающее событие. Для каждого события определяется одно число – ранний срок его наступле-ния.
2) обратный – вычисления начинают с завершающего события и продол-жают до тех пор, пока не будет достигнуто исходное событие. Для каж-дого события вычисляется поздний срок его наступления.
Рассмотрим прямой подход:
tiр.н. – ранний срок начала всех операций, выходящих из события i.
Если i=0 , то tiр.н = 0
tjр.н – ранний срок начала всех операций, входящих в bj. Тогда
tjр.н = для всех (i,j),где tij продолжительность операции (i,j).
Рассмотрим на конкретном примере: программа создания нового быто-вого прибора (данные в таблице 1. 1). На основании данных таблице постро-им сетевой график создания прибора с учетом вышеизложенных рекоменда-ций (рисунок 1.8).
Таблица 1.1. Программа создания нового бытового прибора.
Операции Наименование работ Непосредственно предшествующие операции Продолжительность, недели
А, Б Разработка техниче-ское документации (ТД) на прибор и его электронную часть - А – 3
Б – 2
В, Г Разработка технологи-ческой документации на электронную часть прибора и прибор А, Б В – 2
Г – 2
Д Передача ТД на при-бор А 3
Е Изготовление прибо-ров В 7
Ж Изготовление элек-тронной части прибо-ра Д, Г 3
З, К Разработка ТД на экс-плуатацию прибора и электронную часть Г, В З – 5
К - 2
И Сборка и испытание прибора Е, Ж 6
Рисунок 1.8 – Сетевой график создания прибора
1.3.3 Сетевые методы
Сетевая модель – графическое изображение плана выполнения комплек-са работ, состоящего из нитей (работ) и узлов (событий), которые отражают логическую взаимосвязь всех операций.
Задача минимизации сети состоит в нахождении ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину (рисунок 1.9).
Рисунок 1.9
На ребрах, соединяющих узлы 1, 2, 3, указаны длины. Узел 3 соединен с узлами 1 и 2 минимальной длиной 4+6=10. Если соединить узлы 1 и 2, то возникает цикл и получившаяся сеть не будет минимальной. Отсутствие цик-лов в минимальной сети дало ей название «Минимальное дерево - остов»
1.4 Решение игр (аij) с помощью линейного программирования.
Теория игр находится в тесной взаимосвязи с линейным програм-мированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и решена СМ и , наоборот, задача линейного программирования может быть представлена как игра.
Для первого игрока математическая модель задачи имеет вид:
при ограничениях
Математическую модель можно упростить, разделив все (n+1) ограни-чений на V. Это возможно при V0. При V=0 рекомендуется прибавить лю-бое положительное число ко всем элементам платежной матрицы, что гаран-тирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения это-го положительного числа. Если V<0, то надо сменить знаки неравенств. По-лагая V>0, систему ограничений можно записать так:
Положим . Так как Vmax, то
Получим задачу линейного программирования вида:
при ограничениях
Для второго игрока математическая модель записывается в виде:
при ограничениях
где
Задача второго игрока является двойственной по отношению к задаче первого игрока. Можно найти решение одного из игроков, а затем по теоре-мам двойственности – решение другого.
2. Решение типовых примеров.
Пример 2.1
Определить оптимальный цикл замены оборудования при следующих исходных данных: Р=10, S(t)=0, f(t)=r(t)-u(t), представлена в таблице 3. 1
Таблица 2.1
N 0 1 2 3 4 5 6 7 8 9 10 11 12
f(t) 10 9 8 7 6 5 4 3 2 1 0 0 0
Решение:
Функциональные уравнения, основанные на принципе оптимальности Беллмана имеют вид:
(2.1)
(2.2)
Для N=1
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Для N=2
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Вычисления продолжаются до тех пор, пока не будет выполнено усло-вие f1(1)>f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае использования старого. Результаты расчетов помещаем в таблицу 2.2
Можно не решать каждый раз уравнение (2.1), а вычисления проводить в таблице 2.2. например: вычислим f4(t):
Дальнейшие расчеты f4(t) прекращаем, так как f4(4)=23< f3(1)=24:
По результатам вычислений и по линии, разграничивающей области ре-шений сохранения и замены оборудования, находим оптимальный цикл за-мены оборудования. Для данной задачи он составляет 4 года.
Таблица 2.2
FN(t) 0 1 2 3 4 5 6 7 8 9 10 11 12
10 9 8 7 6 5 4 3 2 1 0 0 0
10 9 8 7 6 5 4 3 2 1 0 0 0
19 17 15 13 11 9 9*
27 24 21 18 17 17*
34 30 26 24 24*
40 35 32 31 30 30*
45 41 39 37 36 35 35*
51 48 45 43 41 41*
58 54 51 48 48*
64 60 56 55 54 54*
70 65 63 51 60 60*
75 72 69 67 66 65 65*
82 78 75 73 72 72*
Ответ: для получения максимальной прибыли от использования обору-дования в двенадцатиэтапном процессе оптимальный цикл состоит в замене оборудования через каждые 4 года
Пример 2.2
Для производства двух видов изделий А и В предприятие использует три типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования. Время обработки каждого из-делий, затраты, связанные с производством одного изделия, даны в таблице 2.3. оборудование 1 и 3 типов предприятие может использовать не более 26 и 39 часов соответственно, оборудование 2 типа целесообразно использовать не менее4 часов. Определить, сколько изделий каждого вида следует изгото-вить предприятию, чтобы средняя себестоимость изделия была минималь-ной.
Таблица 2.3
Тип оборудования Затраты времени на обработку одного изделия, ч.
А В
1 2 8
2 1 1
3 12 3
Затраты на производст-во одного изделия, т.р. 2 3
Решение:
Составим математическую модель задачи:
Пусть х1 – количество изделий вида А, которое следует изготовить предприятию, х2 – количество изделий вида В. Общие затраты на их произ-водство составят: (2х1+3х2)тыс. руб, а средняя себестоимость одного изделия будет равна
Так как она должна быть минимальной , то математическая модель зада-чи имеет вид:
при ограничениях
Найдем область допустимых решений. Для этого используем систему ограничений, в которой каждое неравенство представляет собой некоторую полуплоскость с соответствующими границами-прямыми:
Подставив в каждое неравенство системы ограничений точку (0,0), оп-ределяем соответствующую полуплоскость. Таким образом область допус-тимых решений АВС (рисунок 2.1).
Рисунок 2.1
Выразим х2 из целевой функции
Пусть , тогда , где k – угловой коэффициент. Выясним знак k по отношению к F:
Так как , то функция возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рисунок 2.1) целевая функция F будет иметь наименьшее значение (гло-бальный минимум).
Найдем координаты точки C, решая систему:
Итак средняя себестоимость равна 2,25 тыс. руб.
Ответ: предприятию следует выпускать 3 изделия А и 1 изделие В. при этом средняя себестоимость будет минимальной и равной 2,25 тыс. руб.
Пример 2.3
Дана задача нелинейного программирования , при ограниче-ниях . Найти условный экстремум с использованием метода множителей Лагранжа.
Решение: Составим функцию Лагранжа:
Найдем частные производные функции F по х1, х2, , приравняем их к нулю, получим систему уравнений:
Давая х1 значения больше и меньше 1000, находим L и из определения экстремума функции, получаем:
х1>1000, х1=1100, х2=300, L=11002+3002 = 1300000>L=1250000
х1<1000, х1=900, х2=700, L=9002+7002 = 1300000>L=1250000
при х1=1000, х2=500 функция L достигает минимума.
Ответ: (1000,500) – точка минимума функции L, Lmin=1250000
Пример 2.4
Телевизионная фирма планирует создание кабельной сети для обслужи-вания 5 районов – новостроек. Числа на ребрах указывают длину кабеля (ри-сунок 2.2.) Узел 1 – телевизионный центр. Отсутствие ребра между двумя уз-лами означает, что соединение соответствующих новостроек либо связано с большими затратами, либо невозможно. Найти такое соединение кабелем районов – новостроек, чтобы длина его была минимальной.
Рисунок 2.2
Решение: начинаем с любого узла и соединяем его с ближайшим узлом сети, например узел 1 и узел 2. Соединенные два узла 1и 2 образуют связное множество, а остальные – несвязное. Далее в несвязном множестве выберем узел, который расположен ближе других к любому из узлов связного множе-ства, например узел 5. скорректируем связное и несвязное множества и бу-дем повторять процесс до тех пор, пока в связное множество не попадут все узлы сети. В случае одинаково удаленных узлов выберем любой из них, что указывает на неоднозначность (альтернативность «минимального дерева-остова»). Таким образом минимальная длина кабеля равна 1+3+4+3+5=16 (рисунок 2. 3).
Рисунок 2. 3
Ответ: минимальное соединение имеет длину 16.
Пример 2. 5
Торговая фирма разработала несколько вариантов плана продажи това-ров на предстоящей ярмарке с учетом меняющейся конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены в таблице 2.4. Определить оптимальный план продажи товаров.
Решение:
Обозначим: вероятность применения торговой фирмой стратегии П1 че-рез х1, стратегии П2 - х2, стратегии П3 – х3,вероятность использования стра-тегии К1 через y1, стратегии К2 – у2, стратегии К3 - у3.
Таблица 2. 4
План продаж Величина дохода, ден. ед.
К1 К2 К3
П1 8 4 2
П2 2 8 4
П3 1 2 8
Для первого игрока (торговой фирмы) математическая модель задачи имеет вид:
при ограничениях
Для второго игрока (конъюнктуры рынка и спроса покупателей) матема-тическая модель задачи имеет вид:
при ограничениях
Найдем оптимальное решение задачи для второго игрока симплексным методом. Приведем систему ограничений к каноническому виду добавив по-ложительные переменные y4, y5, y6. Тогда система уравнений – ограничений имеет вид:
При этом
Составим симплексную таблицу:
Базис
1 1 1 0 0 0
y1 y2 y3 y4 y5 y6
0 1 8 4 2 1 0 0 /8
0 1 2 3 4 0 1 0
0 1 1 2 8 0 0 1
0 -1 -1 -1 0 0 0
0 1/8 1 1/2 1/4 1/8 0 0
0 1 2 8 4 0 1 0
0 1 1 2 8 0 0 1
0 -1 -1 -1 0 0 0
1 1/8 1 1/2 ¼ 1/8 0 0
0 ¾ 0 7 7/2 -1/4 1 0
0 7/8 0 3/2 31/4 -1/8 0 1 *4/31
1/8 0 -1/2 -3/4 1/8 0 0
1 3/31 1 14/31 0 4/31 0 -1/31
0 11/31 0 196/31 0 -6/31 1 -14/31 *31/196
1 7/62 0 6/31 1 -1/62 0 4/31
13/62 0 -11/31 0 7/62 0 3/31
1 3/31 1 14/31 0 4/31 0 -1/31
0 11/196 0 1 0 -3/98 31/196 -1/14
1 7/62 0 6/31 1 1/62 0 4/31
13/62 0 -11/31 0 7/62 0 3/31
1 1/14 1 0 0 1/7 -1/14 0
1 11/196 0 1 0 -3/98 31/196 -1/14
1 5/49 0 0 1 -1/98 -3/98 1/7
45/196 0 0 0 5/49 11/196 1/14
Так как исследуем функцию на max, то в индексной строке не должно быть отрицательных оценок. Выберем в качестве разрешающего столбец у1, так как min1/8; 1/2; 1=1/8, то строка - разрешающая. Ее делим на 8 и переписываем в следующую таблицу без изменения. В разрушающем столб-це все элементы, кроме разрешающего заменяем на нули. Остальные элемен-ты таблицы пересчитываем по правилу прямоугольника:
.
Например, а22=8: и т.д. Далее переходим к новому ба-зису, так как опять есть в индексной строке отрицательные оценки. В качест-ве разрешающего столбца выбираем , так как его оценка < 0 и по модулю больше оценки . Строка разрешающая , так как min1/81/4; 3/47/2; 7/831/4=7/62 и т.д. Процесс продолжается до тех пор, пока в индексной строке все оценки не будут положительными. При этом решение должно быть допустимым, т.е. состоит из положительных переменных.
Из таблицы следует, что
Цена игры
Так как , то
Оптимальная стратегия второго игрока: .
Стратегию первого игрока найдем из последней симплексной таблицы, использую метод соответствия переменных исходной и двойственной задач. Получим:
Таким образом, торговая фирма на ярмарке должна придерживаться стратегии , при этом она получит доход не менее V=196/45 ден. ед.
Пример 2. 6
В ОТК цеха работают три контролера. Если деталь поступает в ОТК, ко-гда все контролеры заняты обслуживанием ранее поступившей деталей, то она проходит непроверенной. Среднее число деталей, поступающих в ОТК в течении часа, равно 24, среднее время, затрачиваемое одним контролером на обслуживание одной детали, равно 5 минут. Определить вероятность того, что деталь пройдет ОТК необслуженной, насколько загружены контролеры и сколько их необходимо поставить, чтобы
Решение:
По условию задачи интенсивность потока заявок – среднее число дета-лей, поступающих на ОТК в течении часа: =24дет/ч=0,4 дет/мин.
Среднее время обслуживания - три контролера. Тогда интенсивность потока обслуживания, т.е. среднее число заявок, обслуживае-мых в единицу времени: . Интенсивность нагрузки:
1. Вероятность простоя каналов обслуживания (к=0), когда нет об-служивания:
2. Вероятность отказа в обслуживании, когда поступающая на об-служивание заявка найдет все каналы занятыми (к=n)
3. Вероятность обслуживания:
4. Среднее число занятых обслуживанием каналов:
5. Доля каналов, занятых обслуживанием:
6. Абсолютная пропускная способность СМО:
При n=3 Робс=0,79
Произведем аналогичные расчеты при n=4, получим
1.
2.
3.
Так как , то произведем расчеты для n=5. по-лучим:
1.
2.
3.
Ответ: вероятность того, что при n=3 деталь пройдет ОТК не обслужен-ной, составляет 21%, и контролеры будут заняты обслуживанием на 53%. Чтобы обеспечить вероятность обслуживания более 95%, необходимо не ме-нее 5 контролеров.
3. Задание для самостоятельной работы
Тема: «Динамическое программирование»
1. Определить оптимальный цикл замены оборудования при следующих исходных данных S(t)=0, f(t)=r(t)-u(t),
N 1 2 3 4 5 6 7 8 9
f(t) а1 а2 а3 а4 а5 а6 а7 а8 а9
Значения коэффициентов условия задачи
Вариант Значения
Р а1 а2 а3 а4 а5 а6 а7 а8 а9
1 12 12 10 8 6 4 2 0 0 0
2 10 10 9 8 7 5 3 1 0 0
3 14 14 12 10 8 6 4 1 0 0
4 11 11 10 9 7 5 3 0 0 0
5 13 13 12 11 9 7 4 1 0 0
6 15 15 14 12 10 8 6 3 0 0
7 16 16 15 13 11 8 5 2 0 0
8 15 15 14 13 11 9 7 4 1 0
9 14 14 13 12 10 7 4 1 0 0
10 11 11 10 9 8 7 5 3 1 0
11 11 11 10 8 6 4 3 1 0 0
12 14 14 9 10 7 5 2 0 0 0
13 15 15 12 8 8 5 3 1 1 0
14 16 16 10 9 7 6 4 3 0 0
15 15 15 12 11 10 8 4 1 0 0
16 13 13 15 12 9 7 3 4 0 0
17 111 11 14 13 11 8 5 2 1 0
18 14 15 14 12 10 9 6 3 0 0
19 10 10 13 13 11 7 7 1 0 0
20 12 12 10 9 8 7 7 0 1 0
Тема «Нелинейное программирование».
1 Решить задачу дробно-линейного программирования
Для производства двух видов изделий А и В предприятие использует три типа технологического оборудования. Каждое из изделий должно пройти об-работку на данном типе оборудования. Время обработки каждого из изделий, затраты, связанные с производством одного изделия, даны в таблице. Обору-дование 1 и 3 типов предприятие может использовать не менее в1 и в3 часов соответственно, оборудование 2 типа - не более в2 часов. Определить, сколь-ко изделий следует изготовить предприятию, чтобы средняя себестоимость одного изделия была минимальной.
Тип оборудования Затраты времени на обработку одного изделия, ч.
А В
1 а11 а12
2 а21 а22
3 а31 а32
Затраты на производст-во одного изделия, т.р. с1 с2
Значение коэффициентов условия задачи.
Вариант Значения
с1 с2 а11 а12 в1 а21 а22 в2 а31 а32 в3
1 1 2 12 4 48 10 5 50 1 1 6
2 3 1 12 1 12 10 10 40 5 8 30
3 1 4 7 4 28 5 4 45 2 11 22
4 4 2 8 3 24 1 1 5 2 8 16
5 1 3 8 6 48 6 9 54 8 1 8
6 2 4 8 10 80 12 6 72 3 14 42
7 5 3 4 8 32 9 5 45 10 2 20
8 3 4 11 1 11 4 6 24 1 10 10
9 2 5 16 4 32 7 5 35 2 7 14
10 5 2 12 6 70 8 9 72 1 10 12
11 3 2 12 1 12 10 5 40 5 8 30
12 1 1 12 4 48 10 4 50 1 1 6
13 4 3 8 6 28 6 10 45 8 1 16
14 1 2 7 4 24 5 1 5 2 11 22
15 4 3 8 3 48 1 9 54 2 8 8
16 2 4 11 10 32 9 5 72 10 2 42
17 5 3 4 1 80 12 6 45 3 10 10
18 3 4 8 8 11 4 5 24 1 7 20
19 5 2 12 6 32 8 9 35 1 14 12
20 2 5 16 4 70 7 5 72 2 10 14
2. Дана задача нелинейного программирования , при ограниче-нии . Найти условный экстремум с использованием метода множителей Лагранжа.
Значение коэффициентов условия задачи.
Вариант Значения
а а11 а12 в1
1 1 1 1 1
2 2 2 3 4
3 1 3 1 2
4 3 2 1 3
5 -1 -1 3 2
6 -2 1 -2 2
7 -3 3 -1 3
8 1 1 3
9 2 1 3 2
10 -1 3 -3 2
11 1 1 1 1
12 3 3 1 3
13 1 2 3 4
14 2 3 1 2
15 -1 -1 -1 3
16 -3 3 2 2
17 -2 1 -3 2
18 1 3 3 2
19 2 1 -3 1
20 -1 1 3 2
Тема: «Сетевые модели»
Районной администрацией принято решение о газификации одного из наибольших сел района, имеющего 10 жилых жомов. расположение домов указано на рисунке 4.1. Числа в кружках обозначают условный номер дома. Узел 11 является газо – понижающей станцией. Разработать такой план гази-фикации села, чтобы общая длина трубопровода была наименьшей.
Рисунок 4.1
Значения коэффициентов условия задачи
Ва-ри-ант Значения
а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 а15 а16 а17
1 200 60 250 110 150 300 80 350 120 400 210 40 120 30 70 20 550
2 150 70 270 130 140 320 90 370 130 440 190 50 130 40 50 40 580
3 220 50 290 120 110 310 70 360 140 420 200 30 150 50 40 30 570
4 150 40 220 140 100 350 100 390 190 430 210 60 120 60 60 50 590
5 170 80 230 100 120 330 60 340 150 470 220 80 100 30 30 30 530
6 190 70 240 150 130 360 50 350 180 450 180 70 170 50 80 70 520
7 230 30 280 200 160 340 70 330 170 410 230 90 160 80 70 20 560
8 160 100 250 170 150 310 40 390 160 460 170 80 70 70 90 60 630
9 210 90 260 190 140 290 50 360 140 440 180 50 90 90 40 40 600
10 280 40 300 180 110 370 90 400 160 470 190 40 110 40 50 50 610
11 220 60 290 110 110 320 80 360 120 420 200 40 150 30 50 20 550
12 180 70 250 130 140 300 90 350 130 440 210 50 120 40 70 40 580
13 200 50 270 120 150 310 70 370 140 400 190 30 130 50 40 30 570
14 150 70 220 140 130 360 80 380 150 430 180 60 100 60 30 70 590
15 190 40 230 150 100 350 90 370 190 470 210 80 120 30 60 50 530
16 170 80 240 100 120 360 70 350 180 450 220 70 170 50 80 30 520
17 220 30 280 180 160 340 90 400 170 410 230 90 160 40 50 20 560
18 230 100 260 200 150 310 40 330 160 460 170 80 70 92 70 60 630
19 240 90 250 170 110 290 70 390 140 440 180 50 90 70 90 40 600
20 210 40 300 190 140 370 50 360 160 470 190 40 110 80 40 50 610
Тема: «Теория игр».
Торговая фирма разработала несколько вариантов плана продаж товаров на предстоящей ярмарке с учетом конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены в таблице. Определить
1) Оптимальную стратегию фирмы в продаже товаров на ярмарке.
2) Если риск существует (вероятность реализации плана П1 – в%, П2 – с%, П3 – d%), то какую стратегию фирме следует считать оптималь-ной ?
План продаж Величина дохода, ден. ед.
Д1 Д2 Д3
П1 а11 а12 а13
П2 а11 а22 а23
П3 а31 а32 а33
Значения коэффициентов условия задачи
Вари-ант Значения
а11 а12 а13 а21 а22 а23 а31 а32 а33 в% с% d%
1 3 5 1 1 4 3 4 2 5 40 30 30
2 2 4 2 1 3 5 4 2 -3 30 20 50
3 3 4 2 1 2 4 5 3 1 30 45 25
4 4 3 5 6 2 3 2 5 -2 35 25 40
5 3 2 4 5 3 2 2 5 -5 45 35 20
6 5 3 -4 -2 5 2 1 1 3 20 40 40
7 2 3 3 4 2 1 3 2 4 30 35 35
8 2 1 3 4 3 1 1 4 2 25 25 50
9 3 2 4 5 3 2 2 5 5 40 15 45
10 2 4 3 3 1 4 2 3 3 15 35 50
11 2 4 2 1 3 3 5 2 5 40 30 30
12 3 4 2 6 4 5 4 3 -3 30 20 50
13 2 5 1 1 2 4 4 2 1 30 45 25
14 5 3 4 5 2 3 2 5 -2 35 25 40
15 4 2 -4 -2 3 2 1 1 -5 45 35 20
16 3 3 5 4 5 2 2 5 3 20 40 40
17 3 3 3 5 3 1 3 2 4 30 35 35
18 2 1 4 3 2 1 1 4 2 25 25 50
19 3 2 3 4 3 2 2 3 5 40 15 45
20 3 4 3 3 1 4 2 5 3 15 35 50
Тема: «Система массового обслуживания»
1. На контроль готовой продукции фирмы осуществляют А контролеров. Если изделие поступает на контроль, когда все контролеры заняты проверкой готовых изделий, то оно остается непроверенным. Среднее число изделий, выпускаемых фирмой составляет В изд/час, среднее время на проверку одно-го изделия – С мин. Определить вероятность того, что изделие пройдет про-верку, насколько загружены контролеры и сколько их необходимо поставить, чтобы .
Значение коэффициентов условия задачи.
Вариант Значения
А В С Д
1 3 20 7 0,97
2 4 22 6 0,98
3 5 25 5 0,96
4 6 30 8 0,97
5 3 18 6 0,98
6 5 28 4 0,96
7 4 24 3 0,98
8 2 14 5 0,97
9 3 16 6 0,96
10 5 26 7 0,98
11 5 20 5 0,97
12 4 22 7 0,98
13 3 25 6 0,96
14 3 30 4 0,97
15 6 18 8 0,98
16 5 28 6 0,96
17 5 24 5 0,98
18 4 14 7 0,97
19 2 16 3 0,96
20 3 26 6 0,98
Литература
1. Красс М.С., Б.П. Чупрынов Основы математики и ее приложения в экономическом образовании. – М.: Дело, 2001. – 688с.
2. Исследования операций в экономике / под ред. Н. Ш. Кремера - М.: Банки и биржи, ЮНИТИ, 1999. – 407с.
