Файл: Лекции_по_дисциплине.pdf

Компьютерное моделирование

9.Рассчитайте модель автобусного маршрута с n остановками.

103

Компьютерное моделирование

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

Обозначим число выпускаемых за день мотоциклов X, велосипедов - у. Пусть Т1 -время (в часах), уходящее на производство одного мотоцикла, а т2 - одного велосипеда. Из условия задачи следует, что T1x+T2y 24. Если завод работает круглосуточно, то, очевидно, при одновременном выпуске обоих изделий

Еще одно условие – ограниченная емкость склада: x+y 70.

Обозначим цену мотоцикла - а1, велосипеда – а2. По условию а1=2а2. Общая цена продукции: S=a1x+a2y=2a2x+a2y=a2 (2x+y). Поскольку а2 – заданная положительная величина, то наибольшего значения следует добиваться от величины f=2x+y. Учитывая все условия, имеем: среди неотрица-

вует максимуму функции f=2x+y. Решим задачу геометрически. Построим на плоскости область, соответствующую неравенствам и условию не отрицательности х и у, а также семейство прямых,. Удовлетворяющих уравнению f=2x+y=c (с разными с). Координаты точки Р(10, 60) – точки касания – искомый оптимальный план производства.

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

105

Тарова Инна Николаевна

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

Решение, удовлетворяющее условиям задачи и соответствующее намеченной цели, называется оптимальным планом. Нелинейное программиро-

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

Z1(x1, x2,...,xn) 0;

Z 2(x1, x2,...,xn) 0;

.................... (1.1) где Z1,Z2,…Zm – соответствующие функ-

Zm(x1, x2,...,xn) 0

при xi 0.

ции, характеризующие условие решения поставленной задачи (ограничения), Xi – искомые величины, содержащие решение задачи. Целевая функция задается в виде: y f (x1, x2,...xn) (1.2). Причем хотя бы одна из

функций Z1,Z2,…Zm – нелинейная.

Методами нелинейного программирования решаются задачи распределения неоднородных ресурсов. Пусть имеется m разнородных ресурсов, которые предлагается реализовать для бизнеса в n регионах страны. Известны оценочные возможности (вероятности) начать бизнес в j-том регионе (Рj), а также эффективности использования I-го ресурса в n-м регионе (Wij). Распределение ресурсов по регионам характеризуется так называемым параметром управления (Hij):

106

Компьютерное моделирование

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

n

Должно выполняться также ограничение Hij 1, i 1,2,..., m .

j 1

Это ограничение означает, что каждый из m ресурсов обязательно должен назначаться в какой-либо из регионов.

Динамическое программирование (планирование) служит для вы-

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

управляемая операция (целенаправленное действие), распадающаяся (есте-

ственно или искусственно) на m шагов – этапов. На каждом шаге осуществляется распределение и перераспределение участвующих в операции с целью улучшения ее результата в целом. Эти распределения в динамическом программировании называются управлениями и обозначаются буквой U. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления W(U). При этом W(U) зависит от всей совокупности управлений на каждом шаге операции: W=W (U)=W (U1,U2,…,Um). Управление, при котором показатель W достигает максимума, называется оптимальным управлением. Оптимальное управление обозначается буквой U. Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений: U=(U1,U2,…,Um). Задача динамического программирования – определить оптимальное управление на каждом шаге Ui(I=1,2,…,m) и оптимальное управление всей операцией в целом. В большинстве практических задач принимается, что показатель эффективности операции W в целом пред-

ставляет собой сумму эффективности действий на всех этапах операции:

107

Тарова Инна Николаевна

m

W Wi , где Wi – эффективность операции на I-том шаге. При этом в

i 1

m

случае оптимального управления W max Wi . Существо решения за-

i 1

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

1) оптимизация производится методом последовательных приближений (итераций) в два круга; вначале от последнего шага операции к первому, а затем, наоборот – от первого к последнему; 2) на первом круге, идя от последующих шагов к предыдущим, находится условное оптимальное управление; условное оптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивали максимальную эффективность последующего шага, т.е. на каждом шаге имеется такое управление, которое обеспечивает оптимальное продолжение операции; этот принцип выбора управления называется принципом оптимальности; 3) так продолжается до первого шага, но т.к. первый шаг не имеет предыдущего, то полученное для него условное оптимальное управление теряет свой условный характер и становится просто оптимальным условием, которое мы ищем; 4) второй круг оптимизации начинается с первого шага, для которого оптимальное управление известно. Имея для всех шагов после него условные оптимальные управления, мы знаем, что необходимо делать на каждом последующем шаге. Это дает возможность последовательно переходить от условных к оптимальным управлениям для всех последующих шагов, что обеспечивает оптимальность операции в целом.

Пусть имеется m различных грузов, которые необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза W была максимальной. Ценность груза является функцией от грузоподъемности транспортного средства: W=f(G). Известны массы грузов I-го типа Pi и их стоимости Ci. Необходимо загрузить транспортное средство таким обра-

i 1

гружаемых в транспортное средство; Xi выступает в качестве управления (Ui=Xi). Ограничивающими условиями являются:

m

XiPi G, Xi 0,1,2,... . Первое условие требует, чтобы общая масса

i 1

108

Компьютерное моделирование

груза не превышала грузоподъемности транспортного средства, а второе

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

7.2. СИМПЛЕКС-МЕТОД

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

ний (7.1)

и требуется отыскать минимум линейной функции f=c1x1+c2x2+…+cnxn (7.2). Для отыскания произвольного опорного решения приведем (7.1) к виду, в котором некоторые r неизвестных выражены через остальные, а свободные члены неотрицательны (как это сделать - обсудим позднее):

(7.3)

Неизвестные X1,Х2,…,Xn - базисные неизвестные, набор {х1, х2, ..., хr} на-

зывается базисом, а остальные неизвестные (хг+1, хr+2,..., xn} - свободные. Подставляя (7.3) в (7.1), выразим функцию f через свободные неизвестные:

(7.4)

109

Тарова Инна Николаевна

отвечает базису х1, х2, ..., xr т.е. является базисным решением. Допустим для определенности, что мы ищем минимум f . Теперь нужно от данного базиса перейти к другому, с таким расчетом, чтобы значение линейной функции f при этом уменьшилось. Проследим идею симплекс-метода на примере.

Пример I .Дана система ограничений

Требуется минимизировать линейную функцию f= х2 - х3. В качестве свободных переменных выберем х2 и х3. Тогда данная система ограничений преобразуется к виду

Таким образом, базисное решение (3,0,0,1). Так как линейная функция уже записана в свободных неизвестных, то ее значение для данного базисного решения f=0. Для уменьшения этого значения можно уменьшить х2 или увеличить x3. Но х2 в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x3. Первое из уравнений имеет ограничение x3=1 (из условия X1 0), второе - не дает ограничений. Далее, берем x3 = 1, х2 не меняем и получаем новое допустимое решение (0,0,1,3), для которого f=-1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, х4). От предыдущей системы ограничений переходим к новой:

110