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

Теорема (локальная теорема Лапласа). Если вероятностьpпоявления события А в каждом испытании постоянна и отлична от 0 и 1, то вероятность
того, что событие А появится вnнезависимых испытаниях ровноkраз, приближенно равна значению функции:

,

.

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

Заметим, что функция
четна.

Итак, вероятность того, что событие А появится в nиспытаниях ровноkраз приближенно равна

, где
.

Пример. На опытном поле посеяли 1500 семян. Найти вероятность того, что всходы дадут 1200 семян, если вероятность того, что зерно взойдет, равна 0,9.

Решение.

Интегральная теорема Лапласа

Вероятность того, что в nнезависимых испытаниях событие А появится не менееk1 раз и не болееk2 раз вычисляется по интегральной теореме Лапласа.

Теорема (интегральная теорема Лапласа). Если вероятность р наступления события а в каждом испытании постоянна и отлична от 0 и 1, то вероятность того, что событие А вnиспытаниях появится не менееk 1 раз и не болееk 2 раз приближенно равна значению определенного интеграла:

.

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

Пример. В лаборатории из партии семян, имеющих всхожесть 90%, высеяно 600 семян, давших всходы, не менее 520 и не более 570.

Решение.

Формула Пуассона

Пусть производится nнезависимых испытаний, вероятность появления события А в каждом испытании постоянна и равна р. Как мы уже говорили, вероятность появления события А вnнезависимых испытаниях ровноkраз можно найти по формуле Бернулли. При достаточно большомnиспользуют локальную теорему Лапласа. Однако, эта формула непригодна, когда вероятность появления события в каждом испытании мала или близка к 1. А при р=0 или р=1 вообще не применима. В таких случаях пользуются теоремой Пуассона.

Теорема (теорема Пуассона). Если вероятность р наступления события А в каждом испытании постоянна и близка к 0 или 1, а число испытаний достаточно велико, то вероятность того, что вnнезависимых испытаниях событие А появится ровноkраз находится по формуле:

.

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

Решение.

Вопросы для самопроверки

Сформулируйте классическое определение вероятности события.

Сформулируйте теоремы сложения и умножения вероятностей.

Дайте определение полной группы событий.

Запишите формулу полной вероятности.

Запишите формулу Бейеса.

Запишите формулу Бернулли.

Запишите формулу Пуассона.

Запишите локальную формулу Лапласа.

Запишите интегральную формулу Лапласа.

Тема 13. Случайная величина и ее числовые характеристики

Литература: ,,,,,.

Одним из основных понятий в теории вероятностей является понятие случайной величины. Так принято называть переменную величину, которая принимает свои значения в зависимости от случая. Различают два вида случайных величин: дискретные и непрерывные. Случайные величины принято обозначать X,Y,Z.

Случайная величина Х называется непрерывной (дискретной), если она может принимать лишь конечное или счетное число значений. Дискретная случайная величина Х определена, если даны все ее возможные значения х 1 , х 2 , х 3 ,…х n (число которых может быть как конечным, так и бесконечным) и соответствующие вероятности р 1 , р 2 , р 3 ,…р n .

Закон распределения дискретной случайной величины Х обычно задается таблицей:

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

р 1 +р 2 + р 3 +…+р n =1.

Закон распределения дискретной случайной величины Х можно изобразить графически. Для этого в прямоугольной системе координат строят точки М 1 (х 1 ,р 1), М 2 (х 2 ,р 2), М 3 (х 3 ,р 3),…М n (x n ,p n) и соединяют их отрезками прямых. Полученную фигуру называют многоугольником распределения случайной величины Х.

Пример. Дискретная величина Х задана следующим законом распределения:

Требуется вычислить: а) математическое ожидание М(Х), б) дисперсию D(X), в) среднее квадратическое отклонение σ.

Решение. а) Математическое ожидание М(Х), дискретной случайной величины Х называется сумма попарных произведений всех возможных значений случайной величины на соответствующие вероятности этих возможных значений. Если дискретная случайная величина Х задана с помощью таблицы (1), то математическое ожидание М(Х) вычисляется по формуле

М(Х)=х 1 ∙р 1 +х 2 ∙р 2 +х 3 ∙р 3 +…+х n ∙p n . (2)

Математическое ожидание М(Х) называют также средним значением случайной величины Х. Применяя (2), получим:

М(Х)=48∙0,2+53∙0,4+57∙0,3 +61∙0,1=54.

б) Если М(Х) есть математическое ожидание случайной величины Х, то разность Х-М(Х) называется отклонением случайной величины Х от среднего значения. Эта разность характеризует рассеяние случайной величины.

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

D(X)=M 2 . (3)

Вычислим все возможные значения квадрата отклонения.

2 =(48-54) 2 =36

2 =(53-54) 2 =1

2 =(57-54) 2 =9

2 =(61-54) 2 =49

Чтобы вычислить дисперсию D(X), составим закон распределения квадрата отклонения и затем применим формулу (2).

D(X)= 36∙0,2+1∙0,4+9∙0,3 +49∙0,1=15,2.

Следует отметить, что для вычисления дисперсии часто используют следующее свойство: дисперсия D(X) равна разности между математическим ожиданием квадрата случайной величины Х и квадратом ее математического ожидания, то есть

D(X)-M(X 2)- 2 . (4)

Чтобы вычислить дисперсию по формуле (4), составим закон распределения случайной величины Х 2:

Теперь найдем математическое ожидание М(Х 2).

М(Х 2)= (48) 2 ∙0,2+(53) 2 ∙0,4+(57) 2 ∙0,3 +(61) 2 ∙0,1=

460,8+1123,6+974,7+372,1=2931,2.

Применяя (4), получим:

D(X)=2931,2-(54) 2 =2931,2-2916=15,2.

Как видно, мы получили такой же результат.

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

σ=
. (5)

Применяя (5), имеем: σ=
.

Пример. Случайная величина Х распределена по нормальному закону. Математическое ожидание М(Х)=5; дисперсияD(X)=0,64. Найти вероятность того, что в результате испытания Х примет значение в интервале (4;7).

Решение .Известно, что если случайная величина Х задана дифференциальной функциейf(x), то вероятность того, что Х примет значение, принадлежащее интервалу (α,β), вычисляется по формуле

. (1)

Если величина Х распределена по нормальному закону, то дифференциальная функция

,

где а =М(Х) и σ=
. В этом случае получаем из (1)

. (2)

Формулу (2) можно преобразовать, используя функцию Лапласа.

Сделаем подстановку. Пусть
. Тогда
илиdx =σ∙ dt .

Следовательно
, гдеt 1 иt 2 соответствующие пределы для переменнойt.

Сократив на σ, будем иметь

Из введенной подстановки
следует, что
и
.

Таким образом,

(3)

По условию задачи имеем: а=5; σ=
=0,8; α=4; β=7. Подставив эти данные в (3), получим:

=Ф(2,5)-Ф(-1,25)=

=Ф(2,5)+Ф(1,25)=0,4938+0,3944=0,8882.

Пример. Считается, что отклонение длины изготавливаемых деталей от стандарта является случайной величиной, распределенной по нормальному закону. Стандартная длина (математическое ожидание) а=40 см, среднее квадратическое отклонение σ=0,4 см. Найти вероятность того, что отклонение длины от стандартной составит по абсолютной величине не более 0,6 см.

Решение .Если Х – длина детали, то по условию задачи эта величина должна быть в интервале (а-δ,а+δ), где а=40 и δ=0,6.

Положив в формулу (3) α= а-δ и β= а+δ, получим

. (4)

Подставив в (4) имеющиеся данные, получим:

Следовательно, вероятность того, что изготавливаемые детали по длине будут в пределах от 39,4 до 40,6 см, составляет 0,8664.

Пример. Диаметр деталей, изготавливаемых заводом, является случайной величиной, распределенной по нормальному закону. Стандартная длина диаметраа=2,5 см, среднее квадратическое отклонение σ=0,01. В каких границах можно практически гарантировать длину диаметра этой детали, если за достоверное принимается событие, вероятность которого равна 0,9973?

Решение. По условию задачи имеем:

а=2,5; σ=0,01; .

Применяя формулу (4), получаем равенство:

или
.

По таблице 2 находим, что такое значение функция Лапласа имеет при х=3. Следовательно,
; откуда σ=0,03.

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

Теорема 2 (Муавра-Лапласа (локальная)). А в каждом из n независимых испытаниях равна р n испытаниях событие А наступит раз, приближенно равна (чем больше n , тем точнее) значению функции

,

где , . Таблица значений функции приведена в прил. 1.

Пример 6.5. Вероятность найти белый гриб среди прочих равна . Какова вероятность того, что среди 300 грибов белых будет 75?

Решение. По условию задачи , . Находим . По таблице находим .

.

Ответ: .

Теорема 3 (Муавра-Лапласа (интегральная)). Если вероятность наступления события А в каждом из n независимых испытаний равна р и отлична от нуля и единицы, а число испытаний достаточно велико, то вероятность того, что в n испытаниях число успехов m находится между и , приближенно равна (чем больше n , тем точнее)

,

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

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

Решение. По условию По интегральной теореме Лапласа

Ответ:

Пример 6.7. Город ежедневно посещает 1000 туристов, которые днем идут обедать. Каждый из них выбирает для обеда один из двух городских ресторанов с равными вероятностями и независимо друг от друга. Владелец одного из ресторанов желает, чтобы с вероятностью приблизительно 0,99 все пришедшие в его ресторан туристы могли там одновременно пообедать. Сколько мест должно быть для этого в его ресторане?

Решение. Пусть А = «турист пообедал у заинтересованного владельца». Наступление события А будем считать «успехом», , . Нас интересует такое наименьшее число k , что вероятность наступления не менее чем k «успехов» в последовательности из независимых испытаний с вероятностью успеха р = 0,5 приблизительно равна 1 – 0,99 = 0,01. Это как раз вероятность переполнения ресторана. Таким образом, нас интересует такое наименьшее число k , что . Применим интегральную теорему Муавра-Лапласа

Откуда следует, что

.

Используя таблицу для Ф (х ) (прил. 2), находим , значит . Следовательно, в ресторане должно быть 537 мест.

Ответ: 537 мест.

Из интегральной теоремы Лапласа можно получить формулу

.

Пример 6.8. Вероятность появления события в каждом из 625 независимых испытаний равна 0,8. Найти вероятность того, что относительная частота появления события отклонится от его вероятности по абсолютной величине не более чем на 0,04.

Интегральная теорема Лапласа

Теорема. Если вероятность р наступления события А в каждом испытании постоянна и отлична от нуля и единицы, то вероятность того, что число m наступления события А в n независимых испытаниях заключено в пределах от a до b (включительно), при достаточно большом числе испытаний n приближенно равна

Интегральная формула Лапласа, также как и локальная формула Муавра-Лапласа, тем точнее, чем больше n и чем ближе к 0,5 значения p и q . Вычисление по этой формуле дает незначительную погрешность при выполнении условия npq ≥ 20, хотя допустимым можно считать выполнение условия npq > 10.

Функция Ф(x ) табулирована (см. Приложение 2). Для применения этой таблицы нужно знать свойства функции Ф(x ):

1. Функция Ф(x ) – нечетная, т.е. Ф(–x ) = – Ф(x ).

2. Функция Ф(x ) – монотонно возрастающая, причем при x → +∞ Ф(x ) → 0,5 (практически можно считать, что уже при x ≥ 5 Ф(x ) ≈ 0,5).

Пример 3.4. По условиям примера 3.3 вычислить вероятность того, что от 300 до 360 (включительно) студентов успешно сдадут экзамен с первого раза.

Решение. Применяем интегральную теорему Лапласа (npq ≥ 20). Вычисляем:

= –2,5; = 5,0;

P 400 (300 ≤ m ≤ 360) = Ф(5,0) – Ф(–2,5).

Учитывая свойства функции Ф(x ) и пользуясь таблицей ее значений, находим: Ф(5,0) = 0,5; Ф(–2,5) = – Ф(2,5) = – 0,4938.

Получаем P 400 (300 ≤ m ≤ 360) = 0,5 – (– 0,4938) = 0,9938. ◄

Запишем следствия интегральной теоремы Лапласа.

Следствие 1. Если вероятность р наступления события А в каждом испытании постоянна и отлична от нуля и единицы, то при достаточно большом числе n независимых испытаний вероятность того, что число m наступления события А отличается от произведения np не более, чем на величину ε > 0

.

(3.8)

Пример 3.5. По условиям примера 3.3 найти вероятность того, что от 280 до 360 студентов успешно сдадут экзамен по теории вероятностей с первого раза.

Решение. Вычислить вероятность Р 400 (280 ≤ m ≤ 360) можно аналогично предыдущему примеру по основной интегральной формуле Лапласа. Но проще это сделать, если заметить, что границы интервала 280 и 360 симметричны относительно величины np =320. Тогда на основании следствия 1 получаем

= = ≈

≈ = 2Ф(5,0) ≈ 2·0,5 ≈ 1,

т.е. практически достоверно, что от 280 до 360 студентов успешно сдадут экзамен с первого раза. ◄

Следствие 2. Если вероятность р наступления события А в каждом испытании постоянна и отлична от нуля и единицы, то при достаточно большом числе n независимых испытаний вероятность того, что частость m/n события А заключена в пределах от α до β (включительно) равна

,

(3.9)

где

, .

(3.10)

Пример 3.6. По статистическим данным в среднем 87% новорожденных доживают до 50 лет. Найти вероятность того, что из 1000 новорожденных доля (частость) доживших до 50 лет будет заключена в пределах от 0,9 до 0,95.

Решение. Вероятность того, что новорожденный доживет до 50 лет равна р = 0,87. Так как n = 1000 велико (т.е. условие npq = 1000·0,87·0,13 = 113,1 ≥ 20 выполнено), то используем следствие 2 интегральной теоремы Лапласа. Находим:

2,82, = 7,52.

= 0,5 – 0,4976 = 0,0024. ◄

Следствие 3. Если вероятность р наступления события А в каждом испытании постоянна и отлична от нуля и единицы, то при достаточно большом числе n независимых испытаний вероятность того, что частость m/n события А отличается от его вероятности р не более, чем на величину Δ > 0 (по абсолютной величине) равна

.

(3.11)

Пример 3.7. По условиям предыдущей задачи найти вероятность того, что из 1000 новорожденных доля (частость) доживших до 50 лет будет отличаться от вероятности этого события не более, чем на 0,04 (по абсолютной величине).

Решение. Используя следствие 3 интегральной теоремы Лапласа, находим:

= 2Ф (3,76) = 2·0,4999 = 0,9998.

Так как неравенство равносильно неравенству , полученный результат означает, что практически достоверно, что от 83 до 91% новорожденных из 1000 доживут до 50 лет. ◄

Ранее мы установили, что для независимых испытаний вероятность числа m появлений события А в n испытания находится по формуле Бернулли. Если же n велико, то пользуются асимптотической формулой Лапласа. Однако эта формула непригодна, если вероятность события мала (р ≤ 0,1). В этом случае (n велико, р мало) применяют теорему Пуассона

Формула Пуассона

Теорема. Если вероятность p наступления события А в каждом испытании стремится к нулю (p → 0) при неограниченном увеличении числа n испытаний (n→ ∞), причем произведение np стремится к постоянному числу λ (np → λ), то вероятность P n (m) того, что событие А появится m раз в n независимых испытаниях, удовлетворяет предельному равенству

Алгоритм метода искусственного базиса имеет следующие особенности:

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

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

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

4. Переход от решения расширенной задачи к решению исходной задачи производится с использованием доказанных выше теорем 4.1-4.3.

Пример 4.4. Решить задачу линейного программирования методом искусственного базиса

.

Решение . Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом (всегда) +1. Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим , во второе — . Данная задача — задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом — М . Получаем

Задача имеет начальное опорное решение с единичным базисом .

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

.
.

Записываем исходные данные в симплексную таблицу (табл. 4.6).

Т а б л и ц а 4.6

При этом оценки и для удобства вычислений записываем в две строки: в первую — слагаемые , не зависящие от М , во вторую — слагаемые , зависящие от М . Значения удобно указывать без М , имея в виду однако, что оно там присутствует.

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

В третьем столбце " " за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.

Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение с базисом (табл. 4.7). Решение не является оптимальным так как имеется отрицательная оценка = — 1.

Т а б л и ц а 4.7

В столбце " " единственный положительный элемент принимаем за разрешающий и переходим к новому опорному решению с базисом (табл. 4.8).

Т а б л и ц а 4.8

Данное опорное решение является единственным оптимальным решением расширенной задачи, так как в задаче на максимум оценки для всех векторов, не входящих в базис, положительны. По теореме 4.1 исходная задача также имеет оптимальное решение, которое получается из оптимального решения расширенной задачи отбрасыванием нулевых искусственных переменных, т. е. Х * = (0,0,6,2).

Ответ : max Z (X ) = -10 при .

Пример 4.5. Решить методом искусственного базиса задачу линейного программирования со смешанными ограничениями

Решение . Приводим задачу линейного программирования к каноническому виду. Для этого вводим дополнительные переменные и в первое и третье ограничения соответственно. Получаем

.

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

Данная расширенная задача имеет начальное опорное решение

С единичным базисом , . Вычисляем оценки векторов условий по базису опорного решения и записываем в симплексную таблицу так же, как в предыдущем примере. Решение не является оптимальным, так как в задаче на минимум векторы и имеют положительные оценки . Улучшаем опорные решения. Каждому опорному решению соответствует своя таблица. Все таблицы можно записать друг под другом, объединив в единую таблицу (табл. 4.9).

Т а б л и ц а 4.9

Определяем, введение какого из векторов или в базис начального опорного решения приведет к большему уменьшению целевой функции. Находим при k = 2, т. е. лучше ввести в базис вектор . Получаем второе опорное решение с базисом . Целевая функция . Это решение также не является оптимальным, так как вектор имеет положительную оценку . Вводим вектор в базис, получаем третье опорное решение с базисом . Целевая функция . Это решение оптимальное, но не единственное, так как вектор , не входящий в базис, имеет нулевую оценку. Поэтому необходимо перейти к новому опорному решению, которое также будет оптимальным. Для этого требуется ввести в базис вектор .

Переходим к четвертому опорному (оптимальному) решению

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

Ответ : при , , , .

Слово симплекс

Слово симплекс английскими буквами(транслитом) — simpleks

Слово симплекс состоит из 8 букв: е и к л м п с с

Значения слова симплекс. Что такое симплекс?

Симплекс

Симплекс (от лат. simplex - простой) (математический), простейший выпуклый многогранник данного числа измерений n. При n = 3 трёхмерный С. представляет собой произвольный, в том числе неправильный, тетраэдр.

БСЭ. - 1969-1978

Симплекс - выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. С. выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости.

slovar-lopatnikov.ru

СИМПЛЕКС - выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. С. выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости.

Лопатников. - 2003

Саб симплекс

Саб симплекс Способ применения и дозы: Внутрь, во время или после еды и, при необходимости, перед сном. Перед применением следует активно встряхнуть флакон.

Решение ЗЛП симплекс методом с искусственным базисом

Чтобы суспензия начала поступать из пипетки…

Саб симплексДействующее вещество ›› Симетикон* (Simethicone*) Латинское название Sab simplex АТХ:›› A02DA Ветрогонные препараты Фармакологическая группа…

Словарь медицинских препаратов. — 2005

САБ® СИМПЛЕКС (SAB® SIMPLEX) Суспензия для приема внутрь от белого до серо-белого цвета, слегка вязкая, с характерным фруктовым (ванильно-малиновым) запахом. 100 мл симетикон 6.919 г…

ШОКЕ СИМПЛЕКС

ШОКЕ СИМПЛЕКС — непустое компактное выпуклое множество Xв локально выпуклом пространстве E, обладающее следующим свойством: при вложении Ев качестве гиперплоскости в пространство проектирующий конус.

Шеффилд-Симплекс

«Шеффилд-Симплекс» (англ. Sheffield-Simplex) - лёгкий пулемётный бронеавтомобиль Вооружённых сил Российской империи. Разработан британской фирмой «Sheffield-Simplex» на базе шасси собственного легкового автомобиля…

ru.wikipedia.org

Нордитропин Симплекс

Нордитропин Симплекс Показания: Задержка роста у детей вследствие недостаточности гормона роста или хронической почечной недостаточности (в препубертатном возрасте), синдрома Шерешевского - Тернера…

НОРДИТРОПИН® СИМПЛЕКС® (NORDITROPIN SimpleXx) Раствор для п/к введения 1.5 мл (1 картридж) соматропин 10 мг 1.5 мл — картриджи (1) — упаковки ячейковые контурные (1) — пачки картонные.

Справочник лекарственных препаратов "Видаль"

СТАНДАРТНЫЙ СИМПЛЕКС

СТАНДАРТНЫЙ СИМПЛЕКС — 1) С. с.- симплекс размерности пв пространстве с вершинами в точках е i=(0,…, 1,…, 0), i=0,…, п(единица стоит на i-м месте), т. е.

Математическая энциклопедия. — 1977-1985

Двойственный симплекс-метод

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

ru.wikipedia.org

Русский язык

Си́мпле́кс/.

Морфемно-орфографический словарь. - 2002

Поиск Лекций

Пример решения задачи методом искусственного базиса.

Найти минимум функции F=-2×1+3×2 — 6×3 — x4 при условиях

Решение. Запишем данную задачу в форме основной задачи: найти максимум функции F1=2×1 – 3×2 + 6×3 + x4 при условиях

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

А1 = А2 = А 3= А 4= А 5= А 6=

Среди векторов А1 ,…, А 6 только два единичных (А 4 и А 5). Поэтому в левую часть третьего уравнения системы ограничений добавим дополнительную неотрицательную переменную x 7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F=2×1 – 3×2 + 6×3 + x4 – Mx7

при условиях

Расширенная задача имеет опорный план X=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: А 4 , А5 , А7 .

Таблица 1

i	Базис	Сσ	А0	-3	—M
А1	А2	А3	А4	А5	А6	P7
А4	-2
А5
А7	—M	-1	-1
m +1			-8
m +2			-10	-1	-2

Составляем таблицу (1) I итерации, содержащую пять строк. Для заполнения 4-й и 5-й строк находим F 0 и значения разностей zj – cj (j= ):

F 0 = 24–10M;

z1–c1 = 0–M ;

z2–c2 = 4+M ;

z3–c3 = –8–2M ;

z4–c4 =0+M ;

z5–c5 =0+M ;

z6–c6 = 0+M ;

z7–c7 =0+M ;

Значения F 0 и zj–cj состоят из двух слагаемых, одно из которых содержит M , а другое – нет.

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

В 5-й строке табл.1 в столбцах векторов Аj (j = ) имеется два отрицательных числа (-1 и -2). Наличие этих чисел говорит о том, что данный опорный план расширенной задачи не является оптимальным. Переходим к новому опорному плану расширенной задачи.

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

В базис вводим вектор А3 . Чтобы определить вектор, исключаемый из базиса, находим θ=min(22/4; 10/2)=10/2. Следовательно, вектор А7 исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последующих базисов, поэтому в дальнейшем столбец данного вектора не заполняется (табл. 2 и 3).

Составляем таблицу II итерации (табл. 2). Она содержит только четыре строки, так как искусственный вектор из базиса исключен.

Таблица2

i	Базис	Сσ	А0	-3
А1	А2	А3	А4	А5	А6
А4	-1
А5	-1
А3	1/2	-1/2	-1/2
m +1			-4

Как видно из табл. 2, для исходной задачи опорным является план Х =(0;0;5;34;2).

Проверим его на оптимальность. Для этого рассмотрим элементы 4-й строки. В этой строке в столбце вектора А6 имеется отрицательное число (-4). Следовательно, данный опорный план не является оптимальным и может быть улучшен благодаря введению в базис вектора А6. Из базиса исключается вектор А5 . Составляем таблицу III итерации.

Таблица 3

В 4-й строке табл.3 среди чисел ∆j нет отрицательных. Это означает, что найденный новый опорный план исходной задачи Х *=(0; 0; 11/2; 35; 0; 1) является оптимальным. При этом плане значение линейной формы Fmax = 68.

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

©2015-2018 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Нарушение авторских прав и Нарушение персональных данных

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

• система должна иметь каноническую (ступенчатую) структуру;
• присутствуют только ограничения-равенства;
• правые части ограничений положительны;
• переменные задачи положительны.

Без этих условий нельзя получить опорный план. Однако в реальных задачах далеко не всегда выполняются перечисленные условия.

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

Пусть задача линейного программирования приведена к стандартному виду:

Пусть все /? > 0, но часть или все базисные переменные отрицательны, X; 0. Следовательно, опорного плана нет.

Дополним уравнения-ограничения искусственными переменными (предполагаем, что все x j j - 1, п ).

Введем т переменных (по количеству уравнений): х лМ т, которые в новой системе будут базисными, а отрицательные х-

В результате получим следующую эквивалентную задачу.

Здесь переменные x n+i не имеют никакого отношения к исходной задаче линейного программирования. Они служат лишь для получения опорного плана и называются искусственными переменными. А новая

целевая функция /(.т) сформирована для полноты задачи.

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

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

Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные х } , х А, х 5 , х 6 и запишем задачу в канонической форме.

Свободные переменные х, х 2 = 0, при этом базисные переменные примут значения х 3 =-5, х 4 = -5, х 5 = 7, х 6 =9. Так как часть базисных переменных отрицательны, следовательно опорного плана нет. Для получения начального опорного плана введем переменные х 7 , х 8 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:

Таким образом, начальным базисом является

Симплекс-таблица с искусственным базисом

	Х 4

Запишем последовательности опорных планов.

Для первых трех шагов приращения А к вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию /(х) = х 7 + х 8 с коэффициентом с, = 1.

На третьем шаге искусственные переменные исключены, так как все А к положительны.

Итак, симплекс-метод с введением искусственных переменных включает два этапа.

Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи /(х) = 0.

Оптимальный опорный план вспомогательной задачи ЛП является начальным опорным планом основной задачи ЛП. Задача решается для исходной целевой функции /(х) обычным симплекс-методом.

Замечания

• 1. Введение искусственных переменных требуется в двух случаях:
  • ряд базисных переменных х, в канонической форме отрицательны;
  • если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.
• 2. Встречающиеся в практике автоматического управления задачи линейного программирования содержат от 500 до 1500 ограничений и более 1000 переменных. Ясно, что задачи такой размерности можно решать лишь с помощью ЭВМ и специального программного обеспечения. Сложность алгоритма заключается в том, что:
  • ППП требует канонического вида;
  • ППП для задач такой размерности требует использования больших ЭВМ (и параллельных вычислений), так как симплекс-метод хранит всю таблицу.
• 3. Вычислительную эффективность симплекс-метода можно оценить следующими показателями:
  • число шагов (смежных опорных планов);
  • затраты машинного времени.

Существуют такие теоретические оценки для стандартной задачи линейного программирования с т ограничений и «"переменных:

• среднее число шагов * 2 т и лежит в диапазоне }