Применение оптимизационных методов к решению экономических задач

    Для простейшего потока вероятность p_i(t) поступления в СМО ровно i заявок за время t вычисляется по формуле:

                  

  

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

    Функция распределения F(t) случайного интервала времени T между двумя последовательными заявками по определению равна . Но , где – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t, т.е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (6) при i = 0. Таким образом:

    

     

    

            

   СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

     – число каналов в СМО;

     – интенсивность поступления в СМО заявок;

     – интенсивность обслуживания заявок;

     – коэффициент загрузки СМО;

     – число мест в очереди;

     – вероятность отказа в обслуживании поступившей в СМО заявки;

     – вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

   При этом:

   

  

   А – среднее число заявок, обслуживаемых в СМО в единицу времени (абсолютная пропускная способность СМО)

                                                                     – среднее число заявок, находящихся в СМО

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

   

, 

   где – вероятность нахождения системы в S_k состоянии.

     – коэффициент занятости каналов

     – среднее время ожидания заявки в очереди

     – интенсивность ухода заявок из очереди

     – среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

   

  

   Здесь – вероятность нахождения в очереди i заявок;

     – среднее время пребывания заявки с СМО

     – среднее время пребывания заявки в очереди

   Для открытых СМО справедливы соотношения:

   

  

    

        

   Эти соотношения называются формулами  Литтла и применяются только для  стационарных потоков заявок и обслуживания.

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

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

    1.5 Параметрическое программирование

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

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

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

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

    а) постоянной – стоимость продукции  на момент изготовления;

    б) переменной, зависящей от срока хранения продукции.

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

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

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

    

    при условиях

    

    где c′_j, c′′_j, a_ij, b_i – заданные постоянные числа.

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

    

    где a, β – промежуток изменения значений параметра t (—∞, +∞).

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

    В результате при данном значении либо найдем оптимальный план задачи, либо установим ее неразрешимость.

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

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

    Процесс нахождения решения задачи включает следующие этапы:

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

    2. Определяют множество значений  параметра, для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения.

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

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

    II Практические вопросы

    2.1 Применение параметрического программирования к решению экономических задач

    Пусть предприятие изготавливает два  вида продукции - А, В, для которых использует три вида ресурсов. Известны нормы расхода и запасы каждого вида (табл. 1).

    Из  анализа спроса установлено, что цена единицы продукции для изделия А может изменяться от 2 до 12  тыс. руб., а для изделия В – от 3 до 13  тыс. руб., причем эти изменения определяются соотношениями:

    c₁ = 2 + t, c₂ = 13 – t, где 0 ≤ t ≤ 10.

    Таблица 1

      

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

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

      

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

    После этого, полагая t = 0, строим целевую функцию 2х₁ + 13х₂ = 26 (число 26 – произвольно) и вектор c = (2; 13). Передвигая эту прямую в направлении вектора c, можно установить последнюю ее точку с многоугольником решений OABCD, т. е. точку А(0; 11).

      

    Рис. 2

    Следовательно, задача при t = 0 имеет оптимальный план x₀^* = (0; 11). Это означает, что если цена изделия А равна 2 + 0 = 2  тыс. руб., а цена изделия В 13 – 0 = 13  тыс. руб., то в оптимальном плане производство изделий А не предусматривается, а изделий В требуется изготовить в количестве 11 ед. и максимальная выручка составит maх F = 143 тыс. руб..

    Положим теперь t = 2 и построим прямую целевой  функции (2 + 2) х₁ + (13 – 2) х₂ = = 4х₁ + 11х₂ = 44 (число 44 – произвольно) и вектор (4; 11). Передвигая эту прямую в направлении вектора , устанавливаем последнюю точку многоугольника решений – ту же точку А (0; 11).

    Следовательно, при t = 2 задача имеет тот же оптимальный план x₀^* = (0; 11), означающий, что при цене изделия А – 4 тыс. руб., а изделия В – 11 тыс. руб. требуется изготовить только 11 ед. изделия В, которые обеспечат максимум выручки maх F = 11 * 11 = 121 тыс. руб.

    Данный  план производства будет оставаться оптимальным для всякого значения t, пока прямая целевой функции (2 + t)х₁ + (13 – t) х₂ = L не станет параллельной прямой 2х₁ + 2х₂ = 22. Это произойдет, когда

    

    т. е. при t = 5,5 координаты любой точки отрезка АВ дают оптимальный план задачи.

    Таким образом, для всякого 0 ≤ t ≤ 5,5 задача имеет оптимальный план x₀^* = (0; 11), при котором значение целевой функции maх F = (2 + t) х₁ + (13-t)х₂ = (2 + t) × 0 + (13– t) × 11 = 143-11t.

    При значениях параметра t, больших 5,5, например t = 6, прямая целевой функции: 8х₁ + 7х₂ = 56 (56 – произвольно), которой соответствует вектор c₂(8; 7); в направлении движения по этому вектору последняя точка В (1;10), т. е. при цене А - 2 + 6 = 8 тыс. руб., при цене В - 13 – 6 = 7 тыс. руб. x₁⁰ = 1; x₂⁰ = 10; maх F = 78 тыс. руб.