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

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

максимизировать 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.]

Литература