Метод искусственного базиса в М задачах

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

Пусть задача записана в виде:

(1)

(2)

Среди векторов условий перейдем к расширенной задаче. Вместо задачи (1) и (2) будем рассматривать следующую задачу:

(3)

(4)

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

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

если в оптимальном плане М задачи не все искусственные переменные равны 0, то задача не имеет допустимых решений;

если М задаче неразрешима, то неразрешима и исходная задача.

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

Замечание: в некоторых случаях не обязательно вводить все искусственные переменные. Если имеется несколько единичных векторов, то нам достаточно ввести искусственные переменные, которые дополняют эти векторы до единичного базиса.

27.

Транспортная задача.

 

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

Пусть имеется m предприятий производящих продукцию с объемами производства соответственно и n предприятий потребителей этой продукции с объемами потребления . И пусть стоимость перевозки единицы продукции от производителя к потребителю равна . Обозначим через количество продукции, которую будем перевозить от производителя к потребителю . Требуется составить такой план перевозок, при котором все запасы будут вывезены, все потребности предприятий будут удовлетворены, стоимость суммарных перевозок будет минимальной.

Математическая модель данной задачи будет следующая. Исследуем на минимум целевую функцию:

(1)

(2)

(3)

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

Стоимость перевозок от производителя к потребителям записывают в виде матрицы тарифов.

Матрица перевозок – план транспортной задачи.

Процесс решения транспортной задачи состоит из трех основных этапов:

построение первоначального допустимого плана;

Допустимый план – план, удовлетворяющий ограничениям (2) и (3)

проверка допустимого плана на оптимальность;

в случае неоптимальности указать процедуру перехода к новому допустимому плану

28.

Основные понятия теории массового обслуживания

Потоки событий

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

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

Примеры:

Поток автопоездов подвозящих древесину на нижний склад; поток отказов того или иного узла.

Различают потоки однородных и неоднородных событий.

Примеры:

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

2.поток машин прибывающих на заправку будет неоднородным, если мы будем

делить их на грузовые и легковые.

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

Пример:

Событие А – в течение времени на нижний склад прибудут три лесовоза.

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

Регулярный поток – поток в котором событие следуют одно за другим через строго определенные промежутки времени.

Пример:

Поток изменения минутной стрелки на часах.

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

Рассмотрим основные свойства потоков:

Ординарность

Ординарный поток событий – поток событий, в котором события появляются поодиночке, а не пачками по 2, 3 и т.д.

Пример:

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

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

Интенсивность

Рассмотрим ординарный поток. Обозначим через случайную величину - число событий появившихся в момент времени от t до . Ряд распределения данной случайной величины будет следующий:

Мы знаем, что интенсивность – предел отношения математического ожидания к промежутку времени, когда последний стремиться к 0. Найдем интенсивность:

(в силу (*)).

Если существует конечный предел , то он является интенсивностью потока.

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

Пример:

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

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

Отсутствие последействия

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

Пример:

Поток прибывающих на разгрузку лесовозов.

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

Стационарность потока

Стационарный поток событий – поток событий, в котором все вероятностные характеристики не меняются со временем.

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

длины участка.

 

 

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

Поток (если он нерегулярный) имеет случайные “сгущения и разряжения”, т.е. они не строго следуют друг за другом. Важно, что “сгущения и разряжения” не имеют закономерного характера.

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

28