Алгоритм симплексного метода

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

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу (табл. 21.1). Все строки таблицы 1-го шага, за исключением строки Δ _j (индексная строка), заполняем по данным системы ограничений и целевой функции.

Индексная строка для переменных находится по формуле

и по формуле

Возможны следующие случаи при решении задачи на максимум:

— если все оценки Δ _j ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка Δ _j ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т.е. целевая функция неограничена в области допусти­мых решений;

— если хотя бы одна оценка отрицательная, а при соответ­ствующей переменной есть хотя бы один положитель­ный коэффициент, то нужно перейти к другому опорно­му решению;

— если отрицательных оценок в индексной строке несколь­ко, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по аб­солютной величине отрицательная оценка.

Если хотя бы одна оценка Δ _k < 0, то k- й столбец прини­маем за ключевой. За ключевую строку принимаем ту, кото­рой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k- гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

— переписываем ключевую строку, разделив ее на ключе­вой элемент;

— заполняем базисные столбцы;

— остальные коэффициенты таблицы находим по прави­лу "прямоугольника"*. Оценки можно считать по приве­денным выше формулам или по правилу "прямоугольни­ка" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

81. Решение задачи оптимизации выпуска продукции симплекс-методом

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

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором — 4 тыс. изделий.

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

Решение. Составим математическую модель задачи. Обо­значим: x ₁ — время работы предприятия первым способом, x ₂ — время работы предприятия вторым способом.

Математическая модель имеет вид

при ограничениях:

Приведем задачу к каноническому виду:

при ограничениях:

Составляем симплексную таблицу 1-го шага (табл. 21.3).

Получим решение:

В индексной строке Δ _j имеются две отрицательные оцен­ки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следу­ет принять столбец базисной переменной х ₂, а за ключевую строку взять строку переменной x ₃, где min (4/2,3/l, 8/1) = min (2, 3, 8) = 2.

Ключевым элементом является (2). Вводим в столбец ба­зисной переменной х ₂, выводим х ₃. Составляем симплексную таблицу 2-го шага (табл. 21.4).

Получим

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является (1/2). Составляем симплексную таблицу 3-го шага (табл. 21.5).

Все оценки свободных переменных Δ _j ≥ 0, следовательно, найденное опорное решение является оптимальным:

Таким образом, по первому способу предприятие должно работать два месяца, по второму — один месяц, при этом мак­симальный выпуск продукции составит 10 тыс. ед.

82. Модель оптимизации плана перевозок (транспортная задача). Экономическая постановка задачи.

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

В общем виде задачу можно представить следующим об­разом: в т. пунктах производства A ₁, A ₂,..., A_m имеется од­нородный груз в количестве соответственно a ₁, a ₂ ,…, a_m. Этот груз необходимо доставить в п пунктов назначения B ₁, В ₂, …., В_п в количестве соответственно b ₁, b ₂ ,..., b_п. Сто­имость перевозки единицы груза (тариф) из пункта A_i в пункт B_j равна c_ij.

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

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

Определение 1. Если

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

то открытой.

Обозначим через x_ij количество груза, перевозимого из пункта A_i в пункт B_j. Рассмотрим закрытую транспорт­ную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения (табл. 23.1).

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

при ограничениях:

Оптимальным решением задачи является матрица

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

— нахождение исходного опорного решения;

— проверка этого решения на оптимальность;

— переход от одного опорного решения к другому.

83. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

≈82.

84. Построение начального (опорного) плана перевозок по методу северо-западного угла и по методу наименьшей стоимости.

87. Понятия испытания и случайного события. Частота и относительная частота появления события в серии испытаний. Вероятность случайного события.

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

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

Выше было введено определение случайного события. Обычно в теории вероятностей вместо "совокупности условий" употребляют термин "испытание", и тогда событие трактует­ся как результат испытания. Например, стрельба по мишени: выстрел — это испытание, попадание в мишень — это собы­тие. Другой пример: подбрасывание монеты вверх — это ис­пытание, выпадение орла (или решки) — это событие.

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

Определение 2. Несколько событий образуют полную груп­пу, если в результате испытания появление хотя бы одного из них является достоверным событием. Например, при произве­дении выстрела по мишени (испытание) обязательно будет ли­бо попадание, либо промах; эти два события образуют полную группу.

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

Этот частный случай будет использован далее.

Классическое определение вероятности

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

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

Вероятность события А обозначается Р(А). Понятие веро­ятности является одним из основных в теории вероятностей. Данное выше определение является классическим. Из него вы­текают некоторые свойства.

Свойство 1. Вероятность достоверного события равна единице.

Свойство 2. Вероятность невозможного события равна нулю.

Свойство 3. Вероятность случайного события есть поло­жительное число:

Следовательно, вероятность любого события удовлетворя­ет неравенству

Отметим, что современные курсы теории вероятностей ос­нованы на теоретико-множественном подходе, в котором эле­ментарные события являются точками пространства элемен­тарных событий Ω; при этом событие А отождествляется с подмножеством элементарных исходов, благоприятствующих этому событию, А Ω.

Приведем примеры непосредственного вычисления вероят­ностей.

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

Решение. Найдем число благоприятных исходов: число способов, которыми можно взять 4 белых шара из 6 имеющихся, равно C = C = . = 15. Общее число исходов определяется числом сочетаний из 10 по 5: C = 252. Согласно определению 3 искомая вероятность Р = 15/252 ≈ 0,06.

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

Определение 1. Суммой двух событий А и В называют со­бытие С = А + В, которое состоит в появлении либо события А, либо события В, либо событий A и В одновременно.

Это определение напоминает сумму множеств (см. гл. 1) и используется в теоретико-множественном подходе теории веро­ятностей. Примеры суммы событий: произведены два выстре­ла, и события А и В — попадания при первом и втором вы­стрелах соответственно; тогда А + В — попадание либо при первом выстреле, либо при втором, либо в обоих выстрелах. Если события А и В несовместные, то их сумма — это собы­тие, состоящее в появлении какого-либо из этих событий.

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

ТЕОРЕМА 1. Вероятность появления какого-либо из двух несовместных событий равна сумме вероятностей этих со­бытий:

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

Пример 1. Стрелок стреляет по мишени, разделенной на 4 концентрические зоны. Вероятности попадания в эти области соответственно равны 0,4, 0,3, 0,2 и 0,1. Найти вероятность попадания либо в первую, либо во вторую зоны.

Решение. Пусть событие А — попадание в первую зону мишени, а событие В — попадание во вторую зону мишени. Эти события несовместны, поэтому применимы теорема 17.1 и формула (17.3) сложения вероятностей. Искомая вероятность равна

Дата добавления: 2015-05-26