Исследование операций

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

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

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

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

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

Граничные условия показывают предельно допустимые значения искомых переменных.

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

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

Раздел 1. Основы моделирования

§ 1. Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

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

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

Иногда в результате исследования удается указать одно-единственное строго оптимальное решение, чаще — выделить область практически равноценных оптимальных (разумных) решений, в пределах которой может быть сделан окончательный выбор.

Параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А1, А2, … Am в пункты назначения В1, В2, …, Вn, то элементами решения будут числа xij, показывающие, какое количество груза будет отправлено из i-го пункта отправления Ai в j-й пункт назначения Bj. Совокупность чисел xij образует решение.

Совокупность элементов решения будем обозначать одной буквой х и говорить «решение х».

Кроме элементов решения в любой задаче исследования операций имеются еще заданные условия, которые фиксированы с самого начала и нарушены быть не могут (например, грузоподъемность машины; размер планового задания; весовые характеристики оборудования и т. п.). В своей совокупности они формируют так называемое «множество возможных решений».

Обозначим это множество буквой X. Запишем в виде формулы, что решение х принадлежит этому множеству: х X (читается: элемент х входит в множество X).

Во множестве возможных решений Х необходимо выделить те решения х (одно или область решений), которые с той или другой точки зрения эффективнее других. Для сравнения между собой по эффективности разные решения существует количественный критерий — показатель эффективности W («целевая функция»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели.

Если показатель эффективности желательно максимизировать, то будем записывать в виде W => max, а если минимизировать — W => min.

§ 2. Математические модели, основные принципы построения моделей

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

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

При построении модели реальное явление упрощается, схематизируется, и эта схема («макет» явления) описывается с помощью того или другого математического аппарата.

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

а) с той точностью, с которой нам нужно знать решение;

б) с той информацией, которой мы располагаем или можем приобрести.

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

Характерным для исследования операций является также повторное обращение к модели (после того, как первый тур расчетов уже проведен) для внесения в модель коррективов.

При построении математической модели может быть использован математический аппарат различной сложности. В самых простых случаях явление описывается простыми, алгебраическими уравнениями. В более сложных, когда требуется рассмотреть явление в динамике, применяются дифференциальные уравнения. В наиболее сложных случаях, когда развитие операции и ее исход зависят от большого числа сложно переплетающихся между собой случайных факторов, применяется метод статистического моделирования (Монте-Карло). Идею этого метода можно описать так: процесс развития операции, со всеми сопровождающими его случайностями, как бы «копируется», воспроизводится на машине (ЭВМ). В результате получается один экземпляр («реализация») случайного процесса развития операции со случайным ходом и исходом. Сама по себе одна такая реализация не дает оснований к выбору решения, но, получив множество таких реализаций и обработав их, находим средние характеристики процесса и получаем представление о том, как в среднем влияют на них условия задачи и элементы решения.

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

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

Наилучшие работы в области исследования операций основаны на совместном применении аналитических и статистических моделей. Аналитическая модель дает возможность в общих чертах разобраться, в явлении, наметить как бы «контур» основных закономерностей. Любые уточнения могут быть получены с помощью статистических моделей.

Имитационное моделирование применяется к процессам, в ход которых может время от времени вмешиваться человеческая воля. Человек (или группа людей), руководящий операцией, может, в зависимости от сложившейся обстановки, принимать те или другие решения. Затем приводится в действие математическая модель, которая показывает, какое ожидается изменение обстановки в ответ на это решение и к каким последствиям оно приведет спустя некоторое время. Следующее «текущее решение» принимается уже с учетом реальной новой обстановки и т. д. В результате многократного повторения такой процедуры руководитель постепенно «учится» принимать правильные решения — если не оптимальные, то почти оптимальные. Такие процедуры известны под названием «деловых игр».

§ 3. Прямые и обратные задачи. Детерминированные задачи и задачи в условиях неопределенности

Задачи исследования операций делятся на две категории: прямые и обратные. Прямые задачи отвечают на вопрос: что будет, если в заданных условиях мы примем какое-то решение хX? В частности, чему будет равен, при данном решении х, выбранный показатель эффективности W?

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

Обратные задачи отвечают на вопрос: как выбрать решение х для того, чтобы показатель эффективности W обратился в максимум?

Если число возможных вариантов решения, образующих множество X, мало, то можно вычислить величину W для каждого из них, сравнить между собой полученные значения и непосредственно указать один или несколько оптимальных вариантов, для которых W достигает максимума. Такой способ нахождения оптимального решения называется «простым перебором».

Запишем постановку задачи оптимизации решения (обратной задачи исследования операций) в общей форме:

Пусть имеется некоторая операция О, на успех которой мы можем в какой-то мере влиять, выбирая тем или другим способом решение х. Пусть эффективность операции характеризуется одним показателем W=> max.

Возьмем самый простой, так называемый «детерминированный» случай, когда все условия операции полностью известны заранее, т. е. не содержат неопределенности. Тогда все факторы, от которых зависит успех операции, делятся на две группы:

1) заданные, заранее известные факторы (условия выполнения операции), которые обозначим буквой ;

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

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

Показатель эффективности W зависит от обеих групп факторов. Запишем это в виде формулы:

W=W (, x) (3.1)

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

Будем считать, что вид зависимости (3.1) нам известен, т. е. прямая задача решена. Тогда обратная задача формулируется следующим образом.

При заданном комплексе условий найти такое решение х=х*, которое обращает показатель эффективности W в максимум.

Этот максимум обозначим:

W* = max {W (, х)}. (3.2)

Формула (3.2) читается так: W* есть максимальное значение W (, х), взятое по всем решениям, входящим в множество возможных решений X.

Метод поиска экстремума и связанного с ним оптимального решения х* должен всегда выбираться исходя из особенностей функции W и вида ограничений, накладываемых на решение. Например, если функция W линейно зависит от элементов решения х1, х2, …, а ограничения, налагаемые на х1, х2, …, имеют вид линейных равенств или неравенств, возникает классическая задача линейного программирования.

Для оптимизации управления многоэтапными операциями применяется метод динамического программирования.

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

Запишем зависимость показателя эффективности W от всех трех групп факторов:

W=W (, х,). (3.3)

Так как величина W зависит от неизвестных факторов, то даже при заданных и x она уже не может быть вычислена, т. е. остается неопределенной. Задача поиска оптимального решения тоже теряет определенность. Следовательно, при заданных условиях, с учетом неизвестных факторов, требуется найти такое решение хX, которое, по возможности, обеспечивает максимальное значение показателя эффективности W.

Наличие неопределенных факторов характерно для задачи о выборе решения в условиях неопределенности.

Типичной для крупномасштабной задачи исследования операций является многокритериальность — наличие ряда количественных показателей W1, W2,., одни из которых желательно обратить в максимум, другие — в минимум.

Рассмотрим пример такой задачи.

Организуется (или реорганизуется) работа промышленного предприятия. Под углом зрения какого критерия надо выбирать решение? С одной стороны, нам хотелось бы обратить в максимум валовой объем продукции V. Желательно также было бы получить максимальный чистый доход D. Что касается себестоимости S, то ее хотелось бы обратить в минимум, а производительность труда П — в максимум.

Раздел 2. Линейное программирование

§1. Задачи линейного программирования

В задачах, где выбор показателя эффективности (целевой функции) W определяется целевой направленностью операции, а ее условия известны заранее (детерминированный случай), показатель эффективности зависит только от двух групп параметров: заданных условий и элементов решения х, т. е.

W=W (, x).

В число заданных условий входят и ограничения, налагаемые на элементы решения. Пусть решение х представляет собой совокупность n элементов решения x1, x2, …, xn (иначе — n-мерный вектор):

х= (x1, x2, …, xn).

Требуется найти такие значения x1, x2, …, xn, которые обращают величину W в максимум или в минимум (т.е. «экстремум»).

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

Для задач линейного программирования характерно что:

а) показатель эффективности (целевая функция) W линейно зависит от элементов решения x1, x2, …, xn и

б) ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно x1, x2, …, xn.

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

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

1. Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно c1, c2, с3, с4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков — не менее b1 единиц; углеводов — не менее b2 единиц; жиров — не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице 4.1, где aij (i=1, 2, 3, 4; j=1, 2, 3) — какие-то определенные числа; первый индекс указывает номер продукта, второй — номер элемента (белки, углеводы, жиры).

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

Таблица 4.1

Составим математическую модель. Обозначим х1, х2, x3, x4 количества продуктов П1, П2, П3, П4, входящих в рацион. Показатель эффективности, который требуется минимизировать, — стоимость рациона (обозначим ее L); она линейно зависит от элементов решения х1, х2, x3, x4:

L = c1x1 + c2x2 + c3x3 + c4x4 (4.1)

или

L = ci xi (4.2)

i=1

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

a11×1 + a21×2 + a31×3 + a41×4? b1

a12×1 + a22×2 + a32×3 + a42×4? b2 (4.3)

a13×1 + a23×2 + a33×3 + a43×4? b3

Эти линейные неравенства представляют собой ограничения, накладывае-мые на элементы решения х1, х2, x3, x4.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х1, х2, x3, x4, чтобы они удовлетворяли ограничениям — неравенствам (3.3) и одновременно обращали в минимум линейную функцию этих переменных:

L = cixi min (4.4)

i=1

2. Задача о планировании производства. Предприятие производит изделия трех видов: U1, U2, U3. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не менее b1 единиц изделия U1, не менее b2 единиц изделия U2 и не менее b3 единиц изделия U3. План может быть перевыполнен, но в определенных границах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно 1, 2, 3, единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: S1, S2, S3, S4, причем запасы ограничены числами 1, 2, 3, 4 единиц каждого вида сырья. Укажем, какое количество сырья каждого вида идет на изготовление каждого вида изделий. Обозначим аij количество единиц сырья вида Si (i=l, 2, 3, 4), потребное на изготовление одной единицы изделия Uj (j = 1, 2, 3). Первый индекс у числа аij — вид сырья, второй — вид изделия. Значения аij сведены в таблицу 4.2.

Таблица 4.2

При реализации одно изделие U1 приносит предприятию прибыль c1, U2— прибыль с2, U3 — прибыль с3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Запишем задачу в форме задачи линейного программирования. Элементами решения будут х1, х2, х3, — количества единиц изделий U1, U2, U3, которые мы произведем. Обязательность выполнения планового задания запишется в виде трех ограничений-неравенств:

x1? b1, x2? b2, x3? b3 (4.5)

Отсутствие излишней продукции (затоваривания) даст нам еще три ограничения-неравенства:

x1? 1, x2? 2, x3? 3 (4.6)

Кроме того, нам должно хватить сырья. Соответственно четырем видам сырья будем иметь четыре ограничения-неравенства:

a11×1 + a21×2 + a31×3? 1

a12×1 + a22×2 + a32×3? 2 (4.7)

a13×1 + a23×2 + a33×3? 3

a14×1 + a24×2 + a34×3? 4

Прибыль, приносимая планом (х1, х2, х3), будет равна

L = c1x1 + c2x2 + c3x3 max (4.8)

3. Задача о загрузке оборудования. Ткацкая фабрика располагает двумя видами станков, из них n1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: Т1, Т2, T3, но с разной производительностью. Данные aij производительности станков даны в таблице 4.3 (первый индекс — тип станка, второй — вид ткани).

Таблица 4.3

Каждый метр ткани вида T1 приносит фабрике доход с1, вида Т2 — доход с2, T3 — доход С3.

Фабрике предписан план, согласно которому она должна производить в месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани T3; количество метров каждого вида ткани не должно превышать соответственно 1, 2, 3 метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, T3, чтобы суммарный месячный доход был максимален.

В этой задаче элементы решения — не количества тканей каждого вида, а количества станков типов 1 и 2, занятых производством тканей каждого вида. Здесь удобно обозначить элементы решения буквами х с двумя индексами (первый — тип станка, второй — вид ткани). Всего будет шесть элементов решения:

x11×12×13 (4.9)

x21×22×23

Здесь x11 — количество станков типа 1, занятых изготовлением ткани T1, x12 — количество станков типа 1, занятых изготовлением ткани T2, и т. д.

Запишем условия-ограничения, наложенные на элементы решения хij. Прежде всего, обеспечим выполнение плана. Это даст нам три неравенства-ограничения:

a11×11 + a21×21? b1

a12×12 + a22×22? b2 (4.10)

a13×13 + a23×23? b3

После этого ограничим перевыполнение плана; это даст нам еще три неравенства-ограничения:

a11×11 + a21×21? 1

a12×12 + a22×22? 2 (4.11)

a13×13 + a23×23? 3

Запишем ограничения, связанные с наличием оборудования и его полной загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 — N2. Отсюда еще два условия — на этот раз равенства:

x11 + x12 + x13 = N1 (4.12)

x21 + x22 + x23 = N2

Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани T1, произведенное всеми станками, будет равно а11×11+a21×21 и принесет доход c1(a11×11+а21×21). Рассуждая аналогично, найдем суммарный доход фабрики за месяц при плане (4.9):

L = c1(a11×11+а21×21) + c2(a12×12+а22×22) + c3(a13×13+а23×23) или

3 2

L = cj aijxij (4.14)

j=1 i=1

Эта линейная функция шести аргументов стремится к максимуму:

L max

В этой задаче линейного программирования требуется найти такие неотрицательные значения переменных x11, x12, …, x23, которые, во-первых, удовлетворяли бы ограничениям-неравенствам (4.10), (4.11), во-вторых — ограничениям-равенствам (4.12) и, наконец, обращали бы в максимум линейную функцию этих переменных (4.13). В этой задаче линейного программирования шесть ограничений-неравенств и два ограничения-равенства.

4. Задача о снабжении сырьем. Имеются три промышленных предприятия: П1, П2, П3, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия равны соответственно a1, а2, a3 единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких-то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием Пi с базы Бi обходится предприятию в сij рублей (первый индекс — номер предприятия, второй — номер базы, см. таблицу 4.4).

Таблица 4.4

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б1, Б2, Б3, Б4, Б5 могут дать не более b1, b2, b3, b4, b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

Обозначим xij количество сырья, получаемое i-м предприятием с j-й базы. Всего план будет состоять из 15 элементов решения:

x11×12×13×14×15

x21×22×23×24×25 (4.15)

x31×32×33×34×35

Введем ограничения по потребностям. Они состоят в том, что каждое предприятие получит нужное ему количество сырья (ровно столько, сколько ему требуется):

x11 + x12 + x13 + x14 + x15 = a1

x21 + x22 + x23 + x24 + x25 = a2 (4.16)

x31 + x32 + x33 + x34 + x35 = a3

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

x11 + x21 + x31? b1

x12 + x22 + x32? b2

x13 + x23 + x33? b3 (4.17)

x14 + x24 + x34? b4

x15 + x25 + x35? b5

Запишем суммарные расходы на сырье, которые требуется минимизировать. С учетом данных таблицы 4.4 получим (пользуясь знаком двойной суммы):

3 5

L = cijxij min (4.18)

i=1 j=1

§2. Основная задача линейного программирования (ОЗЛП)

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формулируется так: найти неотрицательные значения переменных x1, x2, …, xn, которые удовлетворяли бы условиям-равенствам

a11×1 + a21×2 + … + an1xn = b1

a21×1 + a22×2 + … + a2nx2 = b2 (5.1)

…

am1x1 + am2x2 + … + amnxn = bm

и обращали бы в максимум линейную функцию этих переменных:

L = c1x1 + c2x2 + … + cnxn max (5.2)

Пусть требуется найти неотрицательные значения переменных х1, x2, x3, удовлетворяющие ограничениям-неравенствам

3x1 + 2×2 — x3? 4

x1 — 2×2 + 3×3? 10 (5.3)

и обращающие в максимум линейную функцию от этих переменных:

L = 4×1 — x2 + 2×3 max (5.4)

Приведем условия (5.3) к стандартной форме, так, чтобы знак неравенства был, а справа стоял нуль. Получим:

3x1 + 2×2 — x3 — 4? 0

— x1 + 2×2 — 3×3 + 10? 0 (5.5)

Обозначим левые части неравенств (5.5) соответственно через y1 и y2:

y1 = 3×1 + 2×2 — x3 — 4

y2 = - x1 + 2×2 — 3×3 + 10 (5.6)

Из условий (5.5) и (5.6) видно, что новые переменные y1 и y2 также должны быть неотрицательными.

Требуется найти неотрицательные значения переменных х1, x2, x3, y1, y2 такие, чтобы они удовлетворяли условиям-равенствам (5.6) и обращали в максимум линейную функцию этих переменных. Перед нами — основная задача линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями-неравенствами (5.3) «куплен» ценой увеличения числа переменных на два (число неравенств).

Всякая задача линейного программирования может быть сведена к стандартной форме ОЗЛП.

§3. Графический метод решения задач линейного программирования

Рассмотрим метод графического решения ЗЛП на примере задачи технического контроля.

Задача технического контроля. В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Норма выработки ОТК за 8 — часовой рабочий день составляет не менее 1800 изделий. Контролер разряда 1 проверяет 25 изделий в час, причем не ошибается в 98% случаев. Контролер разряда 2 проверяет 15 изделий в час; его точность составляет 95%.

Заработная плата контролера разряда 1 равна 4 руб. в час, контролер разряда 2 получает 3 руб. в час. При каждой ошибке контролера фирма несет убыток в размере 2 руб. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2.

Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальны.

Разработка модели. Пусть x1 и x2 обозначают количество контролеров разрядов 1 и 2 соответственно. Число контролеров каждого разряда ограничено, т. е. имеются следующие ограничения:

x1 8 (разряд 1),

x210 (разряд 2).

Ежедневно необходимо проверять не менее 1800 изделий. Поэтому выполняется неравенство

8*25*x1+8*15*x2=200*x1+120*x2 1800,

или 5*x1+3*x245.

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

1) зарплату контролеров и

2) убытки, вызванные ошибками контролеров.

Расходы на одного контролера разряда 1 составляют

4 руб. +2*25*0,02=5 руб./ч.

Расходы на одного контролера разряда 2 равны

3 руб. +2*15*0,05=4,50 руб./ч.

Следовательно, минимизирующая целевая функция, выражающая ежедневные расходы на контроль, имеет вид

z=8*(5*x1+4,5*x2)= 40×1+36*x2min.

Можно сформулировать следующую задачу:

минимизировать z=40*x1+36*x2

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

x18, x210,

5*x1+3*x245,

x10, x20.

В этой задаче требуется найти значения переменных x1 и x2, удовлетворяющие всем ограничениям и обеспечивающие минимальное значение целевой функции. В качестве первого шага решения следует определить все возможные неотрицательные значения переменных x1 и x2, которые удовлетворяют ограничениям. Например, координаты точки x1=8 и x2=10 положительны и для этой точки выполняются все ограничения. Такая точка называется допустимым решением. Множество всех допустимых решений называется допустимой областью. Решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области. Лучшее допустимое решение задачи ЛП называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, минимизирующее целевую функцию 40*x1+36*x2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

Для изображения допустимой области следует начертить графики всех ограничений. Все допустимые решения лежат в первом квадранте, поскольку значения переменных неотрицательны. В силу ограничения 5*x1+3*x245 все допустимые решения (x1, x2) задачи располагаются по одну сторону от прямой, описываемой уравнением 5*x1+3*x2=45. Нужную полуплоскость можно найти, проверив, удовлетворяет ли начало координат рассматриваемому ограничению. Прямую 5×1+3*x2=45 удобно провести, соединяя пару подходящих точек (например, x1=0, x2=15 и x1=9, x2=0).

Поскольку начало координат не удовлетворяет ограничению, нужная полуплоскость отмечена стрелкой, направленной перпендикулярно прямой. Аналогичным образом представлены ограничения x1 8 и x2 10.

На рисунке 6.1 допустимая область (АВС) заштрихована. Ясно, что в допустимой области содержится бесконечное число допустимых точек. Нужно найти допустимую точку с наименьшим значением Z.

Если заранее зафиксировать значение целевой функции Z=40*x1+36*x2, то соответствующие ему точки будут лежать на некоторой прямой. При изменении величины Z эта прямая подвергается параллельному переносу. Рассмотрим прямые, соответствующие различным значениям Z, имеющие с допустимой областью хотя бы одну общую точку. Начальное значение Z положим равным 600. При приближении прямой к началу координат значение Z уменьшается. Если прямая имеет хотя бы одну общую точку с допустимой областью АВС, ее можно смещать в направлении начала координат. Ясно, что для прямой, проходящей через угловую точку, А с координатами х1=8, х2=1.6, дальнейшее движение невозможно. Точка, А представляет собой наилучшую допустимую точку, соответствующую наименьшему значению Z, равному 377.6. Следовательно, х1=8, х2=1.6 — оптимальное решение и Z=377.6 — оптимальное значение рассматриваемой задачи линейного программирования.

Таким образом, при оптимальном режиме работы ОТК необходимо использовать восемь контролеров разряда 1 и 1.6 контролеров разряда 2. Дробное значение х2=1.6 соответствует использованию одного из контролеров разряда 2 в течение неполного рабочего дня. При недопустимости неполной загрузки контролеров дробное значение обычно округляют, получая приближенное оптимальное целочисленное решение х1=8, х2=2.

Рисунок 6.1 — Графическое решение задачи линейного программирования

§4. Решение задач линейного программирования симплекс-методом

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

Постановка задачи Для изготовления n видов изделий И1, И2, …, Иn необходимы ресурсы m видов: трудовые, материальные, финансовые и др. Известно необходимое количество отдельного i-ro ресурса для изготовления каждого j-ro изделия. Назовем эту величину нормой расхода. Пусть определено количество каждого вида ресурса, которым предприятие располагает в данный момент. Известна прибыль Пj, получаемая предприятием от изготовления каждого j-ro изделия. Требуется определить, какие изделия и в каком количестве должно изготавливать предприятие, чтобы обеспечить получение максимальной прибыли. Необходимая исходная информация представлена в таблице 7.1.

Таблица 7.1

Построение математической модели.

Количество изделий j-ro наименования, которое может производить предприятие, обозначим через хj. Зная количество каждого вида i-го ресурса для изготовления отдельного j-ro типа изделия — норму расхода и количество каждого i-го ресурса (таблица 1), можно записать следующую систему неравенств:

3x1 + 5×2 + 2×3 + 7×4? 15

4x1 + 3×2 + 3×3 + 5×4? 9 (7.1)

5x1 + 6×2 + 4×3 + 8×4? 30

Полученную систему можно представить в виде совокупности равенств, если в каждое из неравенств ввести фиктивные изделия (дополнительные переменные) х5, х6, х7, при изготовлении которых используют каждый оставшийся вид ресурса.

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

3x1 + 5×2 + 2×3 + 7×4 + x5 = 15

4x1 + 3×2 + 3×3 + 5×4 + x6 = 9 (7.2)

5x1 + 6×2 + 4×3 + 8×4 + x7 = 30

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

Критерий оптимизации (суммарную величину прибыли) можно тогда представить так:

Y = 40×1 + 50×2 + 30×3 + 20×4 + 0×5 + 0×6 + 0×7 (7.3)

Граничные условия будут записаны следующим образом:

xj? 0 (j =1, 2, …, 7) (7.4)

Совокупность системы ограничений (7.2), целевой функций (7.3) и граничных условий (7.4) образует математическую модель данной задачи.

Нахождение базисного решения.

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

В данной задаче для определения базиса требуется взять m неизвестных по числу уравнений в системе (7.2), желательно наиболее редко встречающиеся в ней. В нашей совокупности уравнений (m — 3) это х5, х6, х7, которые и выражаем через оставшиеся неизвестные х1, х2, х3, х4.

Систему уравнений необходимо записать в таком виде:

х5 = 15 — (Зх1 + 5×2 + 2×3 + 7×4)

х6 = 9 — (4x1 + 3×2 + 3×3 + 5×4) (5)

х7 = 30 — (5×1 + 6×2 + 4×3 + 8×4)

Переменные, находящиеся в левой части системы уравнений, называются базисными (основными), а находящиеся справа — небазисными (не основными). Для определения значений базисных переменных х5, х6, х7 необходимо приравнять к нулю небазисные х1, х2, х3, х4 и подставить их в систему уравнений (5). Полученное таким образом решение называется базисным. Оно будет выглядеть следующим образом:

(х1, х2, х3, х4, х5, х6, х7)

(0, 0, 0, 0, 15, 9, 30).

После определения начального базиса можно переходить непосредственно к использованию алгоритма симплекс-метода.

Решение задачи симплекс-методом.

1. Заполнение исходной симплекс-таблицы.

В соответствии с полученной системой уравнений и критерием оптимизации заполняем исходную симплекс-таблицу (таблица 7.2).

Таблица 7.2

2. Проверка базисного решения на оптимальность.

Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) — последняя строка таблицы 7.2.

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

3. Проверка задачи на наличие решения.

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

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

Наиболее простой и чаще всего используемый способ состоит в выборе той небазисной переменной, которой соответствует наибольший положительный коэффициент в целевой функции. В нашей задаче это переменная х2 (наибольший положительный коэффициент равен 50). Значит, х2 необходимо ввести в базис.

5. Определение базисной переменной, которая должна быть выведена из базиса.

Для всех положительных коэффициентов при вводимой в базис переменной в системе уравнений определяется отношение свободного члена уравнения к коэффициенту при вводимой в базис переменной. Для нашей задачи это будут следующие отношения: 15/5 = 3; 9/3 = 3; 30/6 = 5.

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

6. Представление новой базисной переменной через небазисные.

Строится новая симплекс-таблица (таблица 7.3). Отмечается звездочкой строка и столбец в предыдущей симплекс-таблице (таблица 7.2), соответственно для выводимой из базиса и для вводимой в него переменной. Коэффициент, находящийся на пересечении строки и столбца, отмеченных звездочками, называется разрешающим и помечается звездочкой (таблица 7.2). Все коэффициенты строки, отмеченной звездочкой, делятся на разрешающий элемент, а результаты расчета заносятся в новую симплекс-таблицу. В нашей задаче на первой итерации разрешающий элемент равен 5 (таблица 7.2).

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

7. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных.

Для этого коэффициенты в новой таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце при новой базисной переменной в новой таблице появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов второй строки в новой таблица 7.3 умножаем коэффициенты при новой базисной переменной х2 (таблица 7.3) на число -3, складываем с соответствующими коэффициентами второй строки предыдущей симплекс-таблицы (таблица 7.2) и результаты расчета заносим во вторую строку новой таблицы (таблица 7.3).

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

Таблица 7.3

Поскольку в последней строке таблицы 7.3 в целевой функции не все коэффициенты при небазисных переменных неположительны, то решение не оптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица (таблица 7.4). Цикл расчета начинается с этапа 2 и проводится до тех пор, пока не будет найдено оптимальное решение.

В качестве вводимой в базис небазисной переменной берем х3 (можно x1) как имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец х3. В качестве выводимой из базиса переменной берем х6, так как для нее частное от деления свободного члена на соответствующий коэффициент минимально. Разрешающий множитель равен 9/5.

Результаты расчета представлены в таблице 7.4.

Таблица 7.4

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

(х1, х2, х3, х4, х5, х6, х7)

(0, 3, 0, 0, 0, 0, 12).

Из полученного решения видно, что изделия ИI, И3 и И4 предприятие изготавливать не должно. Цифра в переменной x2 определяет изделие, планируемое для изготовления, следовательно, предприятие будет производить только второе изделие в количестве 3 единиц.

Оптимальное распределение ресурсов обеспечит получение максимальной прибыли Y, которая составит 150 единиц.

При этом материальные и трудовые ресурсы будут задействованы полностью, а финансовые — недоиспользованы на 12 единиц.

§5. Транспортная задача. Методы нахождения начального решения транспортной задачи

Рассмотрим одну из задач линейного программирования — так называемую «транспортную задачу». Она ставится следующим образом: имеются m пунктов отправления (ПО) А1, A2, …, Am, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, a2, …, am единиц. Имеются n пунктов назначения (ПН) B1, В2,…, Вn, подавших заявки соответственно па b1, b2, …, bn единиц груза. Сумма всех заявок равна сумме всех запасов:

m n

ai = bj (8.1)

i = 1 j = 1

Известны стоимости сij перевозки единицы груза от каждого пункта отправления Аi, до каждого пункта назначения Bj; (i =1, 2,…, m; j = 1, 2,…, n). Все числа сij, образующие прямоугольную таблицу (матрицу), заданы:

с11 с12. .. с1n

с21 с22. .. с2n (8.2)

.. .. .. .. .. .. ... .

сm1 сm2. .. сmn

Коротко матрицу (8.2) будем обозначать (сij).

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

Требуется составить такой план перевозок (откуда, куда и сколько единиц везти), чтобы все заявки были выполнены, а общая стоимость всех перевозок минимальна.

Поставим эту задачу как задачу линейного программирования. Обозначим xij, — количество единиц груза, отправляемого из i-го ПО Ai, в j-й ПН Вj. Неотрицательные переменные xij тоже можно записать в виде матрицы

x11×12. .. x1n

x21×22. .. x2n (8.3)

.. .. .. .. .. .. ... .

xm1 xm2. .. xmn

которую мы будем коротко обозначать (xij). Совокупность чисел (xij) (8.3) мы будем называть «планом перевозок», а сами величины xij — «перевозками». Эти неотрицательные переменные должны удовлетворять следующим условиям.

1. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте. Это даст нам m условий-равенств:

x11 + x12 +. .. + x1n = a1

x21 + x22 +. .. + x2n = a2 (8.4)

.. .. .. .. .. .. .. .. ... .

xm1 + xm2 +. .. + xmn = am

2. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом. Это даст нам n условий-равенств:

x11 + x21 +. .. + xm1 = b1

x12 + x22 +. .. + xm2 = b2 (8.5)

.. .. .. .. .. .. .. .. ... .

x1n + x2n +. .. + xmn = bn

3. Суммарная стоимость всех перевозок, то есть сумма величин хij, умноженных на соответствующие стоимости сij, должна быть минимальной:

m n

Y = Ci, j Xi, j min (8.6)

i = 1 j = 1

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, т. е. по всем парам ПО — ПН.

Перед нами — задача линейного программирования с условиями-равенствами (8.4), (8.5) и минимизируемой линейной функцией (8.6). Особенностью этой задачи является то, что все коэффициенты в условиях (8.4), (8.5) равны единице.

Условия-равенства (8.4), (8.5) не являются линейно независимыми, так как их правые части связаны условием (8.1). Число линейно независимых среди уравнений (8.4), (8.5) равно не m + n (числу уравнений), а m + n — 1. Общее число переменных xij, в нашей задаче равно m * n; как бы ни разрешать уравнения (8.4), (8.5), число базисных переменных будет равно m + n — 1, а число свободных переменных

k = mn — (m + n— 1) = (m — 1) (n — 1).

Для оптимального плана по крайней мере (m — 1) (n — 1) перевозок должны быть равны нулю (из соответствующих ПО в соответствующие ПН ничего не перевозится).

Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (8.4), (8.5) (все заявки удовлетворены, все запасы исчерпаны). Допустимый план будем называть опорным, если в нем отличны от нуля не более m + n — 1 базисных перевозок, а остальные перевозки равны нулю. План (xij) будем называть оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок (Y = min).

Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость сij перевозки единицы груза из Ai, в Вj" а центр клетки оставим свободным, чтобы помещать в нее саму перевозку xij. Клетку таблицы, соответствующую пунктам Ai, Bj, будем кратко обозначать (i, j).

Пример транспортной таблицы, где приведены условия задачи и стоимости перевозок, но нет еще самих перевозок, дан в таблице 10.1, где m = 4, n = 5.

Таблица 8.1

Cоставим опорный план, применив «метод северо-западного угла». Заполнение транспортной таблицы начнем с левого верхнего («северо-западного») угла. Пункт В1 подал заявку па 18 единиц груза; удовлетворим ее из запасов пункта A1. После этого в нем остается еще 30—18=12 единиц груза; отдадим их пункту В2. Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта А2 и т. д. Рассуждая точно таким же образом, заполним до конца перевозками xij транспортную таблицу (таблица 8.2).

Таблица 8.2

Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу — заявке соответствующего пункта назначения. Значит, все в порядке — все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 128, стоящим в правом нижнем углу таблицы).

В таблицах будем проставлять отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем «свободными». Проверим, является ли план перевозок, данный в таблице 8.2, опорным. Число свободных клеток с нулевыми перевозками в таблице 8.2 равно как раз (m -1)(n — 1) = 3 * 4 = 12, так что план — опорный.

Этот план можно улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12, но зато увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6 (таблица 8.3).

Таблица 8.3

Чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных — свободной. Сколько единиц груза можем мы перенести по циклу (2.4) -> (3.4) -> (3.3) -> (2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая — в четных? Очевидно, не больше, чем 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Очевидно, в результате циклического переноса допустимый план остается допустимым — баланс запасов и заявок не нарушается. Произведем этот перенос и запишем новый, улучшенный план перевозок в таблице 8.4.

Таблица 8.4

Общая стоимость плана, показанного в таблице 8.3, равна

L1 = 18 * 13 + 12 * 7 + 15 * 8+ 33 * 12 +9 * 10 + 11 * 8 + 4 * 10 + 26 * 15=1442.

Общая стоимость плана, показанного в таблице 8.4, равна

L2 = 18*13 +12*7 +15*8 + 22*12 +11*6 +20*10+4*10+26*15 =1398.

Таким образом, нам удалось уменьшить стоимость перевозок на 1442 — 1398 == 44 единицы. Будем считать алгебраическую сумму стоимостей, стоящих в вершинах цикла, со знаком плюс, если перевозки в этой вершине увеличиваются, и со знаком минус — если уменьшаются (так называемая «цена цикла»), в данном случае равна: 6—8+10—12 = — 4. Значит, при переносе одной единицы груза по этому циклу стоимость перевозок уменьшается на четыре. А мы их перенесли целых 11; значит, стоимость должна была уменьшиться на 11*4=44 единицы, что и произошло.

Значит, весь секрет оптимизации плана перевозок в том, чтобы переносить («перебрасывать») перевозки по циклам, имеющим отрицательную цену.

В теории линейного программирования доказывается, что при опорном плане для каждой свободной клетки транспортной таблицы существует цикл, и притом единственный, одна вершина которого (первая) лежит в данной свободной клетке, а остальные — в базисных плетках. Поэтому, отыскивая «выгодные» циклы с отрицательной ценой, мы должны смотреть, — нет ли в таблице «дешевых» свободных клеток. Если такая клетка есть, нужно для нее найти цикл, вычислить его цену и, если она будет отрицательной, перенести по этому циклу столько единиц груза, сколько будет возможно (без того, чтобы какие-то перевозки сделать отрицательными). При этом данная свободная клетка становится базисной, а какая-то из бывших базисных — свободной. Очевидно, это равносильно «переразрешению» системы уравнений относительно других базисных переменных, но делается это гораздо легче.

Попробуем еще раз улучшить план, приведенный в таблице 8.4. Например, если улучшить план увеличив перевозки в клетке (1.5) со стоимостью 5 и уменьшив в других клетках. В таблице 8.4 найдем цикл, первая вершина которого лежит в свободной клетке (1.5), а остальные — все в базисных клетках.

Таблица 8.5

Это последовательность клеток (1.5) ->(4.5) ->(4.4) ->(2.4) ->(2.2) ->(1.2) (и замыкая цикл, снова возвращаемся в (1.5)). Нечетные вершины цикла отмечены плюсом — это значит, что перевозки в этих клетках увеличиваются: четные — знаком минус (перевозки уменьшаются). Цикл показан стрелками в таблице 8.4.

Подсчитаем цену этого цикла. Она равна 5—15+ 10—6+8—7= —5. Так как цена цикла отрицательна, то переброска перевозок по этому циклу выгодна. По этому циклу мы можем перебросить 11 единиц. Это определяется наименьшей перевозкой, стоящей в отрицательной вершине цикла. Умножая 11 на цену цикла —5, получим, что за счет переброски 11 единиц груза по данному циклу мы еще уменьшим стоимость перевозок на 55.

Таким образом, разыскивая в транспортной таблице свободные клетки с отрицательной ценой цикла и перебрасывая по этому циклу наибольшее возможное количество груза, мы будем все уменьшать и уменьшать стоимость перевозок. Бесконечно уменьшаться она не может (она никак не может стать меньше нуля!), значит, рано или поздно мы придем к оптимальному плану. Для такого плана уже не остается ни одной свободной клетки с отрицательной ценой цикла. Это — признак того, что оптимальное решение найдено.

В рассмотренной задаче сумма объемов ресурсов поставщиков равна сумме объемов ресурсов потребителей. Однако в некоторых случаях такое равенство отсутствует.