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

Широкий класс задач экономики и социологии труда сводится при их экономико-математическом моделировании к линейным и нелинейным оптимизационным моделям. Рамки данного учебного пособия не позволяют детально остановиться на всех таких задачах; практически за этими рамками остаются задачи нелинейного, целочисленного, динамического программирования, задачи многокритериальной оптимизации и имитационного моделирования и др. (некоторые из этих задач отражены в учебных изданиях [6], [7], [11], [15]). Поэтому рассмотрим лишь некоторые типовые оптимизационные задачи экономики труда.

Транспортная задача

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

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

Есть т пунктов хранения (производства) однородного продукта, на каждом из которых имеется а-, единиц продукта (i = l,m). Эти

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

Имеется п пунктов потребления продукта, каждому из которых требуется bj единиц продукта (у = 1, и). Назовем эти пункты потребителями, а величину bj — мощностью потребителя.

Известны также расходы на перевозку единицы продукта от /-го поставщика у-му потребителю, которые будем обозначать как с,у. Таким образом, известна матрица транспортных расходов С = (с,у) размерности т * п.

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

Будем рассматривать случай, когда выполняется условие баланса:

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

Пусть Ху — объем перевозок от /-го поставщика у-му потребителю. Тогда целевая функция задачи будет иметь вид:

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

Условия (2.20) определяют полный вывоз продукта от всех поставщиков, а условия (2.21) означают полное удовлетворение мощностей всех потребителей.

Транспортная задача (2.19)—(2.22) является задачей линейного программирования и может быть решена симплексным методом.

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

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

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

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

Если баланс (2.18) не выполняется, то ограничения (2.20) или (2.21) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного поставщика, если в неравенства превращаются ограничения (2.21), или фиктивного потребителя, если в неравенства превращаются ограничения (2.20).

Следует отметить, что при условии выполнения баланса (2.18) ранг системы линейных уравнений (2.20), (2.21) равен т + п - 1. Таким образом, из общего числа неизвестных т + п базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной, например, в приведенной ниже табл. 2.6, будет занято ровно т + п - 1 клеток, которые назовем базисными в отличие от остальных, свободных, клеток; занятые клетки отмечаются диагональной чертой.

Чтобы оценить оптимальность распределения, для всех клеток (/; j) матрицы перевозок определяются их оценки, которые обозначим через Ау, по формуле:

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

Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой. Если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой. Например, для распределения, представленного в табл. 2.6, такой клеткой может служить клетка (3; 2).

Для выбранной клетки строится замкнутая линия {контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть только горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол (нельзя рассматривать как вершины клетки, в которых горизонтальные и вертикальные отрезки контура пересекаются). Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура расставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке. Вид контура может быть самым разнообразным (см., например, контур, представленный в табл. 2.6).

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

> Пример 2.8. Решим методом потенциалов закрытую транспортную задачу, заданную в табл. 2.6, в которую уже внесено некоторое допустимое базисное распределение. Суммарные транспортные расходы при этом плане перевозок составляют:

Таблица 2.6

Потенциалы по формуле (2.23) находим следующим образом: задавая, например, и = 0, находим по клетке (1; 1) Vi = 3, по клетке (1; 2) находим vj = 2, а по клетке (1; 4) V4 = 1; затем по клетке (2; 1) находим «2 ⁼ 1 и по клетке (2; 3) V3 = 2; наконец, по клетке (3; 3) находим «3 = -2.

Матрица оценок клеток для этого плана рассчитывается по формуле (2.24):

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

Наименьшая поставка в вершине контура со знаком «-» равна 20, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком «-» на 20 и увеличив поставки в клетках со знаком «+» также на 20. При этом клетка (3; 2) заполняется, а клетка (3; 3) освобождается. Новый план представлен в табл. 2.7. Соответствующие значения потенциалов показаны в последних столбце и строке.

Таблица 2.7

Матрица оценок клеток этого распределения не содержит отрицательных значений:

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

Наличие нулевой оценки незанятой клетки (3; 1) свидетельствует о том, что оптимальный план не является единственным. Можно отметить также, что применяя для начального распределения в этой транспортной задаче метод наименьших стоимостей (см., например, § 3.2 [15]), мы сразу же получили бы оптимальное распределение, представленное в табл. 2.7. ?