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

СОДЕРЖАНИЕ

 

1. ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ  ЗАДАЧА…………………………..….3

 

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

 

1.2. Математическая модель линейной  производственной задачи………...…...4

 

1.3. Решение линейной производственной  задачи симплексным методом….....6

 

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

 

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

переменными…………………………………………………………………...…...9

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

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

 

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

 

2.2. Задача «о расшивке узких  мест производства»…………………………...14

 

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

 

3.1. Математическая модель транспортной задачи…………………………...17

 

3.2. Решение транспортной задачи  методом потенциалов…………………...18

 

4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

    ЗАДАЧА РАСПРЕДЕЛЕНИЯ  КАПИТАЛЬНЫХ ВЛОЖЕНИЙ…………21

 

4.1. Формулировка задачи распределения  капитальных вложений……….21

 

4.2. Решение задачи распределения капитальных вложений методом динамического программирования……………….............................................21

 

5. АНАЛИЗ ДОХОДНОСТИ  И РИСКА ФИНАНСОВЫХ ОПЕРАЦИЙ.......25

 

Список использованной литературы…………………………………………..29

 

 

 

 

 

 

 

 

 

 

 

 

1. ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА

Задание

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

 

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

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

 

                    

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

 

В последней симплексной  таблице указать обращенный базис Q^-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

 

H = Q^-1B

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

 

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

 Сформулируем линейную производственную  задачу.

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

Известны:

• Технологическая матрица затрат любого из имеющихся ресурсов на единицу каждого вида продукции А, в которой каждый элемент a_ij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

• Вектор объемов имеющихся ресурсов В, каждый элемент которого b_i означает предельное количество i-го ресурса для выпуска всего объема продукции:

• Вектор удельной прибыли C, элементы которого c_j означают прибыль от реализации единицы продукции j-го вида (условимся, что реализация произведенной продукции происходит беспрепятственно):

Требуется:

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

1.2. Математическая  модель линейной производственной  задачи

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

,

где x1, x2, x3, x4  - искомое количество 1-ого, 2-ого, 3-его и 4-ого видов продукции соответственно.

 

б) Запишем условие  ограниченности имеющихся ресурсов в виде системы линейных алгебраических неравенств.

Поскольку запас каждого  вида имеющихся ресурсов ограничен, то каков бы ни был искомый план производства (х1, х2, х3, х4), компоненты вектора Х должны удовлетворять следующему условию: общий расход каждого вида ресурса на производство всей продукции не должен превышать запас данного ресурса.

Выразим данное условие  математически.

Технологическая матрица  затрат А показывает, какое количество ресурсов требуется для производства 1 единицы продукции. Каждому виду продукции соответствует столбец в технологической матрице затрат А. Каждая строка матрицы А соответствует одному из видов ресурсов. Чтобы получить расход каждого ресурса при заданной производственной программе перемножим матрицу А и вектор производственной программы X:

 

Общий расход первого  вида ресурса:                             3х1 + 3х3 + 3х4

Общий расход второго  вида ресурса:                             2х1 + 3х2 + х3 + х4

Общий расход третьего вида ресурса:                            4х1 + 3х2 + 2х3 + 2х4

 

Запасы имеющихся ресурсов соответствуют значениям компонент  вектора объемов ресурсов В:

Запас первого вида ресурса:                                              186

Запас второго вида ресурса:                                              102

Запас третьего вида ресурса:                                             196

 

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

3х1 + 3х3 + 3х4                  ≤   186

2х1 + 3х2 + х3 + х4      ≤   102

4х1 + 3х2 + 2х3 + 2х4  ≤   196

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

Вектор С указывает  на прибыль от продажи 1 единицы продукции  каждого вида. Каждая компонента вектора  соответствует одному из четырех  видов продукции. Чтобы найти  прибыль от реализации всей производимой продукции, следует помножить вектор производственной программы X на вектор удельной прибыли С:

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

 

Так как x₁, x₂, x₃, x₄ – неизвестные, запишем полученное выражение в виде функции:

Z = 38x₁ + 12x₂ + 28x₃ + 21x₄

 

Для достижения максимальной прибыли требуется найти максимум полученной функции Z:

Z = 38x₁ + 12x₂ + 28x₃ + 21x₄ → max

 

г)  Так как компоненты (x1, x2, x3, x4)  вектора производственной программы Х суть искомое количество каждого вида продукции, которое планируем производить, они не могут быть выражены отрицательными числами:

х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0

 

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

 

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

 

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

 

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

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

           2х1 + 3х2 + х3 + х4      ≤   102

           4х1 + 3х2 + 2х3 + 2х4  ≤   196

 

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

 

Преобразуем полученную модель линейной производственной задачи к основному (предпочитаемому) виду задачи линейного программирования

Систему неравенств, через  которую выражено условие ограниченности имеющихся ресурсов, заменим системой линейных алгебраических уравнений посредством дополнительных неотрицательных неизвестных х₅, х₆, х₇ , которые имеют экономический смысл остатков 1-го, 2-го и 3-го видов ресурсов соответственно.

Математическая модель линейной производственной задачи примет вид:

 

         Z = 38x₁ + 12x₂ + 28x₃ + 21x₄ → max,

3х1 + 3х3 + 3х4 + х5                     =   186

2х1 + 3х2 + х3 + х4 + х6        =   102

4х1 + 3х2 + 2х3 + 2х4+ х7     =   196

 

х1, х2, х3, х4, х5, х6, х7  ≥   0

 

Среди всех решений системы уравнений, удовлетворяющих условию неотрицательности х1, х2, х3, х4, х5, х6, х7, необходимо найти то решение, при котором целевая функция Z примет наибольшее значение.

 

 

1.3. Решение линейной  производственной задачи симплексным  методом.

 

Поскольку правые части всех уравнений системы неотрицательны, а сама система линейных алгебраических уравнений имеет предпочитаемый вид (дополнительный переменные х5, х6, х7 являются базисными), для решения полученной задачи можно применить симплексный метод

 

 

			38	12	28	21	0	0	0	Преобразования	Пояснения
Č	Базис	H	х1	х2	х3	х4	х5	х6	х7
0	Х5	186	3	0	3	3	1	0	0	I+III*(-3/4) → I’   II+III*(-1/2) → II’   III : 4 → III’   IV+III*(38/4) → IV’	min(Dj<0) = -38 Х1 → в базис min hi/ai1>0 = min (62,51,49) = 49 => Х7 → из базиса
0	Х6	102	2	3	1	1	0	1	0
0	Х7	196	4	3	2	2	0	0	1
	Z0 – Z	0-Z	-38	-12	-28	-21	0	0	0
										I’ : 3/2 → I’’   II’+I*0 → II’’   III’+I*(-1/3) → III’’   IV’+I*6 → IV’’	min(Dj<0) = -9 Х3 → в базис min hi/ai1>0 = min (26,98) = 26 => Х5 → из базиса
0	X5	39	0	- 9/4	3/2	3/2	1	0	- 3/4
0	Х6	4	0	3/2	0	0	0	1	- 1/2
38	Х1	49	1	3/4	1/2	1/2	0	0	1/4
	Z0 – Z	1862-Z	0	33/2	- 9	- 2	0	0	19/2
											Z0 = Č* H ∆j = Č*Gj – cj     все ∆j≥0
28	Х3	26	0	-  3/2	1	1	2/3	0	- 1/2
0	Х6	4	1	3/2	0	0	0	1	1/2
38	Х1	36	0	3/2	0	0	- 1/3	0	1/2
	Z0 – Z	2096-Z	0	3	0	7	6	0	5

 

 

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

 

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

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. Двойственная задача  линейного программирования

 

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

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

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

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