Исследование моделей массового обслуживания

т. е. общий  объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу: Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой

                                                     (1)          Суммарное количество продукта, направляемого из каждого пункта

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

, i 1, ..., m              (2)

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

 

, j 1, ..., n              (3)

Объемы перевозок - неотрицательные числа, так как  перевозки из пунктов потребления в пункты производства исключены

  x_ij

0, i 1, ..., m; j 1, ..., n                             (4)

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

Определение 1: всякое неотрицательное решение системы линейных уравнений , j 1, ..., n; , i 1, ..., m, определяемое матрицей X=(x_ij)(i 1, ..., m; j 1, ..., n), называется планом транспортной задачи.

Определение 2: план X*=(x*_ij)(i 1, ..., m; j 1, ..., n), при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Очевидно, общее наличие  груза у поставщиков равно  , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

                      (5)

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

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

, i 1, ..., m.

Введение этого условия  приводит к открытой транспортной модели.

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

        Стандартная задача линейного программирования

или в матричной записи

где    x = (x₁, x₂, x₃, … , x_n), c = (c_1, c_2, c₃, … , c_n), b = (b₁, b₂, b₃, … , b_n),

A = a_ij – матрица коэффициентов.

Вектор  c – называется вектором коэффициентов линейной формы, b – вектором ограничений.

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

или в матричной записи

Основные  вычислительные схемы решения задач  ЛП разработаны именно для канонической задачи.

Общая задача ЛП ставится следующим образом

здесь . Ясно, что стандартная задача получается как частный случай общей при ; каноническая – при .

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

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

1) суммарные запасы превышают суммарные потребности ;

2) суммарные потребности превышают суммарные запасы .

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

Найти минимальное значение линейной функции при ограничениях , i = 1, 2, ..., m, (случай  1) , j = 1, 2, ..., n;    , i = 1, 2, ..., m, (случай 2) , j = 1, 2, ..., n, x_ij ³ 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае 1, когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, потребности которого

b_n+1 =

.

В случае 2, когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого

a_m+1 =

.

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

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

 

3 ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО  ПРОГРАММИРОВАНИЯ

Целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.

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

Иногда задачи целочисленного программирования сводят к методам непрерывного программирования.

Графический метод. При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.  
В системе координат X₁0X₂ находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты. 

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

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

 

4 ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Нелинейное программирование  — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(х₁, х₂,..., х_n), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

h_i(x) ≥ 0,   i=1,2,…,m

переменные x_j (компоненты вектора х) неотрицательны

          x_j ≥ 0

Иногда в формулировке задачи ограничения имеют противоположные знаки неравенств. Учитывая, однако, что если h_i (x) ≥ 0 , то -h_i (x) ≤ 0 , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например φ(x) = 0, то их можно представить в виде пары неравенств φ(x) ≥ 0, -φ(x) ≤ 0, сохранив тем самым типовую формулировку задачи.

В общем виде классификация задач нелинейного программирования, соответствии с видом функции F(x), представлена в таблице 1.

Таблица1 – Классификация задач нелинейного программирования

Вид F(x)	Вид функции ограничений	Число      переменных	Название задачи
Нелинейная	Отсутствуют	1	Безусловная    однопараметрическая оптимизация
Нелинейная	Отсутствуют	Более 1	Безусловная многопараметрическая оптимизация
Нелинейная         или  линейная	Нелинейные или   нелинейные	Более 1	Условная  нелинейная оптимизация

 

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

Общая формулировка нелинейных задач: найти переменные х₁, х₂, …, х_n, удовлетворяющие системе уравнений

Ψ ( х₁ , х₂ , …, х_n ) = b_i , i = 1, 2, …, m

и обращающие в максимум ( минимум ) целевую функцию

Z = f ( х₁ , х₂ , …, х_n )

Пример простой нелинейной задачи: данное предприятие для производства какого-то продукта расходует два средства в количестве х₁ и х₂ соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п., а величины х₁ и х₂ – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства (выраженный в  натуральных или стоимостных  единицах) является функцией затрат производства Z = f (х₁ , х₂). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х₁ и х₂) и от цен этих факторов (c₁ и c₂). Совокупные издержки выражаются формулой b = c₁ х₁ + c₂ х₂. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.

Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2(n≥2). Будем полагать, что функция Z = f( х₁, х₂, …, х_n)=f(X) дважды дифференцируема в точке Х* = (х₁ *, х₂ *, …, х_n*), (Х* € D(f)) и в некоторой ее окрестности.

Если для всех точек Х этой окрестности f (X*) ≥ f (X) или f (X*) ≤ f (X), то говорят, что функция f (X) имеет экстремум в X* (соответственно максимум или минимум).

Точка X* , в которой все частные производные функции Z = f (Х) равны 0, называется стационарной точкой.

Необходимое условие экстремума. Если в точке X* функция Z=f(Х) имеет экстремум, то частные производные функции в этой точке равны 0

f '_x1 (X*) = 0, i = 1, 2, ..., n

Следовательно, точки экстремума функции Z = f (Х) удовлетворяют системе уравнений

 

Для получения достаточных условий  следует определить в стационарной точке знак дифференциала второго  порядка. Дифференциала второго  порядка обозначается d²f (х₁ , х₂ , …, х_n ) f '_x1 (X) найти частную производную по переменной х_j , то получим частную производную второго порядка по переменным х_i , х_j , которая обозначается f ''_{xi, xj} (X). В этом случае

Достаточные условия экстремума двух переменных:

• если Δ > 0 и а₁₁ < 0 (а₂₂ < 0), то в точке Х ⁰ функция имеет максимум:  
  если Δ>0 и а₁₁ >0 (а₂₂ >0), то в точке Х ⁰ – минимум (в этих случаях Х ⁰ = Х*);
• если Δ < 0, то экстремума нет;
• если Δ = 0, то вопрос об экстремуме остается открытым.

 

5 ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

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