Содержание

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

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

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

3. Транспортная задача линейного программирования 7

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

5. Анализ доходности и риска финансовых операций 13

6. Матричная игра как модель конкуренции и сотрудничества 15

7. Задача о кратчайшем пути 20

8. Задача о максимальном потоке в сети 21

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

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

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

Примем следующие обозначения:

i – номер ресурса (i=1,2, … , m);

j – номер вида изделия (j=1,2, … , n);

a_ij – норма расхода ресурса вида j- на единицу i-го изделия;

b_i общий объем ресурса вида j, который может быть использован для выпуска продукции в определенный период времени;

с_j удельная прибыль на единицу j-го изделия.

Для построения формальной модели введем переменные x_i , значения которых будут показывать планируемое количество единиц j-го изделия. По смыслу задачи все переменные могут принимать только неотрицательные значения. Набор значений переменных (x₁, x₂, … , x_n) будет представлять искомый план производства.

Исходные параметры задачи представлены в виде технологической матрицы A затрат ресурсов на единицу продукции каждого вида, вектора B объемов ресурсов и вектора C удельной прибыли:

2 3 4 1 103

A = 4 2 0 2 B= 148 C= ( 36 32 10 13)

2 8 7 0 158

При этом x₁  0, x₂  0, x₃  0, x₄  0.

Составим функция прибыли (целевую функцию):

Z=36x₁+32x₂+10x₃+13x₄

Необходимо составить производственную программу (х₁, х₂, …, х_n) так, чтобы функция Z приняла наибольшее значение при выполнении всех других условий:

2x ₁ + 3x₂ + 4x₃ + 1x₄  1 вид ресурса

4x₁ + 2x₂ + 0x₃ + 2x₄  148 2 вид ресурса (1)

2x₁ + 8x₂ + 7x₃ + 0_x4  158 3 вид ресурса

Неравенства (1) нужно превратить в равенства. Для этого вводим дополнительные неотрицательные неизвестные x₅  0, x₆  0, x₇  0.

Решим задачу с помощью симлексной таблицы:

			X1	X2	X3	X4	X5	X6	X7
c`	Базис	H	36	32	10	13	0	0	0
0	X5	103	2	3	4	1	1	0	0
0	X6	148	4	2	0	2	0	1	0
0	X7	158	2	8	7	0	0	0	1
	Z-Z0	0	1 = -36	2 = -32	3 = -10	4 = -13	5 = 0	6 = 0	7 = 0
0	X5	29	0	2	4	0	1	-0.5	0
36	X1	37	1	0.5	0	0.5	0	0.25	0
0	X7	84	0	7	7	-1	0	-0.5	1
	Z-Z0	1332	1 = 0	2 = -14	3 = -10	4 = 5	5 = 0	6 = 9	7 = 0
0	X5	5	0	0	2	0.29	1	-0.36	-0.29
36	X1	31	1	0	-0.5	0.57	0	-0.29	-007
32	X2	12	0	1	1	-0.14	0	-0.07	0.14
	Z-Z0	1500	1 = 0	2 = 0	3 = 4	4 = 3	5 = 0	6 = 8	7 = 2

Рассчитываем таблицу до тех пор пока все j не станут неотрицательными.