Методы разработки управл решений

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

2. Управленческие задачи, решаемые с помощью модели линейного программирования

2.1. Задача о планировании  производственной  программы предприятия 

     Предприятие может выпускать n видов продукции Р₁, Р₂, ..., Р_n, располагая для этого т различными ресурсами R₁, R₂, ..., R_m в количествах b₁ b₂,..., b_m соответственно. Известно, что для выпуска единицы продукции P_j необходимо затратить a_ij единиц ресурса R₁, i = 1, 2, ..., m;j = 1, 2,..., n. Кроме того, известен доход с₁, с₂,..., с_n от продажи единицы каждого вида продукции, где с_j, j = 1, 2, ..., n, - стоимость единицы продукта P_j, например 1 шт., 1 т и т.д.

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

     Для удобства дальнейших выводов и рассуждений сведем исходную информацию в единую табл. 1, где через x_j обозначены объемы продукции P_j, выпускаемой предприятием. Тогда набор переменных {x₁,x₂,..., х_n} представляет собой не что иное, как производственную программу предприятия.

Таблица 1

Исходная  информация задачи

 
 

     Доход, полученный предприятием при производстве продукта P_j в количестве х_j, составит c_jx_j, а при реализации производственной программы {х₁, x₂,..., x_j} будет равен величине

     Z = с₁х₁ + с₂х₂ +... + с_пх_п.

     Подсчитаем, какое количество ресурсов будет  израсходовано, если выбрать некоторый план {х₁, x₂,..., x_j}.

     Ресурса R₁ потребуется а₁₁х₁ + а₁₂х₂ +... + а_1nх_n, в то время как в наличии имеется запас b₁.

     Ресурса R₂ потребуется а₂₁х₁ + а₂₂х₂ +... + а_2nх_n, в то время как в наличии имеется b₂.

     Ресурса R_m потребуется а_m1х₁ + а_m2х₂ +... + а_mnх_n, в то время как в наличии имеется b_m.

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

     Кроме того, понятно, что переменные решения  x₁,x₂, ..., х_n, должны удовлетворять условию неотрицательности:

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

     Требуется найти совокупность значений {х₁,х₂,...,х_п}, обращающих в максимум целевую функцию:

     Z = c_lx₁ +c₂x₂ +... + c_nx_n => max,                       

при условии, что переменные {х₂,х₂,..., х_n} удовлетворяют системе ограничений:

 

Пример  3

     Химическая  фабрика выпускает три разновидности стирального порошка марок А, В, С. Доход от реализации 1 кг порошка каждого наименования известен, и составляет с_A = 10, с_в = 12, с_с= 8 руб. соответственно. Недельные запасы и удельные расходы ресурсов, необходимых для производства 1 кг порошка каждой марки, приведены в табл. 2.

Таблица 2

 

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

Решение

     Обозначим через х_А,х_в,х_с недельные объемы выпуска стиральных порошков марок А, В, С (кг). Тогда доход от реализации порошков при производственной программе {х_д,х_в,х_с} составит:

     Z = с_Ах_А + с_Bх_B + с_сх_с,

или

     Z = 10x_А + 12x_B + 8x_c.

     Подсчитаем  расходы ресурсов, необходимые для выполнения производственной программы {х_A,х_в,х_с}.

     Сырья будет израсходовано 1,4х_A + 1,2х_в + 1,5х_с кг при запасе, равном 15 000 кг. Следовательно, для того, чтобы программу можно было реализовать, необходимо, чтобы выполнялось ограничение:

     1,4х_A + 1,2х_в + 1,5х_с < 15 000.

     Расход  ресурса «оборудование» составит 0,2х_А + 0,7х_а + 0,3х_с нормо-часов при запасе 2300 нормо-часов. Следовательно, при выборе производственной программы необходимо выполнить условие:

     0,2х_А + 0,7х_в + 0,3х_с < 2300.

     Расход ресурса «трудозатраты» составит 0,3х_А + 0,2х_в + 0,1х_с чел.-часов при запасе 1600 чел.-часов. Следовательно, при поиске оптимальной программы должно выполняться условие:

     0?3х_А + 0,2х_в + 0,1х_с < 1600.

     Кроме того, переменные х_А,х_в,х_с не могут принимать отрицательных значений:

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

     Необходимо  сформировать такую производственную программу {х_A,х_в,х_с} (определить объемы выпуска продукции каждой марки), при которой целевая функция (доход от реализации) будет максимальной:

     Z = 10х_А +12х_в + 8х_с = max,

при условии, что переменные х_А,х_в,х_с удовлетворяют системе ограничений:

     Заметим, что и целевая функция, и левые части ограничений в рассмотренном примере линейны относительно переменных х_А,х_в,х_с. Следовательно, это задача линейного программирования. 

2.2. Задача об оптимальной  корзине продуктов  (задача о диете) 

     Медициной установлена суточная потребность организма в питательных веществах T₁,T₂, ..., Т_m (белки, жиры, углеводы и т.д.): человеку они необходимы в количествах не менее чем b₁, b₂, ..., b_m некоторых условных единиц (например, миллиграмм). В продаже имеются продукты питания П₁, П₂, ..., П_n, стоимость которых известна и равна c₁,с₂,...,с_n (где c_j -стоимость единицы продукта П_j, например 1 кг, 1 л, 1 уп. и т.д.). Известно также, что питательное вещество T_i содержится в единице продукта П_j в количестве а_ij единиц, i = 1,2, ..., m; j = 1,2,..., n.

     Требуется составить продуктовую корзину  с минимальной стоимостью, т.е. определить количество продуктов каждого вида {х₁, х₂,..., х_n}, которые следует приобрести для того, чтобы, с одной стороны, удовлетворить суточную потребность организма в питательных веществах, а с другой - израсходовать при этом минимум средств. Исходная информация, необходимая для формулировки задачи приведена в табл. 3.

Таблица 3

Исходная  информация для задачи

 

     Обозначим стоимость искомой корзины через  Z. Тогда для некоторого продуктового набора {х,,х₂,..., x}

     Z = c_lx_l + c₂x₂ +... + c_nx_n.

     Подсчитаем  количество каждого питательного вещества Т_i, i = 1,2, ..., m, содержащегося в корзине {х,,х₂,..., x}.

     Содержание  вещества T_l в корзине a₁₁x₁ + a_l2x₂ +... + a_lnx_n, в то время как его должно быть не менее b₁

     Содержание  вещества Т₂ в корзине а₂₁х₁ +a₂₂x₂+... + a_2nx_n, в то время как его должно быть не менее b₂.

     Содержание  вещества Т_m в корзине a_mlx₁ + a_m2x₂ + ... + a_mnx_n, в то время как его должно быть не менее b_m.

     Кроме того, переменные решения {х₁,х₂,..., х_n} не могут быть отрицательными числами:

     В результате приходим к следующей оптимизационной задаче. Необходимо   найти   такой   набор   значений   для   переменных {х,, х₂,..., х_n}, которые обращают в минимум целевую функцию

Z = c₁x₁ + c₂x₂ +... + c_nx_n => min,

и одновременно удовлетворяют следующей системе  ограничений:

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

Пример  4

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

Таблица 4

 

Решение

     Обозначим через х₁,х₂,х₃,х₄ количество приобретаемых продуктов каждого вида (в кг). Тогда стоимость продуктового набора будет равна:

     Z = 45x₁, + 60х₂ + 70х₃ + 80х₄.

     Содержание  А в продуктовом наборе составит х₁ + 0х₂ + 2х_э + + 5х₄. Причем, согласно требованиям, его количество должно быть не менее 50. Тогда получаем первое ограничивающее условие - набор продуктов х₁,х₂,х₃,х₄ должен быть таким, чтобы обеспечить количество А не менее чем 50 условных единиц:

     Х₁ + 0х₂ + 2х₃ + 5х₄ > 50.

     Рассуждая аналогично, получим ограничивающие условия по другим компонентам:

     3х₁ + 5х₂ + 0х₃ + 4х₄ > 60 - ограничение по удовлетворению потребности в B;

     4х₂ + 7х₃ + 0х₄ > 40 - ограничение по удовлетворению потребности в С.

     Кроме того, переменные х₁,х₂,х₃,х₄ не могут быть отрицательными числами. Следовательно,

     Объединяя полученные результаты, получаем следующую  оптимизационную задачу.

     Необходимо  найти такой набор значений переменных х₁, х₂, х₃, х₄ (количества продуктов каждого вида), который обращает целевую функцию (стоимость продуктового набора) в минимум:

     Z = 45х₁ + 60х₂ + 70х₃ + 80х₄ => min,

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

     Так как и целевая функция, и ограничения линейны, то это задача линейного программирования. 
 

2.3. Формы записи задач  линейного программирования 

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