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

СОДЕРЖАНИЕ

 

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