Системное програмирование

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

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

Это уже  другая, не чисто математическая задача (недаром в ее формулировке сделана  оговорка "по возможности"). Наличие  неопределенных факторов переводит  эту задачу в новое качество: она  превращается в задачу о выборе решений  в условиях неопределенности.

Приведем  примеры.

Пример 1.7.1

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

Пример 1.7.2

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

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

Пример 1.7.3

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

Пример 1.7.4

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

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

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

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

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

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

Пример 1.7.5

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

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

Но дело в том, что время ожидания врача  отдельными больными не суммируется: слишком  долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием  другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности  добавочными требованиями, чтобы  фактическое время ожидания врача  было не больше какого предельного  значения f₀. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F≤ f₀, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F≤ f₀ было практически достоверным. Пусть k=0,995 и потребуем, чтобы вероятность P(F≤ f₀ ) ≥ k.

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

Особенно  осторожными надо быть с "оптимизацией в среднем", когда речь идет об единичной операции.

Кроме рассмотренных выше, бывают задачи, когда неизвестные факторы не могут быть изучены и описаны статистическими методами. Это бывает в двух случаях:

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

Пример 1.7.6

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

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

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

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

Пример 1.7.7

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

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

Можно поступить следующим  образом. Задаться каким  более или менее  правдоподобным значением  вероятностного параметра  и решить данную задачу, как обычную детерминированную  задачу. Но полученное решение может  и не быть оптимальным, просто мы получим  некоторое компромиссное  решение.

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

Вариант 13.

Методы  математического программирования

Ранее уже упоминалось о самых простых - детерминированных и одноцелевых задачах, исследованием которых занимается математическое программирование. Слово программирование в данном случае означает "планирование".

К математическому  программированию относится:

1. Линейное программирование: состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные;
2. Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями;
3. Особым случаем в задачах линейного и нелинейного программирования является случай, когда на оптимальные решения накладывается условие целочисленности. Такие задачи относятся к целочисленному программированию;
4. Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;
5. Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.
6. Стохастическое линейное программирование
7. Бывает много практических ситуаций, когда коэффициенты ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.
8. Геометрическое программирование
9. Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
10. Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
11. Теория игр пытается математически объяснить явления возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.

 

Вариант 14.

Общая и основная задачи линейного программирования

Общая и основная задачи линейного программирования

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

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

                         (10)

при условиях                                                     (i = 1,k)     (11)

   (i = k+1, m )              (12)

   (j=1,l; l£ n)                           (13)

где , , —заданные постоянные величины и k £ m.

   Функция (10) называется целевой функцией (или  линейной формой) задачи (10) —(13), а условия (11)— (13) — ограничениями данной задачи.

  Стандартной (или симметричной) задачей линейного  программирования называется задача, которая состоит в определении  максимального значения функции (10) при выполнении условий (11) и (13), где  k = m и l = n.

   Канонической (или основной), задачей линейного  программирования называется задача, которая состоит в определении  максимального значения функции (10) при выполнении условий (12) и (13), где   k = 0 и l = n.

   Совокупность  чисел Х= (х₁, х₂,..., х_n), удовлетворяющих ограничениям задачи (11) — (13), называется допустимым решением (или планом).

  План  Х*=(х₁*, x₂*,… х_n*), при котором целевая функция задачи (10) принимает свое максимальное (минимальное) значение, называется оптимальным.

   Значение  целевой функции (10) при плане  X будем обозначать через F(X). Следовательно, X* — оптимальный план задачи, если для любого X выполняется неравенство F(X) £ F(X*), соответственно F (X) ³ F(X*).