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

Данная задача подобна той, которая была рассмотрена в при­мере 2.2.1, Основное отличие состоит в том, что сверхурочные работы требуют дополнительных расходов. Пусть х_j — количество изделий j, j =1, 2.

сверхурочные работы не допускаются, то ограничения имеют вид

х₁ /5 + х₂ /6≤ 8 (станок 1),

х₁/4 + х₂/8≤ 8 (станок 2).

Чтобы учесть возможность сверхурочных работ, можно видоизме­нить эти ограничения следующим образом:

х₁ /5 + х₂ /6 – y₁ = 8 (станок 1),

х₁/4 + х₂/8 – y₂ =8 (станок 2)

где введенные переменные (y₁ и у₂ не имеют ограничения в знаке, что обусловлено следующими факторами. Если переменная у_^ отрицательна, то имеющийся восьмичасовой фонд рабочего вре­мени полностью не израсходован, т. е. сверхурочное время не используется. Если переменная у, положительна, восьмичасового фонда времени не хватает, и используется сверхурочное время в объеме y₁ часов.

Вводя переменные y₁, для того чтобы учесть возможность ис­пользования сверхурочного времени, мы не принимали во вни­мание ограничений, накладываемых на их значения. Теперь сле­дует отразить тот факт, что продолжительность сверхурочных работ не превышает 4 ч в сутки. Кроме того, в выражении для це­левой функции нужно учесть дополнительные расходы, обусловлен­ные сверхурочными работами. Так как переменная y_i, положи­тельна только в том случае, когда используется сверхурочное время, ограничения y_i ≤ 4, i= 1, 2, адекватны условиям задачи, характеризующим возможность использования сверхурочного вре­мени. Заметим, что при y_i < 0 (сверхурочные работы не выполняются) эти ограничения становятся избыточными.

Рассмотрим теперь целевую функцию. Наша цель заключается в максимизации чистой прибыли, представляющей собой общую прибыль от реализации изделий, уменьшенную на величину до­полнительных расходов, связанных с выполнением сверхурочных работ. Величина общей прибыли непосредственно определяется из условий задачи как 6 х₁ + 4 х₂. Следует отметить, что дополни­тельные расходы на сверхурочные работы учитываются только при y₁> 0. Таким образом, эти дополнительные расходы удобно пред­ставить в виде

Затраты на сверхурочные работы = Затраты/час х Сверхурочное время (час) = 5(mах {0, y_i}).

Заметим, что mах {0, у₍}=0, если y_i, < 0; при этом (как и должно быть) расходы на сверхурочные работы равны нулю. Таким образом, математическая формулировка задачи имеет вид

максимизировать z =6 х₁ +4 х₂ - 5 (mах{0, y₁} + mах {0, y₂ })

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

х₁ /5 + х₂ /6 – y₁ = 8

х₁/4 + х₂/8 – y₂ = 8

y₁ ≤ 4

y₂ ≤ 4

х₁, х₂ ≥ 0, y₁ , y₂ - не ограничены в знаке.

Для приведения модели у линейно форме используем следующую подстановку:

w_i = max {0, y_i}

которая эквивалентна введению условий

w_i ≥ y_i и w_i ≥ 0,

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

максимизировать 6х₁ + 4х₂ – 5 (w₁ + w₂)

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

х₁/5 + х₂/6 – y₁ =8

х₁/4 + х₂/8 – y₂ =8

y₁ - w₁ ≤ 0

y₂ - w₂ ≤ 0

y₁ ≤ 4

y₂ ≤ 4

х₁, х₂, w₁ , w₂ ≥ 0

y₁, y₂ - не ограничены в знаке.

В заключение данного раздела отметим, что характер ряда рассмотренных задач требовал введения условия целочисленности переменных для соответствующих моделей. Например, в задаче минимизации переменные соответствовали количеству рулонов, которые следовало раскрыть при том или ином варианте установки режущей кромки. Следует подчеркнуть, что в общем случае модель ЛП не гарантирует получения целочисленного решения, и единственный способ, который можно использовать в этой ситуации, - это округление полученных оптимальных значений переменных. Иногда такая процедура оказываеться вполне приемлемой, особенно при достаточно больших значениях переменных. Методы получения точного оптимального решения задач целочисленного программирования будут рассмотрены в главе 10. Основной недостаток целочисленных линейных моделей заключается в низкой эффективности соответствующих вычислительный методов.

Задача линейного программирования как задача распределения ресурсов

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

максимизировать z= c₁х₁ + c₂х₂ +_{……………}+ c_nх_n

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

a₁х₁ + a₂х₂ +……… + a_1nх_n ≤ b₁

a₂₁х₁ + a₂₂х₂ + ……….. + a_2nх_n ≤ b₂

…………………………..

a_m1х₁ + a_m2х₂ +……… + a_mnх_n ≤ b_m

х₁, х₁, …., х_n ≥

Модель ЛП направлена на поиск наиболее выгодного способа распределения ограниченных ресурсов по нескольким видам производственной деятельности. В сформулированной выше задаче ЛП представлено n видов производственной деятельности, интенсивности использования которых (искомые величины) равные х₁, х₂, ….., х_n. Для осуществления всех видов производственной деятельности имеется m видов ресурсов, возможные объемы потребления которых ограничены значениями b₁, b₂, ……, b_m. Расход i-го ресурса на единицу продукции j-го вида производства равен a_ij. Поэтому, сумма ∑ ⁿ_j=1 a_ij х_j, представляющая собой общий объем ресурса i, потребляемый n видами производства, не может превышать величины b_1.

Структура целевой функции ∑ ⁿ_j=1 a_ij х_j отражает вклад каждого вила производственной деятельности в общий результат. В случае максимизации c_j, представляет собой прибыль от j -го вида производственной деятельности на единицу соответствующей продукции, а в случае минимизации сj характеризует удельные затраты. Заметим, что «полезность» некоторого вида производственной деятельности нельзя установить только по значению соответствующего коэффициента целевой функции, так как объем потребления ограниченных ресурсов также является важным фактором. Поскольку все виды производственной деятельности, представленные в модели претендуют на использование ограниченных ресурсов, относительная полезность некоторого вида производства (но сравнению другими видами производственной деятельности) зависит как от величины коэффициента целевой функции c_j, так и от интенсивность потребления ресурсов a_ij. Поэтому может оказаться, что из-за слишком большого расхода ограниченных ресурсов некоторый i-й вид производственной деятельности, характеризующийся высокой прибылью, использовать нецелесообразно (т, е. в оптимальном решении x_j =0).

Заключение

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

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

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

Контрольные вопросы

Верно (В) или неверно (Н)?

1. ------Условие пропорциональности модели ЛП не выполняется, если удельный вклад в целевую функцию некоторой пере­менной зависит от значения этой переменной.

2. ------- Заменяя в линейной модели знаки ограничений ≤ или ≥ на знак =, можно улучшить значение целевой функции.

3. ----- Замена знака ≤ на знак = в ограничении линейной модели может привести к более жесткому ограничению пространства решений.

4. -- Ограничение типа ≥ можно сделать более жестким, умень­шив постоянную в его правой части.

5. ---- Двумерное пространство решений с двумя ограничениями

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

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

7. ---- Оптимальное решение задачи ЛП, если оно конечно, можно всегда найти, зная все экстремальные точки про­странства решений.

8.----- В задаче ЛП с двумя переменными целевая функция мо­жет принимать одно и то же значение в двух различных экстремальных точках.

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

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

11.--- Оптимальное решение задачи ЛП можно изменить, ис­ключая несвяэывающие ограничения.

12.--- Избыточные ограничения соответствуют недефицитным ресурсам.

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

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

15. ----- изменения коэффициентов целевой функции могут изменить статус ресурсов (т.е. дефицитный ресурс может стать недефицитным, и наоборот).

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

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

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

[Ответы: 1-B, 2-H, 33-B, 4-H, 5-B, 6-B, 7-B, 8-B, 9-H, 10-B, 11-H, 12-H, 13-B, 14-H, 15-B, 16-B, 17-H,

18-B.]