Модели

т — количество используемых производственных ресурсов (например, производственные мощности,

сырье, рабочая сила); aij — объем затрат i-го ресурса на выпуск единицы j-й продукции; с — прибыль от выпуска и реализации единицы j-го продукта; bi — количество имеющегося i-го ресурса; Xj — объем выпуска j-го продукта.

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

п

? с,X: -» шах, ...

1

Здесь (1) — целевая функция (максимум прибыли);

— система специальных ограничений (constraint) на объем фактически имеющихся ресурсов;

— система общих ограничений (на неотрицательность переменных); xj — переменная (variable).

Задача (1)—(3) называется задачей линейного программирования в стандартной форме на максимум.

(5)

Вектор х = (xi, x2, ..., xn), компоненты х. которого удовлетворяют ограничениям (2) и (3) (или (5) и (6) в

задаче на минимум), называется допустимым решением или допустимым планом задачи ЛП. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение задачи ЛП, на котором целевая функция (1) (или (3) в задаче на минимум)

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

называется двойственной задачей ЛП. Двойственной к задаче ЛП (1)—(3) является задача

І ЬІУІ -> rnin, (7)

т

/?і аи У І - cj» У =1, •••>«, (8)

У І ^ 0, /=1,..., т. (9)

Соответственно, двойственной к задаче ЛП (7)—(9) является задача (1)—(3). Каждой переменной (специальному ограничению) исходной задачи соответствует специальное ограничение (переменная) двойственной задачи.

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

*

Компонента Уі оптимального решения двойственной задачи (7)—(9) называется двойственной оценкой

n

У a.x. < b,

и >j j \'

(Dual Value) ограничения j 1 исходной задачи ЛП.

n

У c-xj

Пусть j = max ( j=1 ), где х. — компонента допустимого решения задачи (1)—(3). Тогда при выполнении условий невырожденности оптимального решения имеют место следующие соотношения: Д(Р . • _ ,

Изменим значение правой части bi одного основного ограничения (RHS) исходной задачи ЛП.

Пусть Ь — минимальное значение правой части основного ограничения, при котором решение у*

двойственной задачи не изменится. Тогда величину Ь называют нижней границей (Lower Bound) устойчивости по правой части ограничения.

Ь"

Пусть

максимальное значение правой части основного ограничения, при котором решение у*

Ь"

двойственной задачи не изменится. Тогда величину i называют верхней границей (Upper Bound) устойчивости по правой части ограничения.

Изменим значение одного коэффициента с- целевой функции исходной задачи ЛП.

t

С ,

Пусть

минимальное значение коэффициента целевой функции, при котором оптимальное решение

х* исходной задачи не изменится. Тогда величину 1 называют нижней границей устойчивости по

коэффициенту целевой функции.

tt

c,

Пусть

максимальное значение коэффициента целевой функции, при котором оптимальное

TT c j

решение х* исходной задачи не изменится. Тогда величину "1 называют верхней границей устойчивости по коэффициенту целевой функции.

Примеры

Пример 1. Сколько производить?

Предприятие располагает ресурсами сырья и рабочей силы, необходимыми для производства двух видов продукции. Затраты ресурсов на изготовление одной тонны каждого продукта, прибыль, получаемая предприятием от реализации тонны продукта, а также запасы ресурсов указаны в следующей таблице:\r\n Расход ресурса Запас ресурса\r\n на продукт 1 на продукт 2 \r\nСырье, т 3 5 120\r\nТрудозатраты, ч 14 12 400\r\nПрибыль на единицу продукта, тыс.

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

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

Какова максимальная прибыль?

На сколько возрастет максимальная прибыль, если запасы сырья увеличатся на 1 т?

На сколько возрастет максимальная прибыль, если допустимый объем трудозатрат увеличится с 400 до 500 ч?

Решение. Пусть хі — объем выпуска продукта 1 в тоннах, х2 — объем выпуска продукта 2 в тоннах.

Тогда задача может быть описана в виде следующей модели линейного программирования: 30х, + 35*2 -» шах, 3х1 + 5X2 < 120, 14*! + 12x2 < 400, > 0, Х2 > 0.

Используя пакет РОМ for WINDOWS (далее - POMWIN), исходную информацию для решения этой задачи можно представить в виде следующей таблицы:\r\n Продукт 1 Продукт 2 Знак ограничения RHS\r\nMaximize 30 35 \r\nСырье 3 5 <= 120\r\nТрудозатраты 14 12 <= 400\r\nРешая эту задачу, получаем следующий результат:

\r\n Продукт 1 Продукт 2 RHS Двойственная оценка (Dual)\r\nMaximize 30 35 \r\nСырье 3 5 <= 120 3,82\r\nТрудозатраты 14 12 <= 400 1,32\r\nРешение (Solution) 16,47 14,12 988,24 \r\nВ нижней строке указан объем выпуска каждого продукта, удовлетворяющий ограничениям на ресурсы и обеспечивающий максимальную прибыль. Величина 988,24 — максимальное значение целевой функции.

Чтобы обеспечить максимальную прибыль, следует производить 16,47 т продукта 1 и 14,12 т продукта 2.

Максимальная прибыль равна 988,24 тыс. руб.

В правом столбце таблицы указаны двойственные оценки для каждого ограничения. Так, величина 3,82 показывает, что при увеличении запаса сырья на 1 т (до 121) максимальное значение целевой функции для нового оптимального плана увеличится по сравнению с 988,24 на 3,82 тыс. руб. Аналогично можно интерпретировать значение двойственной оценки 1,32 для второго ресурса.

Следующая таблица содержит дополнительную информацию, предоставляемую пакетом POMWIN:\r\nVariable Value Reduced Cost Original Value Lower Bound Цррег Bound\r\nПродукт 1 16,47 0 30 21 40,83\r\nПродукт 2 14,12 0 35 25,71 50\r\nConstraint Dual Value Slack/Surplus Original Value Lower Bound Upper Bound\r\nСырье 3,82 0 120 85,71 166,66\r\nТрудоза-траты 1,32 • 0 400 288 560\r\nДва правых столбца таблицы — границы устойчивости по значениям коэффициентов целевой функции (верхняя часть таблицы) и правых частей ограничений (нижняя часть).

Так, в случае если прибыль, получаемая от реализации 1 т продукта 1, изменится, но останется в пределах от 21 до 40,83, количество продукта 1 в оптимальном плане не изменится.

В случае если запас сырья изменится, но останется в пределах от 85,71 до 166,66, двойственная оценка этого ресурса не изменится.

Соответственно, если допустимый объем трудозатрат изменится в пределах от 288 до 560 ч, двойственная оценка этого ресурса не изменится.

Если допустимый объем трудозатрат увеличится с 400 до 500 ч, то максимальная прибыль увеличится на 132 тыс.

Ответы: 1. 16,47 т. 2. 14,12 т. 3. 988,24 тыс. руб.

4. На 3,82 тыс. руб. 5. На 132 тыс. руб.

Пример 2. Производить или покупать?

Фирма производит два типа химикатов. На предстоящий месяц она заключила контракт на поставку следующего количества этих химикатов: \r\nТип химикатов Продажи по контракту, т\r\n1 100\r\n2 120\r\nПроизводство фирмы ограничено ресурсом времени работы двух химических реакторов. Каждый тип химикатов должен быть обработан сначала в реакторе 1, а затем в реакторе 2. Ниже в таблице приведен фонд рабочего времени, имеющийся у каждого реактора в следующем месяце, а также время на обработку одной тонны каждого химиката в каждом реакторе:

\r\nРеактор Время на обработку 1 т химикатов, ч Фонд времени, ч\r\n типа 1 типа 2 \r\n1 4 2 300\r\n2 3 6 400\r\nИз-за ограниченных возможностей, связанных с существующим фондом времени на обработку химикатов в реакторах, фирма не имеет достаточных мощностей, чтобы выполнить обязательства по контракту. Выход заключается в следующем: фирма должна купить какое-то количество этих химикатов у других производителей, чтобы использовать эти закупки для выполнения контракта. Ниже приводится таблица затрат на производство химикатов самой фирмой и на закупку их со стороны: ^ \r\nТип химикатов Затраты на производство, тыс. руб./т Затраты на закупку, тыс. руб./т\r\n1 35 45\r\n2 56 66\r\nЦель фирмы состоит в том, чтобы обеспечить выполнение контракта с минимальными издержками. Это позволит ей максимизировать прибыль, так как цены на химикаты уже оговорены контрактом. Другими словами, фирма должна принять решение: сколько химикатов каждого типа производить у себя, а сколько — закупать со стороны для того, чтобы выполнить контракт с минимальными издержками.

Вопросы:

Сколько химикатов типа 1 следует производить фирме?

Сколько химикатов типа 2 следует производить фирме?

Сколько химикатов типа 1 следует закупать со стороны?

Сколько химикатов типа 2 следует закупать со стороны?

Каковы минимальные издержки на выполнение контракта?

Следует ли изменить объем закупок химикатов типа 2 со стороны, если их цена возрастет до 75 тыс.

На сколько возрастут минимальные издержки, если фонд времени работы реактора 2 сократится с 400 до 300 ч?

Решение. Введем обозначения:

x1 — количество продукта 1, производимого компанией;

z1 — количество продукта 1, закупаемого компанией;

x2 — количество продукта 2, производимого компанией;

z2 — количество продукта 2, закупаемого компанией.

Модель линейного программирования приведена в следующей таблице: \r\nЦелевая функция 35*, + 56х2 + 45*! + 66г2 min\r\nРесурсные ограничения: реактор 1 реактор 2 4х. + 2*j й 300 3JC,+6X2S400\r\nОграничения на спрос: продукт 1 продукт 2 X, + z, = 100 x2 + z2= 120\r\n: x1 > 0. x2 > 0. z1 > 0. z 2 > 0

Условия неотрицательности переменных:\r\nПеременные XI XI Z1 Z2 RHS\r\nMinimize 35 56 45 66 \r\nРеактор 1 4 2 0 0 <= 300\r\nРеактор 2 3 6 0 0 <= 400\r\nХимикат 1 1 0 1 0 = 100\r\nХимикат 2 0 1 0 1 = 120\r\n

Результаты расчетов:

\r\nПеременные XI XI Z\\ Z2 RHS Dual\r\nMinimize 35 56 45 66 \r\nРеактор 1 4 2 0 0 <= 300 1,66\r\nРеактор 2 3 6 0 0 <= 400 1,11\r\nХимикат 1 1 0 1 0 = 100 -45\r\nХимикат 2 0 1 0 1 = 120 -66\r\nSolution 55,55 38,89 44,44 81,11 11 475,56 \r\nТаблица двойственных оценок и границ устойчивости:

\r\nVariable Value Reduced Cost Original Value Lower Bound Upper Bound\r\nXI 55,55 0 35 25 40\r\nX2 38,89 0 56 46 61\r\n21 44,44 0 45 40 55\r\nZ2 81,11 0 66 61 76\r\nConstraint Dual Value Slack/Surplus Original Value Lower Bound Upper Bound\r\nРеактор 1 1,66 0 300 133,33 433,33\r\nРеактор 2 1,11 0 400 225 765\r\nХимикат 1 -45 0 100 55,55 Infinity\r\nХимикат 2 -66 0 120 38,89 Infinity\r\nИз таблицы двойственных оценок и границ устойчивости видно, что в пределах изменения закупочной цены на химикат типа 2 от 61 до 76 (ее фактическое значение 66) оптимальный план не изменится.

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

Ответы: 1. 55,55 т. 2. 38,89 т. 3. 44,44 т. 4. 81,11 т.

5. 11 475,56 тыс. руб. 6. Нет, не следует.

7. Ha 111 тыс. руб.