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

I раздел. Прикладные вопросы теории вероятностей и математической статистики Лекция №1. Виды случайных величин. Задание дискретной случайной величины.1 Основные формулы комбинаторики2 Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Pn=n!, (удобно рассматривать 0!=1) Например: сколькими способами можно расположить бункерыпитатели АБЗ (щебень, песок, МП)? (не может быть два МП или др.) P=3!=1*2*3=6. В случае если элементы повторяются, то число перестановок Pn(n1, n2, …)=n!/( n1!n2! …), где n1, n2, …число элементов первого, второго и т.д. видов среди n элементов, причем n1+n2+…=n. Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений Anm  n(n  1)(n  2)...(n  m  1) . Например: Сколько можно составить вариантов двухслойного основания дорожной одежды, располагая шестью видами материалов? 3 A62  6  5  30 . Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний C nm  n! . (m!(n  m)!) Например: Сколькими способами можно выбрать из транспортного потока, состоящего из 10-и типоразмеров машин, два автомобиля? C102  10!  45 . (2!(10  2)!) Случайные величины 1 Гмурман В.Е. Теория вероятностей и математическая статистика. Комбинаторика – изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. 3 (А=6*…*(6-2+1)=6*…*5=30) 2 Случайной называют величину, которая в результате испытания примет одно и только одно возможное значение, наперед не известное и зависящее от случайных причин, которые заранее не могут быть учтены. Дискретной (прерывной) называют случайную величину, которая принимает отдельные, изолированные возможные значения с определенными вероятностями. Число возможных значений дискретной случайной величины может быть конечным и бесконечным. Например, число прошедших за час легковых автомобилей при интенсивности движения 100 авт/час, может принимать значение 1, 2, 3, …, 100. Непрерывной называют случайную величину, которая может принимать все значения из некоторого конечного или бесконечного промежутка. Число возможных значений непрерывной случайной величины бесконечно. Например, расстояние, которое пройдет автомобиль при торможении. Каждая из случайных величин принимает то или иное значение с определенной вероятностью. Для задания дискретной случайной величины недостаточно перечислить все возможные ее значения, нужно еще указать их вероятности. Законом распределения дискретной случайной величины называют соответствие между возможными значениями и их вероятностями, например: X x1 x2 … xn p p1 p2 … pn X – случайная величина; P – вероятность; x1, 2, …, n – возможные значения случайной величины; p1, 2, …, n – вероятности выпадения возможных значений. Биноминальное распределение Пусть производится п независимых испытаний, в каждом из которых событие А может появиться либо не появиться. Вероятность наступления события во всех испытаниях постоянна и равна р (следовательно, вероятность непоявления q=1- р). Рассмотрим в качестве дискретной случайной величины X число появлений события А в этих испытаниях. Поставим перед собой задачу: найти закон распределения величины X. Для ее решения требуется определить возможные значения X и их вероятности. Очевидно, событие А в п испытаниях может либо не появиться, либо появиться 1 раз, либо 2 раза, ..., либо п раз. Таким образом, возможные значения X таковы: х1 = 0, x2 = 1, х3 = 2, …, хп+1 = п. Остается найти вероятности этих возможных значений, для чего достаточно воспользоваться формулой Бернулли: (*) Pn (k )  Cnk p k q nk , где k = 0, 1, 2, .... п. Формула (*) и является аналитическим выражением искомого закона распределения. Биномиальным называют распределение вероятностей, определяемое формулой Бернулли. Закон назван «биномиальным» потому, что правую часть равенства (*) можно рассматривать как общий член разложения бинома Ньютона. Распределение Пуассона Пусть производится п независимых испытаний, в каждом из которых вероятность появления события А равна р. Для определения вероятности k появлений события в этих испытаниях используют формулу Бернулли. Если же п велико, то пользуются асимптотической формулой Лапласа. Однако эта формула непригодна, если вероятность события мала (р^0,1). В этих случаях (п велико, р мало) прибегают к асимптотической формуле Пуассона. Итак, поставим перед собой задачу найти вероятность того, что при очень большом числе испытаний, в каждом из которых вероятность события очень мала, событие наступит ровно k раз. Сделаем важное допущение: произведение пр сохраняет постоянное значение, а именно пр = . Это означает, что среднее число появлений события в различных сериях испытаний, т. е. при различных значениях п, остается неизменным. Pn (k )  k e  / k! Эта формула выражает закон распределения Пуассона вероятностей массовых (n велико) и редких (р мало) событий4. Простейший поток событий Потоком событий называют последовательность событий, которые наступают в случайные моменты времени. Примерами потоков служат: проезд транспортных средств через сечение дороги, поступление вызовов на АТС и многие другие. Среди свойств, которыми могут обладать потоки, выделим свойства стационарности, отсутствия последействия и ординарности. Свойство стационарности характеризуется тем, что вероятность появления k событий на любом промежутке времени зависит только от числа k и от длительности t промежутка и не зависит от начала его отсчета; при этом различные промежутки времени предполагаются непересекающимися. Например, вероятности появления k событий на промежутках времени (1; 7), (10; 16), (Т; Т + 6) одинаковой длительности t=6 ед. времени равны между собой. Итак, если поток обладает свойством стационарности, то вероятность появления k событий за промежуток времени длительности t есть функция, зависящая только от k и t. 4 и . Имеются специальные таблицы, пользуясь которыми можно найти Рп(k), зная k Свойство отсутствия последействия характеризуется тем, что вероятность появления k событий на любом промежутке времени не зависит от того, появлялись или не появлялись события в моменты времени, предшествующие началу рассматриваемого промежутка. Таким образом, предыстория потока не сказывается на вероятности появления событий в ближайшем будущем. Итак, если поток обладает свойством отсутствия последействия, то имеет место взаимная независимость появлений того или иного числа событий в непересекающиеся промежутки времени. Свойство ординарности характеризуется тем, что появление двух и более событий за малый промежуток времени практически невозможно. Другими словами, вероятность появления более одного события пренебрежимо мала по сравнению с вероятностью появления только одного события. Итак, если поток обладает свойством ординарности, то за бесконечно малый промежуток времени может появиться не более одного события. Простейшим (пуассоновским) называют поток событий, который обладает свойствами стационарности, отсутствия последействия и ординарности. Интенсивностью потока  называют среднее число событий, которые появляются в единицу времени (напр.: интенсивность движения). Можно доказать, что если постоянная интенсивность потока известна, то вероятность появления k событий простейшего потока за время длительностью t определяется формулой Пуассона. Pt (k )  (t ) k e t / k! Эта формула отражает все свойства простейшего потока5. Формулу Пуассона можно считать математической простейшего потока событий. моделью Пример. Среднее значение интенсивности движения автомобилей в течение часа составляет 2 авт/мин. Найти вероятности того, что за 6 мин проедет 3 автомобиля. Поток автомобилей предполагается простейшим. Решение. По условию,  = 2, t = 6, k = 3. Воспользуемся формулой Пуассона Искомая вероятность того, что за 6 мин проедет 3 автомобиля, Р6(3)= 123е-12/3! = 1440,000006144/6 = 0,000147. Это событие практически невозможно. Геометрическое распределение Пусть производятся независимые испытания, в каждом из которых вероятность появления события А равна р (0<р<1) и, следовательно, вероятность его непоявления q=1-р. Испытания заканчиваются, как только появится событие А. Таким образом, если событие А появилось в k-м испытании, то в предшествующих k-1 испытаниях оно не появлялось. 5 Здесь и далее доказательство опущено. Доказательства приводятся: Гмурман В.Е. Теория вероятностей и математическая статистика. М.: Высшая школа. 2003. – 479 с. Обозначим через X дискретную случайную величину — число испытаний, которые нужно провести до первого появления события А. Очевидно, возможными значениями X являются натуральные числа: х1=1, х2=2, ... Пусть в первых k-1 испытаниях событие А не наступило, а в k-м испытании появилось. Вероятность этого «сложного события», по теореме умножения вероятностей независимых событий, (**) P( X  k )  q k 1  p Полагая k=1, 2, ... в формуле (**), получим геометрическую прогрессию с первым членом р и знаменателем q (0 x1. Следствие: Вероятность того, что случайная величина примет значение, заключенное в интервале (а, b), равна приращению функции распределения на этом интервале: P(a≤X 0). Нормированным называют нормальное распределение с параметрами а = 0 н =1. Нормальная кривая График плотности нормального распределения называют нормальной кривой (кривой Гаусса), Исследуем функцию y 1  2 e ( x  a ) 2 / 2 2 методами дифференциального исчисления. На рисунке изображена нормальная кривая при а = 1 и =2 1. Очевидно, функция определена на всей оси х. 2. При всех значениях х функция принимает положительные значения, т.е. нормальная кривая расположена над осью Ох. 3 Предел функции при неограниченном возрастании (по абсолютной величине) равен нулю: lim y  0 x  т.е. ось Ох служит горизонтальной асимптотой графика. 4. у' = 0 при х = а, у'>0 при х < a, у' < 0 при х > а. Следовательно, при х = а функция имеет максимум равный 1  2 . 5. Разность х - а содержится в аналитическом выражении функции в квадрате, т.е. график функции симметричен относительно прямой x = а. 6. Исследуем функцию на точки перегиба. При х=а+ и х=а- вторая производная равна нулю, а при переходе через эти точки она меняет знак (в обеих этих точках значение функции равно 1 ( 2 e) ). Таким образом, точки графика (а-, 1 ( 2 e) ) и (а+, 1 ( 2 e) ) являются точками перегиба. Влияние параметров нормального распределения на форму нормальной кривой Изменение величины параметра а (математического ожидания) не изменяет формы нормальной кривой, а приводит лишь к ее сдвигу вдоль оси Ох: вправо, если а возрастает, и влево, если а убывает. С возрастанием  максимальная ордината нормальной кривой убывает, а сама кривая становится более пологой, т. е. сжимается к оси Ох; при убывании  нормальная кривая становится более «островершинной» и растягивается в положительном направлении оси Оу. Подчеркнем, что при любых значениях параметров а и  площадь, ограниченная нормальной кривой и осью х, остается равной единице (второе свойство плотности распределения). Заметим, что при а=0 и =1 нормальную кривую 1  x2 / 2  ( x)  e 2 называют нормированной. Вероятность попадания в заданный интервал нормальной случайной величины. Вероятность попадания P в заданный интервал (α; β) нормальной случайной величины X может быть определена с помощью функции Лапласа: ( x)  1 2 x z 2  e dz , где z=(x-a)/. 2   a   a  P(  X   )      .       Оценка отклонения теоретического распределения от нормального. Асимметрия и эксцесс. При изучении распределений, отличных от нормального, возникает необходимость количественно оценить это различие. С этой целью вводят специальные характеристики, в частности асимметрию и эксцесс. Для нормального распределения эти характеристики равны нулю. Поэтому если для изучаемого распределения асимметрия и эксцесс имеют небольшие значения, то можно предположить близость этого распределения к нормальному. Введем понятие центрального момента. Центральным моментом порядка k случайной величины X называют математическое ожидание величины (X-M(X))k. k=M[(X-M(X))k]. 1=0, 2=D(X) Как оценить асимметрию? Можно доказать, что для симметричного распределения (график такого распределения симметричен относительно прямой х = М (Х)) каждый центральный момент нечетного порядка равен нулю. Для несимметричных распределений центральные моменты не четного порядка отличны от нуля. Поэтому любой из этих моментов (кроме момента первого порядка, который равен нулю для любого распределения) может служить для оценки асимметрии; простейший из них - момент третьего порядка. Однако принять этот момент для оценки асимметрии неудобно потому, что его величина зависит от единиц, в которых измеряется случайная величина. Чтобы устранить этот недостаток 3 делят на 3 и, таким образом, получают безразмерную характеристику. Асимметрией теоретического распределения называют отношение центрального момента третьего порядка к кубу среднего квадратического отклонения: As=3/3. Асимметрия положительна, если «длинная часть» кривой распределения расположена справа от математического ожидания; асимметрия отрицательна, если «длинная часть» кривой расположена слева от математического ожидания. Эксцессом теоретического распределения называют характеристику, которая определяется равенством: Ek=(4/4)-3 для нормального распределения (4/4)=3; следовательно, эксцесс равен нулю. Поэтому если эксцесс некоторого распре деления отличен от нуля, то кривая этого распределения отличается от нормальной кривой: если эксцесс положительный, то кривая имеет более высокую и острую вершину чем нормальная кривая; если эксцесс отрицательный то сравниваемая кривая имеет более низкую и плоскую вершину, чем нормальная кривая. При этом предполагается, что нормальное и теоретическое, распределения имеют одинаковые математические ожидания и дисперсии. Определение показательного распределения Показательным (экспоненциальным) называют распределение вероятностей непрерывной случайной величины X, которое описывается плотностью 0 f ( x)   x e при x0 при x0 где  - постоянная положительная величина. Видно, что показательное распределение определяется одним параметром . Функция распределения показательного закона: 0 F ( x)   x 1  e при x0 при x0 Числовые характеристики показательного распределения Математическое ожидание показательного распределения равно обратной величине параметра : M(X)=1/. Дисперсия: D(X) = 1/2. Среднее квадратическое отклонение: (X)=1/ Очевидно, что М(Х)=(Х)=1/, т. е. математическое ожидание и среднее квадратическое отклонение показательного распределения равны между собой. Показательное распределение широко применяется в приложениях, в частности в теории надежности, одним из основных понятий которой является функция надежности. Функция надежности Пусть покрытие автомобильной дороги начинает работать в момент времени t=0, а по истечении времени длительностью t происходят критические разрушения10 дорожной одежды - отказ. Обозначим через Т непрерывную случайную величину - длительность времени безотказной работы покрытия. Если дорога проработала безотказно (до наступления критических разрушений) время, меньшее t, то, следовательно, за время длительностью t наступит отказ. Таким образом, функция распределения F(t)=Р(Тt, равна R(t)=P(T>t)=1-F(t). Функцией надежности R(t) называют функцию, определяющую вероятность безотказной работы элемента за время длительностью t: R(t) = P(T>t). Показательный закон надежности Часто длительность времени безотказной работы элемента имеет показательное распределение, функция распределения которого F(t)=1-e-t. Следовательно, функция надежности в случае показательного распределения времени безотказной работы элемента имеет вид R(t)=1-F(t)=e-t. Показательным законом надежности называют функцию надежности, определяемую равенством R(t)=e-t. где  — интенсивность отказов. Как следует из определения функции надежности, эта формула позволяет найти вероятность безотказной работы элемента на интервале времени длительностью t, если время безотказной работы имеет, показательное распределение. Пример. Время безотказной работы светофора распределено по показательному закону f(t)= 0,08е-0,08t при t≥0 (t — время, мес). Найти вероятность того, что элемент проработает безотказно 3 года. Решение. По условию, постоянная интенсивность отказов =0,08 раз/мес. тогда: R(36)=e-0,0836=e-2,88=0,057 Искомая вероятность того, что светофор проработает безотказно 3 года, приближенно равна 0,06. Если отказы элементов в случайные моменты времени образуют простейший поток, то вероятность того, что за время длительностью t не наступит ни одного отказа: Pt(0)=e-t. Характеристическое свойство показательного закона надежности: вероятность безотказной работы элемента на интервале времени длительностью t не зависит от времени предшествующей работы до начала рассматриваемого интервала, а зависит только от длительности времени t (при заданной интенсивности отказов ). ПРАКТИКА №3 Нормальное распределение. Асимметрия и эксцесс. Шифр: 123456 Исходные данные: v, км/ч N, авт v, км/ч N, авт v, км/ч 48 56 6 64 49 1 57 8 65 50 2 58 10 66 51 2 59 11 67 52 3 60 14 68 53 2 61 19 69 54 4 62 28 70 55 6 63 70 71 vрасч= 60 км/ч a= 0,80 N, авт v, км/ч 75 72 82 73 90 74 99 75 105 76 100 77 98 78 94 79 e= 1,8 N, авт 85 80 70 47 25 10 8 6 v, км/ч 80 81 82 83 84 85 86 87 N, авт 6 7 5 4 1 2 1 Решение: 1. Используя данные расчетной работы №2: a=M(v)=68,48 км/ч, =(v)=5,11 км/ч напишем законы распределения отклонения vi ni 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 ∑= vрасч= pi 1 2 2 3 2 4 6 6 8 10 11 14 19 28 70 75 82 90 99 105 100 98 94 85 80 70 47 25 10 8 6 6 7 5 4 1 2 1 1286 60 0,00000 0,00078 0,00156 0,00156 0,00233 0,00156 0,00311 0,00467 0,00467 0,00622 0,00778 0,00855 0,01089 0,01477 0,02177 0,05443 0,05832 0,06376 0,06998 0,07698 0,08165 0,07776 0,07621 0,07309 0,06610 0,06221 0,05443 0,03655 0,01944 0,00778 0,00622 0,00467 0,00467 0,00544 0,00389 0,00311 0,00078 0,00156 0,00078 0,00000 a=M(v)= vi*pi 0,0000 0,0381 0,0778 0,0793 0,1213 0,0824 0,1680 0,2566 0,2613 0,3546 0,4510 0,5047 0,6532 0,9012 1,3499 3,4292 3,7325 4,1446 4,6190 5,1579 5,5521 5,3655 5,3344 5,1897 4,7589 4,5412 4,0280 2,7411 1,4774 0,5988 0,4852 0,3686 0,3733 0,4409 0,3188 0,2582 0,0653 0,1322 0,0669 0,0000 68,48 vi-M(v) -20,48 -19,48 -18,48 -17,48 -16,48 -15,48 -14,48 -13,48 -12,48 -11,48 -10,48 -9,48 -8,48 -7,48 -6,48 -5,48 -4,48 -3,48 -2,48 -1,48 -0,48 0,52 1,52 2,52 3,52 4,52 5,52 6,52 7,52 8,52 9,52 10,52 11,52 12,52 13,52 14,52 15,52 16,52 17,52 18,52 D(v)= = pi*(vi-M(v))^2 0,0000 0,2950 0,5311 0,4751 0,6335 0,3726 0,6521 0,8477 0,7266 0,8197 0,8539 0,7686 0,7827 0,8264 0,9140 1,6340 1,1700 0,7718 0,4301 0,1684 0,0187 0,0211 0,1763 0,4645 0,8194 1,2715 1,6592 1,5541 1,0996 0,5646 0,5639 0,5164 0,6193 0,8534 0,7108 0,6559 0,1873 0,4245 0,2387 0,0000 26,09 5,11 pi*(vi-M(v))^4 0,0000 111,9505 181,3441 145,1630 172,0300 89,2814 136,7017 154,0074 113,1436 108,0105 93,7647 69,0562 56,2687 46,2262 38,3663 49,0528 23,4718 9,3410 2,6431 0,3684 0,0043 0,0057 0,4078 2,9524 10,1587 25,9887 50,5739 66,0865 62,2014 40,9940 51,1185 57,1660 82,1997 133,7866 129,9462 138,2944 45,1271 115,8601 73,2815 0,0000 3= As= E k= pi*(vi-M(v))^3 0,0000 -5,7472 -9,8135 -8,3050 -10,4393 -5,7679 -9,4414 -11,4257 -9,0667 -9,4094 -8,9479 -7,2852 -6,6362 -6,1808 -5,9216 -8,9529 -5,2404 -2,6850 -1,0662 -0,2491 -0,0090 0,0110 0,2681 1,1711 2,8852 5,7485 9,1603 10,1344 8,2704 4,8109 5,3690 5,4335 7,1348 10,6850 9,6107 9,5238 2,9075 7,0129 4,1825 0,0000 -28,27 -0,21 0,95 2. Найдем центральные моменты третьего и четвертого порядка по формулам: 3=M[(X-M(X))3]=-28,27 4=M[(X-M(X))4]=2686,34 3. Определяем величины асимметрии и эксцесса по формулам: As=3/3=-0,21 Ek=(4/4)-3=0,95 Т.к. : асимметрия – As=0,21 0 и х2 > 0, получаем заштрихованную часть плоскости, образующую многоугольник решений OABCD. Рис. 2.1 Затем строим линию уровня 10х1 + 5х2 = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линейной функции. Действительно Z0 = 10х10 + 5х20 = 10  0 + 5  0 = 0, ZA = 10х1А + 5х2А = 10  0 + 5  34 = 170, ZD = 10х1D + 5x2D = 10  25 + 5  0 = 250 и т. д. Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает min значение функции Z, a другая проходит через точку С и функция Z для нее принимает max значение. Эти линии уровня называются опорными. Точка С образована первой и второй прямыми. Следовательно, решая систему уравнений 14 x1  5 x 2  350 ,  14 x1  8 x2  392 найдем координаты точки С x1 = 20, х2 = 14, при этом Zmax = 10  20 + 5  14 = 270 руб. Таким образом, max прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изделий вида В. Лекция №6 Транспортная задача. Это задача о наиболее экономном плане перевозок однородного или взаимозаменяемого продукта из пунктов производства (станций отправления) в пункты потребления (станции назначения). Транспортная задача является важнейшей частной моделью линейного программирования, имеющей обширные практические приложения не только к проблемам транспорта. Особо важное значение она имеет в деле рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта. Постановка задачи и ее математическая модель Некоторый однородный продукт производится в m пунктах производства А1, А2, ..., Ат. Задан объем производства ai пункта Ai( i  1, m ). Произведенный продукт должен быть перевезен в n пунктов_потребления В1 В2, ..., Вn. Известен спрос bj. пункта Вj ( j  1, n ) Заданы также транспортные издержки Cij, связанные с перевозкой единицы продукта из пункта Аi в пункт Вj. Требуется составить план перевозок, обеспечивающий при минимальных транспортных расходах (издержках) удовлетворения спроса всех пунктов потребления за счет продукта, произведенного во всех пунктах производства. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Тогда условие задачи можно записать в виде табл. 1, которую в дальнейшем будем называть матрицей планирования. Таблица 1 Поставщики А1 … Ai … Am Потребности В1 С11 xl1 … Сi1 xi1 … Сm1 xm1 b1 Потребители Запасы … Bj … Bn С1j С1n … … a1 xlj xln … … … …. … Сij Сin … … ai xij xin … … … ... … Сmj Сmn … … am xmj xmn ∑ai … bj … bn ∑bj Тогда математическая формулировка транспортной задачи сводится к минимизации линейной формы m Z  i 1 при ограничениях n C j 1 ij xij n x j 1 ij  ai , i  1, m , ij  bj , (ограничения по запасам), m x i 1 j  1, m , (ограничения по потребностям), xij ≥ 0 Различают задачи с закрытой моделью, когда ∑ai=∑bj и открытой моделью, когда ∑ai≠∑bj т.е. баланс между запасами и потребностями отсутствует. Необходимым и достаточным условием разрешимости транспортной задачи является равенство суммарных запасов суммарным потребностям, т.е. m n i 1 j 1  ai   b j . Если ∑ai>∑bj, то вводят фиктивный (n + 1)-й пункт назначения с потребностью bn+1 = ∑ai-∑bj и полагают ci,n+1=0, i  1, m . Если ∑ai<∑bj, то вводят фиктивный (m + 1)-й пункт отправления с запасами am+1 = ∑bj-∑ai и полагают cm+1,j=0, j  1, n . Самым распространенным методом решения транспортной задачи является метод потенциалов. Решение разбивается на два этапа: 1. Определение начального допустимого базисного решения (первого опорного плана) - первоначальное распределение поставок. 2. Построение последовательных итераций (шагов), улучшающих опорные планы (каждый новый план не должен увеличивать суммарные затраты). После выполнения первого этапа шаги второго этапа проводятся до тех пор, пока не будет найдено оптимальное распределение поставок. Построение первоначального опорного плана Рассмотрим два метода построения первого опорного плана. План составляется последовательным заполнением по одной клетке в таблице перевозок так, что каждый раз либо полностью удовлетворяется потребность одного из потребителей, либо полностью вывозится груз от некоторого поставщика. Различие двух методов отыскания первого опорного плана состоит в различии способов выбора последовательности заполнения клеток. Диагональный метод или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется верхняя левая клетка ("северо-западный угол") оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки переменного х11 и заканчивается в клетке неизвестного xmn, т. е. идет как бы по диагонали таблицы перевозок. Метод наименьшей стоимости. Исходное опорное решение, построенное диагональным методом, как правило, оказывается весьма далеким от оптимального, так как при его определении совершенно игнорируются величины затрат сij. Поэтому требуются в дальнейших расчетах много итерации для достижения оптимального плана. Число итераций можно сократить, если исходный план строить по более рациональному правилу "минимального элемента". Сущность его состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной сij. Если такая клетка не единственная, то лучше заполнять ту, по вертикали или горизонтали которой встречаются большие cij, а в принципе заполняется любая из них. Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному, чем план, составленный по методу северозападного угла. Условие закрытости модели транспортной задачи означает, что среди m+n уравнений системы ограничений независимых только m+n-1, поэтому в любом базисном решении этой системы должно быть m+n-1 базисных переменных. Поскольку свободные переменные в таком решении равны нулю, то в транспортной таблице им будут соответствовать пустые клети. Клетки таблицы, в которых записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) — свободными. План называется вырожденным, если количество базисных клеток в нем меньше, чем m+n-1. Если на каком-то этапе решения получился вырожденный план, то его необходимо пополнить, проставив в недостающем числе клеток 0 и тем самым объявив их базисными. Поскольку этим дополнительным клеткам будут отвечать нулевые перевозки, то общий баланс и суммарная стоимость перевозок плана при этом не изменится. Однако проводить пополнение плана, выбирая клетки произвольно, нельзя. Приведем условия, которым должен соответствовать пополненный план. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ломаная может иметь точки самопересечения, но не в клетках цикла. План называется ациклическим, если его базисные клетки не содержат циклов. Доказано, что оптимальные планы являются ациклическими, поэтому и первоначальный план также должен удовлетворять этому требованию. Заметим, что планы, полученные с помощью методов северо-западного угла и наименьшей стоимости, ациклические. Однако если план оказался вырожденным, то при его пополнении требование ацикличности необходимо учитывать. Оптимальность базисного решения. Метод потенциалов Получив первый опорный план, следует проверить его оптимальность и, если требуется, перейти к новому опорному плану с лучшим значением целевой функции Z. Для этого применяют метод потенциалов. Каждому поставщику Аi и каждому потребителю Вj. сопоставляют, соответственно, величины Ui и Vj — потенциалы этих пунктов. Для того чтобы некоторый опорный план транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала система из (m+n) чисел, удовлетворяющих условиям: Cij-(Ui+Vj)=0 для xij≥0 (1) (для занятых клеток) и ΔC=Cij-(Ui+Vj)≥0, ( i  1, m ; j  1, n ) (2) 16 (для свободных клеток) . Поскольку число неизвестных потенциалов (m+n) всегда на единицу больше числа уравнений (числа заполненных клеток) N=m+n-1, то выбираем строку, где есть занятая клетка и для этой строки назначаем потенциал равным нулю и легко находим последовательно из уравнений (1) значения остальных потенциалов. Если же число заполненных клеток N0, то получим оптимальный план перевозок, если же встречаем отрицательные ΔCij, то план не оптимален и его надо улучшать. Улучшение плана перевозок Среди пустых клеток с отрицательными значениями ΔCij выбираем ту, у которой ΔCij наименьшая. Эта пустая клетка рекомендуется к заполнению, в результате которого одна из заполненных клеток станет пустой т.е. хij из не основных (нулевых) переходит в основные (положительные). Остается определить, какая из основных переменных должна стать не основной. Для свободной клетки строим замкнутую ломаную линию (цикл), состоящую из горизонтальных и вертикальных отрезков прямых. Одна из вершин находится в свободной клетке, а остальные в занятых клетках, число вершин всегда четное. Свободной вершине придаем знак плюс, знаки остальных вершин чередуются. На каждой стороне этого контура 16 Числа Ui, Vj называются потенциалами соответственно производителей и потребителей, вся их система — потенциальной, а условия (1) и (2) — условиями потенциальности системы; каждое в отдельности неравенство (равенство) называется условием потенциальности для соответствующей клетки (i, j). могут находиться две заполненные вершины, кроме того одна вершина лежит в заполняемой пустой клетке. Наиболее часто контур имеет вид прямоугольника, но возможны фигуры другого типа (рис.1). Рис.1 Перепланировке подвергаются только клетки контура, а величина перевозок во всех остальных заполненных клетках таблицы не изменяется. В отрицательных вершинах контура выбираем наименьшее число и это число прибавляем к положительным вершинам и отнимаем от отрицательных вершин. Выбранная отрицательная вершина станет свободной, число занятых вершин не изменится, баланс перевозок старого и нового контура останется без изменения. Далее строим новую таблицу перевозок и проверяем оптимальность плана. Если план оптимальный, то получим оптимальное решение транспортной задачи, если нет, то план улучшаем. Через какое-то число последовательных шагов улучшения планов перевозок будет получен оптимальный план. Открытая модель транспортной задачи Для открытой модели может быть два случая: а) суммарные запасы превышают суммарные потребности ∑ai>∑bj;. б) суммарные потребности превышают суммарные запасы ∑ai<∑bj. Открытая модель решается приведением к закрытой. В случае (а) вводится фиктивный потребитель Bn+1 потребности которого bn+1=∑ai-∑bj В случае (б) вводится фиктивный поставщик Am+1 запасы которого am+1 =∑bj-∑ai Стоимости перевозок в обоих случаях полагаются равными нулю. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. ПРАКТИКА №6 Пример решения расчетной работы: шифр – 123456 n u1 (тыс.м3) u2 (тыс.м3) u3 (тыс.м3) u4 (тыс.м3) u5 (тыс.м3) = = = = = = кар-р 85 u1 35 5 35 45 55 65 45 m v1 (тыс.м3) v2 (тыс.м3) v3 (тыс.м3) v4 (тыс.м3) v5 (тыс.м3) = = = = = = 4 25 35 45 55 65 Баланс земляных масс: ∑VВыемок = 35+45+55+65+45=245 тыс.м3 ∑VНасыпей = 25+35+45+55=160 тыс.м3 Требуется разработка грунтового карьера мощностью 245-160=85 тыс.м3. Транспортная задача носит открытый характер. Т.к. m