Линейная производственная задача

Содержание

1) Цели и задачи курсового проекта…………………………………. ...3

2) Линейная производственная задача………………………………… ..3

3) Двойственная задача…………………………………………………… 6

4) Транспортная задача линейного программирования……………….12

5) Динамическое программирование. Распределение капитальных вложений…………………………………………………………………19

6) Задача формирования оптимального портфеля ценных бумаг……22

7) Матричная игра как модель конкуренции и сотрудничества… …27

8) Анализ доходности и риска финансовых операций…………… ….33

9) Принятие решений в условиях неопределенности………………. ..35

ЦЕЛИ И ЗАДАЧИ КУРСОВОГО ПРОЕКТА

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

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

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

 

Линейная производственная задача

Задание:

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

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

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

H = Q^-1B

 

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

Постановка задачи:

Компания «Малыш» выпускает четыре вида детского питания, используя для этого сухое молоко, сою и фруктовое пюре. Известна технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания, вектор В объемов имеющихся ресурсов и вектор  С   стоимости каждого вида питания.

 

                           2 3 0 4        148

                A = 4 1 5 0 B=  116 C=(30 25 14 12)

                           0 2 4 3         90

 

Примем следующие обозначения: а _{i j} – расход i-ого ресурса на единицу j-го вида питания; b_i – запас i-ого ресурса; с _j – прибыль на единицу j-го вида питания; x_j – количество выпускаемого питания j -ого вида.

На производство x ₁ питания 1-го вида

                           x ₂ питания 2-го вида

                           x ₃ питания 3-го вида

                           x ₄ питания 4-го вида компания затратит следующее количество ресурсов:

                                                        (1)

Требуется найти производственную программу X ^* = ( x ₁ , x ₂ , x ₃ , x ₄ ), реализация которой обеспечит компании получение наибольшей прибыли:

,

при линейных ограничениях неравенства (1).

 

Решение:

Приведем задачу к основной задаче линейного программирования. Для этого добавим в левую часть системы ограничений (1) дополнительные неотрицательные неизвестные x ₅ , x ₆ , x ₇ , которые  по физическому смыслу будут представлять собой:

x ₅ – остаток ресурса 1-го вида,

x ₆ – остаток ресурса 2-го вида,

x ₇ – остаток ресурса 3-го вида.

Строим симплексную таблицу.

В качестве базисных неизвестных могут быть приняты неизвестные х₅, х₆, х₇ , так как каждый из них входит только в одно уравнение системы и не входит в другие уравнения. Приравняв к нулю свободные переменные х₁, х₂, х₃, х₄ , получаем базисное неотрицательное решение:

х₁=0, х₂=0, х₃=0, х₄=0, х₅=148, х₆=116, х₇=90

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

Выясним, до каких пор наши ресурсы позволяют увеличить выпуск этой продукции:

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

0 – Z = -30 x₁-25x₂-14x₃-12x₄

Ć	Б	Н	X1	X2	X3	X4	X5	X6	X7	α	Пояснения
0	X5	148	2	3	0	4	1	0	0	74	min ( D j <0)= -30 min (α)=29, x 1 в базис, x 6 из базиса
0	X6	116	4	1	5	0	0	1	0	29
0	X7	90	0	2	4	3	0	0	1	∞
		0-Z	-30	-25	-14	-12	0	0	0
0	X5	90	0	5/2	-5/2	4	1	-1/2	0	36	min ( D j <0)= -35/2 min (α)=36, x 2 в базис, x 5 из базиса
30	X1	29	1	1/4	5/4	0	0	1/4	0	116
0	X7	90	0	2	4	3	0	0	1	45
		870-Z	0	-35/2	47/2	-12	0	15/2	0
25	X2	36	0	1	-1	8/5	2/5	-1/5	0		решения оптимальны
30	X1	20	1	0	3/2	-2/5	-1/10	3/10	0
0	X7	18	0	0	6	-1/5	-4/5	2/5	1
		1500-Z	0	0	6	16	7	4	0

 

x ₁ =20, x ₂ =36, x ₃ =0, x ₄ =0, x ₅ =0, x ₆ =0, x ₇ =18 определяют производственную программу x ₁ =20, x ₂ =36, x ₃ =0, x ₄ =0

Прибыль будет наибольшей когда , при этом

остатки ресурсов: 1-ого вида  x ₅ =0

                           2-ого вида x ₆ =0

                           3-ого вида x ₇ =18

Также надо обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Коэффициенты ∆₃ =6 при переменной Х₃,  ∆₄ =16 при переменной Х₄ показывают, что если произвести одну единицу продукции 3-ого или 4-ого видов, то прибыль уменьшится на 6  или 16 единиц соответственно.

Проверим выполнение соотношения H=Q^-1B:

; ; ;

Равенство выполняется.

 

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

    

; ;

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

- ?

Z = 30 x ₁ + 25 x ₂ → max

 

 

 

Двойственная задача

Задание:

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

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

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

Постановка задачи:

Ранее мы рассмотрели конкретную линейную производственную задачу по выпуску четырех видов детского питания с использованием трех видов ресурсов Технологическая матрица А затрат любого вида ресурса на единицу каждого вида питания была известна. 

Теперь представим себе, что возникла новая ситуация. предприниматель П. (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у компании «Малыш», предлагает ей "уступить" по определенным ценам все имеющиеся у «Малыша» ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб. – второго, у₃ руб. – третьего.  Возникает вопрос: при каких ценах у₁, у₂, у₃ компания «Малыш» может согласиться с предложением П.

Величины у₁, у₂, у₃ это двойственные оценки ресурсов. Они прямо зависят от условий, в которых действует компания «Малыш».

В нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид:

 

                           2 3 0 4        148

                A = 4 1 5 0 B=  116 C=(30 25  14 12)

                           0 2 4 3         90

Для производства единицы первого вида питания компания должна затратить, как видно из матрицы А, 2 единицы ресурса первого вида и 4 единицы ресурса второго вида  (элементы первого столбца матрицы). В ценах у₁,  у₂,  у₃ затраты   компании составят 2у₁ + 4у₂ руб., т.е. столько заплатит предприниматель П. за все ресурсы, идущие на производство единицы первой продукции.  На рынке за единицу первого вида питания компания получила  бы прибыль 30 руб. Следовательно, компания «Малыш» может согласиться с предложением П. только в том случае, если он заплатит не меньше 30 руб.:

2у₁ + 4у₂ ³ 30

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы детского питания  второго вида. В ценах П. эти затраты составят 3у₁ + 1у₂ + 2у₃, а на рынке за единицу питания второго вида «Малыш» получил бы прибыль 25 рублей.  Поэтому перед предпринимателем П нужно поставить условие:

3у₁ + 1у₂ + 2у₃ ³ 25 и т.д.

За все, имеющиеся у «Малыша» ресурсы П. должен заплатить:

148у₁ + 116у₂ + 90у₃  рублей

 При поставленных «Малышом» условиях предприниматель П. будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым компания когда-то приобретала эти ресурсы, а о ценах, которые существенно зависят от применяемых «Малышом»  технологий, объемов ресурсов и от ситуации на рынке.

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок У^*(у₁, y ₂ , y ₃ ), минимизирующий общую оценку всех ресурсов:

_,                                                                           (1)

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

 

                                                                              (2)

Решение:

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

 

Прямая задача:	Двойственная задача:

 

Согласно второй основной теореме двойственности для оптимальных решений X ^* =(х₁, х₂, х₃, х₄) и Y ^* =(y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий:

При решении прямой  задачи было получено, что  x ₁ >0_, x ₂ >0.  Поэтому:

      

Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю т.е. y₃=0, то приходим к системе уравнений:

, откуда следует    

Решение двойственной задачи Y ^* =(7, 4, 0)

Тогда общая оценка всех ресурсов равна

                 (3)

Заметим, что решение (3) содержалось в последней строке последней симплексной таблицы исходной задачи. Важен экономический смысл двойственных оценок. Например, двойственная оценка второго ресурса у₂=4 показывает, что добавление одной единицы второго  ресурса обеспечит прирост прибыли в 4 единицы.

 

Задача о "расшивке узких мест производства"

П остановка задачи:

Продолжаем рассмотрение задачи планирования производства. При выполнении оптимальной производственной программы  первый и второй ресурсы используются  полностью, т.е. образуют «узкие места производства» x ₅ =0, x ₆ =0.  Будем «расшивать узкие места производства» т.е. заказывать дополнительно дефицитные ресурсы. Обозначим через t ₁ и t ₂ искомое дополнительное количество единиц первого и второго вида ресурсов. T(t₁, t₂, 0)- вектор дополнительных объемов ресурсов. Согласно третьей основной теореме двойственности, увеличение первого вида ресурса на единицу обеспечивает прирост прибыли, равный двойственной оценке y ₁ =7,   второго вида – y ₂ =4.

При этом, для сохранения структуры плана производства величины t₁, t₂, t₃ должны изменяться лишь в области устойчивости двойственных оценок, т.е. должно выполняться условие:

H + Q^-1T  0, причем, по смыслу задачи t₁ >0, t₂ >0.           (1)

Таким образом,  проблема «расшивки узких мест производства» представляет собой задачу линейного программирования: найти   план расшивки - вектор T (t₁, t₂, 0),  максимизирующий суммарный прирост прибыли:

  ,                                                            (2)

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

Обращенный базис был найден при решении задачи симплексным методом:

Условия (1) запишутся в виде:

                                                    (3)

Предположим также, что поставщики сырья могут выделить компании не более 1/3   первоначального объема ресурса каждого вида:

                                                                                (4)

Перепишем неравенства (3) и (4) в виде:

 

                                                                            (5)

 

Задача оптимизации плана «расшивки узких мест» производства принимает вид: найти переменные  t₁ и  t₂, которые  обеспечивают максимум линейной форме:

, при ограничениях (5).

 

Решение:

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

         

 

Строим график и ищем точки пересечения:

 

 

, откуда оптимальный план «расшивки»:

При этом прирост прибыли составит: W = 7t₁ + 4t₂=447 ½ .

 Сводка результатов приведена в таблице:

 

Cj	30	25	14	12	b	x4+i	yi	ti
	2	3	0	4	148	0	7	41 5/6
aij	4	1	5	0	116	0	4	38 2/3
	0	2	4	3	90	18	0	0
xj	20	36	0	0	1500			447 ½
Δ j	0	0	6	16