Формулировка линейной производственной задачи

 

 

Пояснения к решению задачи

 

Алгоритм решения:

1. Просматриваем значения 4-й строки симплексной таблицы. Если все D_j ³ 0, то решение задачи является оптимальным.
2. Если какие-либо D_j < 0, находим min(D_j < 0) = D _к.
3. Х _к включаем в число базисных переменных.
4. Отыскиваем разрешающее уравнение и переменную, исключаемую из базиса:

• находим min(h_i/а_ik) = h_t/а_tk (для всех а_ik > 0);

• Х _t исключаем из числа базисных переменных.

5. Строим новую симплексную таблицу, преобразуя исходную.

6. Возвращаемся в пункт 1.

 

Пояснения к  первой симплексной таблице 

X = (0, 0, 0, 0, 186, 102, 196) 

Этот опорный план отражает производство, при котором  ничего не выпускается, ресурсы не используются и прибыль от реализации произведённой продукции равна 0.

В строке оценочных коэффициентов  имеются отрицательные значения, которые показывают, на сколько увеличится прибыль от производства продукции  при включении в план производства одной единицы продукции того или иного вида. Например, число –12 означает, что включение в план производства единицы второго вида продукции позволит увеличить прибыль на 12 денежных единиц. Наиболее выгодным в данной задаче  будет внедрение в производство первого вида продукции, так как ему соответствует максимальная удельная прибыль, равная 38 денежным единицам. Поэтому x₁ становится базисной переменной и запускается производство первого вида продукции. Определяем переменную, которую надо исключить из производства. Ограничивающим фактором будет объем ресурса третьего вида (Х7), поскольку из него можно произвести наименьшее количество продукции первого вида, так как ему соответствует наименьшее hi/ai1,  равное 49.

 

Пояснения ко второй  симплексной таблице

X = (49, 0, 0, 0, 39, 4, 0)

Изготавливается 49 единиц первого вида продукции. 39 единиц первого вида ресурса и 4 единицы второго вида ресурса остаются в остатке.

Прибыль от реализации произведенной  при таком плане продукции (Z) составляет 1862 денежные единицы.

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

С учетом вышеизложенного  составляем третью симплексную таблицу.

 

Пояснения к  третьей симплексной таблице

X = (36, 0, 26, 0, 0, 4, 0)

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

Z = 2096 - 3х₂ - 7х₄ - 6х₅ - 5х_7,

то становится совершенно очевидным (в силу того, что все  ∆j ≥ 0), что прибыль будет наибольшей тогда, когда х_{2 ,} х_4, х_5, х₇ = 0.

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

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

Оценочные коэффициенты, соответствующие ресурсам, выражают меру дефицитности ресурсов.

В случае увеличения количества дефицитных ресурсов, например, третьего, на единицу, прибыль увеличится на 5 денежных единиц.

Оценка второго ресурса  равна 0. Он дан в избытке, увеличение его количества не ведет к увеличению прибыли, поэтому увеличивать его  нет смысла.

 

Выводы.

1. Оптимальная производственная программа имеет вид:

х1* = 36, х2* = 0, х3* = 26, х4* = 0         или                        Х* = (36, 0, 26, 0).

 

2. Максимальная прибыль равна Z(max) = 2096 денежных единиц.

 

3. Использование ресурсов:

Первый и  третий ресурсы используются полностью (х5* = 0, х7* = 0),

а второй ресурс имеет  остаток х6* = 4 единицы.

 

4. При выполнении производственной программы ресурсы первого и третьего вида расходуются полностью, т.е. образуют  “узкие места производства”.

 

 

1.4. Проверка  полученного решения

Укажем обращенный базис Q^-1, соответствующий оптимальному базисному решению, и проверим выполнение соотношения     

Q^-1 *В = H

 

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

 

 Обращенный базис Q^-1

 

   2/3 0 -1/2

Q^-1=        0 1 -1/2

- 1/3 0  1/2

х₅ х₆ х₇

 

Проверим выполнение соотношения:     

       2/3*186 + 0*102 - 1/2*196               26

Q^-1 *B=        0*186 + 1*102 – 1/2*196       =       4      =    H

     -1/3*186 + 0*102 + 1/2*196              36

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.5. Графическое  решение линейной производственной задачи с двумя переменными

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

Воспользуемся тем, что  в оптимальной производственной программе х2* = 0, х4* = 0, т.е. продукция второго и четвертого вида не производится. Предположим, что второй и четвертый виды продукции мы не намеревались выпускать с самого начала.

 

Рассмотрим задачу с  оставшимися двумя переменными, сохранив их нумерацию.

 

Исходные данные примут вид:

                                   Вектор удельной прибыли

Нормы затрат различных ресурсов на производство единицы каждого вида продукции	38	28		Вектор объемов ресурсов
	3	3	186
	2	1	102
	4	2	196

 

 

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

 

Найти производственную программу   Х (х1, х3),

 

максимизирующую прибыль                 Z = 38x₁ + 28x₃  → max,

 

при условии ограниченности

имеющихся ресурсов                              3х1 + 3х3    ≤   186

                                                                  2х1 + х3     ≤   102

                                                                  4х1 + 2х3   ≤   196

 

где по смыслу задачи                             х1 ≥ 0, х3 ≥ 0

 

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

 

Построим систему координат, где на горизонтальной оси будем  откладывать значения х1, а на вертикальной – значения х3, причем нас интересует только правая верхняя полуплоскость данной системы, поскольку по условию задачи х1 ≥ 0, х3 ≥ 0.

 

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

 

3х1 + 3х3   = 186 - ограничивающая прямая I

2х1 +   х3  = 102 - ограничивающая прямая II

4х1 + 2х3 = 196 - ограничивающая прямая III

 

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

 

Построим вектор-градиент grad Z = (0, 0); (38, 28), указывающий направление наискорейшего возрастания функции Z.

Линии уровня функции Z перпендикулярны вектору-градиенту grad Z и образуют семейство параллельных прямых.

Перемещаем линию уровня функции Z в направлении вектора-градиента grad Z, не выходя при этом за пределы допустимого множества (четырехугольника OQRS), до крайней точки допустимого множества.

Определяем, что максимального  значения в области допустимого  множества функция Z достигнет в точке R, которая является пересечением I и III прямых. Следовательно, координаты этой точки определяют оптимальный план производства, и мы можем их найти, решив систему уравнений:

     3х1 + 3х3    =  186

     4х1 + 2х3   =   196

 

1). Выразим переменную х3 через второе уравнение системы:

х3 = 196 – 4х1 = 98 – 2х1

              2

2). Подставим полученное выражение    3). Найдем                                     4). Найдем максимальную                                           

в 1-е уравнение и найдем значение х1:    значение х3:                         прибыль:

3х1 + 3 (98 – 2х1) = 186                              108 + 3х3 = 186                  

3х1 + 294 – 6х1    = 186                                          3х3 = 78                   Z = 38х1 + 28х3

                  - 3х1 = - 108                                               

                         х1* = 36                                       х3* = 26                 Z(max) =  38*36 + 28*26 =  2096

     

2. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ,

                   ЗАДАЧА О «РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА»

Задание     

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

Применить найденные  двойственные оценки ресурсов к решению  следующей задачи.

 

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

Составить сводку результатов.

 

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

 

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

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

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

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