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

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

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

Пусть в m пунктах находятся соответственно a₁, a₂, ..., a_m  единиц однородного груза, который должен быть доставлен n потребителям в количествах b₁, b₂, ..., b_n.. заданы стоимости перевозок груза cij из i-го склада j-му потребителю.

Обозначим через x_ij>0 (i=1, ...,m; j=1, ...,n) количество единиц груза, перевозимого от i-го склада j-му потребителю.

 

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

 

 

 

 

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

 

 

Порядок решения транспортных задач

Транспортные задачи обычно решаются в 2 этапа:

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

• Метод «северо-западного» угла.

• Метод наименьшего элемента.
• Метод Фогеля. Позволяет найти решение, не требующее оптимизации!

2. Второй этап - проверка оптимальности найденного на первом этапе решения. Обычно используют:

• Метод потенциалов.
• Метод Фогеля - можно также считать способом поиска оптимального решения.

 

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

 

Планирование  производства

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

1. Целью является максимизация  прибыли.

2. Задача решается в общем  виде, поэтому для определения  параметров введем условные обозначения:

п — число различных видов изделий;

т — число различных типов ресурсов;

b_i — запас ресурса /-го типа, / = \,т;

a_ij — количество  ресурсов  i-го  типа  для  изготовления  одного изделия j-го вида, i = 1,...,m; j = 1,...,n;

P_j— прибыль от реализации одного изделия у'-го вида.

3. Управляющие переменные x_j ,j = 1,...,n —число изделий j-ro вида.

4. Ограничения задачи — это  ограничения по ресурсам и  условия неотрицательности управляющих  переменных.

Таким образом, можно построить  математическую модель.

                                                                         (5)

 

 

                                                                          (6)

 

 

 

 

(5 - 6) — линейная математическая  модель поставленной задачи. В  результате ее расчета определяют  оптимальный план производства, т.е. количество изделий каждого  вида, которые надо изготовить  так, чтобы при этом была  максимальна прибыль (5) и не  был превышен запас ресурсов (6).

  Расчет оптимальной загрузки  оборудования

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

1. Целью является минимизация  себестоимости.

2. Параметры:

т — номенклатура, т.е. число различных видов продукции в производственном заказе;

b_j — число единиц продукции i-го вида, i=1,...,m;

п — число единиц оборудования;

T_j —фонд времени работы оборудования j-го типа, j = 1,...,n;

а_ij — производительность оборудования j-го типа по производству изделий i-го вида, i=1,...,m; j=1,...,n;

c_ij — себестоимость изготовления единицы продукции i-го вида на оборудовании j-го типа, i=1,...,m; j=1,...,n.

3. Управляющие переменные  x_ij, i=1,...,m; j=1,...,n —это время, в течение которого оборудование j-го типа занято изготовлением продукции i-го вид

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

   (9)

 

(10)

Критерий оптимальности задается функцией

 

 

 

где С — суммарная себестоимость.

(9-11) — линейная математическая  модель задачи. Она содержит т*п неизвестных (управляющих переменных) и т+п ограничений, не считая условий (11). После расчета модели определяется оптимальная загрузка оборудования, т.е. время в течение которого оборудование каждого типа занято изготовлением продукции каждого вида.

  Составление плана реализации  товара

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

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

1. Цель — максимизации прибыли.

2. Параметры:

п    - число различных видов реализуемых товаров;

т — число разных видов средств;

b_i — запас средств i-го вида, i = 1,...,т;

a_ij - число средств i-го вида, используемых для реализации единицы товара j-го вида, i=1,...,m, j = 1,...,n;

P_j — прибыль от реализации единицы товара j-го вида, j = 1,...,п.

3. Управляющие переменные x_j , j = 1,..., n — количество реализуемого товара j-го вида;

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

 

(17

 

 

 

5. Критерий оптимальности определяется  по формуле:

где Р - суммарная прибыль.

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

13.  Постановка задачи  динамического программирования.

 

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

Дп – это метод оптимизации  многошаговых или многоэтапных процессов, критерий эффективности которых  обладает свойством:

где W – показатель эффективности задачи в целом,

j_i  (i=1,…,m) – показатели эффективности отдельных шагов задачи.

Переменная x_i, от которой зависит управление на i-шаге (i=1,…,m) и, следовательно, выигрыш в целом, называется шаговым управлением.

Управлением процессом в целом (х) называется последовательность шаговых  управлений х=(х₁,…,х_m).

Оптимальное управление х^* - это значение управления х, при котором значение W(x^*) является максимальным (или минимальным, если требуется уменьшить проигрыш): W^*=W(x^*)=max{W(x)}, xÎX, где Х – область допустимых управлений.

Оптимальное управление определяется последовательностью шаговых управлений: х*=(х₁^*,…,х_m^*).

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

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

s – состояние процесса.

S_i – множество возможных состояний процесса перед i-м шагом.

W_i – выигрыш с i-го шага до конца процесса, (i=1,…,m).

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

1. Разбиение задачи на шаги (этапы). Шаг не должен быть мелким (чтобы не увеличивать число расчетов) и не д.б. слишком большим (чтобы не усложнять проц<span class="Normal__Char" style=" font