20.2. Алгоритм решения задач

1. Находим область допустимых решений системы ограни­чений задачи.

2. Строим вектор .

3. Проводим линию уровня L₀, которая перпендикулярна .

4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача ЛП будет иметь бесчисленное множество решений. Говорят, что такая задача ЛП имеет альтернативный оптимум, и ее решение находится по формуле

где 0 ≤ t ≤ 1, ₁ и ₂ — оптимальные решения в угловых точках ОДР.

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

5. Находим координаты точки экстремума и значение це­левой функции в ней.

80. Решение задачи линейного программирования симплекс-методом. Симплексные таблицы. Алгоритм симплекс-метода.

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

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

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

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. Несколько событий образуют полную груп­пу, если в результате испытания появление хотя бы одного из них является достоверным событием. Например, при произве­дении выстрела по мишени (испытание) обязательно будет ли­бо попадание, либо промах; эти два события образуют полную группу.

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

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