Линейное программирование

Размещено на http:\\www.allbest.ru\

22

Задание 1

Известна матрица В, элемент которой - объем i-го продукта, потребляемого при производстве j-го продукта в модели Леонтьева; известен валовой продукт .

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

(В)=

=(8, 10, 9)

=(10, 11, 6).

РЕШЕНИЕ

Коэффициенты прямых затрат вычисляем по формуле

, , =0,33

, , =0,22

, , =0,22

Коэффициенты прямых затрат показывают затраты продукции i - й отрасли на производство единицы продукции j - й отрасли.

Отсюда матрица прямых затрат

(А)=

Матрица полных затрат

Так как = 0,504 не равен нулю, вычисляем матрицу полных затрат

= =

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

Для определения валового продукта необходимо решить матричное уравнение

Х = АХ+ У

Х = (Е - А)^-1У = SY

=

Х - вектор валового выпуска

Задание 2

Решите задачу линейного программирования. Найдите оптимальный план для неотрицательных значений переменных:

а) геометрическим методом;

б) симплекс-методом.

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

,

РЕШЕНИЕ

а) геометрическим методом

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

Первое ограничение рассмотрим как уравнение прямой: 32х₁ + х₂ = 8. Как известно, через две точки можно провести единственную прямую. Находим любые две точки, принадлежащие данной прямой. Пусть х₁ = 0, тогда х₂ = 8, и пусть х₂ = 0, тогда х₁ = 1/4. Через полученные точки проводим прямую. Для того чтобы определить расположение соответствующей полуплоскости относительно граничной прямой, подставляем координаты какой - либо точки (проще взять начало координат) в левую часть неравенства. Так, например, при подстановке значений х₁ = 0 и х₂ = 0 получаем 0 ? 0 (неверно). Следовательно, соответствующая полуплоскость располагается по отношению к граничной прямой по другую сторону, нежели начало координат.

Второе ограничение рассмотрим как уравнение прямой х₁ + 6х₂ =6. Находим любые две точки, принадлежащие данной прямой. Пусть х₁ = 0, тогда х₂ = 1, и пусть х₂ = 0, тогда х₁ = 6. Через полученные точки проводим прямую. Для того чтобы определить расположение соответствующей полуплоскости относительно граничной прямой, подставляем координаты начало координат в левую часть неравенства. Так, например, при подстановке значений х₁ = 0 и х₂ = 0 получаем 0 ? 6 (неверно). Следовательно, соответствующая полуплоскость располагается по отношению к граничной прямой по другую сторону, нежели начало координат.

Третье ограничение рассмотрим как уравнение прямой 2х₁ + х₂ = 4. Находим любые две точки, принадлежащие данной прямой. Пусть х₁ = 0, тогда х₂ = 4, и пусть х₂ = 0, тогда х₁ = 2. Через полученные точки проводим прямую. Для того чтобы определить расположение соответствующей полуплоскости относительно граничной прямой, подставляем координаты начала координат в левую часть, при подстановке значений х₁ = 0 и х₂ = 0 получаем 0 ? 4 (верно). Следовательно, область решения этого неравенства включает начало координат.

Таким образом получили область ограниченную граничными линиями, а именно: треугольник АВС.

Градиент функции F равен grad F = (7; 2). Строим соответствующую точку и из начала координат проводим вектор в эту тоску. Затем прямую, перпендикулярную построенному градиенту, перемещаем на множеством планов. Точка первого касания - т. В. Ее координаты будут оптимальным планом для задачи минимизации.

Размещено на http:\\www.allbest.ru\

22

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

Точка В получается при пересечении второй и третьей прямой. Для нахождения ее координат решаем систему двух уравнений:

Отнимая от удвоенного первого уравнения второе, получим:

11х₂ = 8, или х₂ = 8/11.

Подставляя полученное значение в первое уравнение имеем: х₁ + 6· = 6, откуда получаем х₁ =

Соответствующее значение функции:

F_max = 7• + 2· =

Х_опт= (; ); F_max =

б) симплекс-методом.

,

С помощью дополнительных неотрицательных переменных перейдем к системе уравнений

Разобьем переменные на две группы: основные и неосновные переменные.

1 шаг

основные: х₃, х₄, х₅

неосновные: х₁, х₂

Выразим основные переменные через неосновные

Полагая неосновные переменные равными нулю, получим Х₁(0;0;-8;-6;4) - первое базисное решение недопустимое, так как х₃ и х₄ меньше нулю.

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

Например, х₂

х₂ = min {8; 1; 4} = 1

Меняем х₂ и х₄

2 шаг

основные: х₃, х₂, х₅

неосновные: х₁, х₄

Выразим основные переменные через неосновные

Полагая неосновные переменные равными нулю, получим Х₂(0;1;-7;0;3) - второе базисное решение недопустимое, так как х₃ меньше нулю.

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

Например, х₁

х₁ = min {; 6; } =

Меняем х₁ и х₅

3 шаг

основные: х₃, х₂, х₁

неосновные: х₅, х₄

Выразим основные переменные через неосновные

Полагая неосновные переменные равными нулю, получим Х₃(;;0;0) - третье базисное решение допустимое.

=

В функцию неосновные переменные входят с отрицательными коэффициентами, следовательно, функция максимальна.

Х_опт(;;0;0); F_max =

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

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

Так как задача на максимум приведем все неравенства системы к «?»

,

Расширенная матрица системы

	F

Матрица транспонированная к ней

	Z

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

Z = -8y₁-6y₂+4y₃

minZ(?y)=?

Задание 3

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

РЕШЕНИЕ

Решение

Матрица игры имеет вид

Аi\ Bj	B1	B2	B3
A1	6	5	6	5
A2	5	3	4	3
А3	3	7	5	3
	6	7	6

Выбирая стратегию А_i

В результате мы не выиграем меньше, чем .

Действуя наиболее осторожно, избегая всякого риска, мы останавливаемся на той стратегии А_i, которая обеспечит максимальный выигрыш .

= 5 - максимина - нижняя цена игры

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



Сам выигрыш

= 6 - минимакса - верхняя цена игры.

Т.к. ? , то седловая точка отсутствует и оптимальное решение следует искать в смешанных стратегиях игроков:

S_А^*=(р₁, р₂,р₃) и S_В^*=(q₁, q₂,q₃)

Обозначим x_i = p_i/v и y_j = q_j/v, составим две взаимнодвойственные задачи линейного программирования

Z = x₁ + x₂ + x₃ min

F = y₁ + y₂ + y₃ max

Решаем вторую задачу симплекс методом.

С помощью дополнительных неотрицательных переменных перейдем к системе уравнений



Разобьем переменные на две группы: основные и неосновные переменные.

1 шаг

основные: у₄, у₅, у₆

неосновные: у₁, у₂, у₃

Выразим основные переменные через неосновные

Полагая неосновные переменные равными нулю, получим У₁(0;0;0;1;1;1) - первое базисное решение допустимое.

Отсюда,

F = y₁ + y₂ + y₃ = 0

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

Выбираем любую переменную входящую с положительным коэффициентом в функцию F, например, y₁

у₁ = min {1/6; 1/5; 1/3} =

Меняем у₁ и у₄

2 шаг

основные: у₁, у₅, у₆

неосновные: у₄, у₂, у₃

Выразим основные переменные через неосновные

Полагая неосновные переменные равными нулю, получим У₂(;0;0;0;;) - второе базисное решение допустимое.

F = + y₂ - y₃ =

Перед у₂ положительный коэффициент, функция не максимальна.

у₂ = min {1/5; 1/7; 1/9} =

Меняем у₂ и у₆

3 шаг

основные: у₁, у₅, у₂

неосновные: у₄, у₆, у₃

Выразим основные переменные через неосновные



Полагая неосновные переменные равными нулю, получим У₃(;0;0;0) - третье базисное решение допустимое.

F_max = - y₃ - y₄ - =

Так как все коэффициенты перед неосновными переменными отрицательны, функция максимальная.

У_опт(;0;0;0)

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

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

F_max = Z_min =

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

Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой.

Введем дополнительные переменные в 1 задачу.

Переменные 1 задачи
первоначальные	дополнительные
х1 х2 х3 у4 у5 у6	х4 х5 х6 у1 у2 у3
дополнительные	первоначальные
Переменные 2 задачи

Так как

F_max = - y₃ - y₄ - ,

То

Х_опт(; 0;;0;0; )

У_опт(;0;0;0)

Отсюда

Z_min = + + +

Поэтому цена игры

= = = 5,4

Возвращаясь к исходным переменным

S_А^*=(р₁, р₂,р₃) и S_В^*=(q₁, q₂,q₃)

Находим p_i = x_i·v и q_j = y_j·v

S_А^*=(; 0; ) и S_В^*= (; 0)

Таким образом первому игроку надо использовать 80% стратегию 1 и 20% третью стратегию, а второму игроку 40% первую стратегию и 60% вторую, тогда выигрыш будет 5,4.

Задание 4

Задан проект сетевого графика строительства объекта, даны нормативы длительности работ (в днях).

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

Размещено на http:\\www.allbest.ru\

22

РЕШЕНИЕ

Пронумеруем события

Размещено на http:\\www.allbest.ru\

22

Расставим над стрелочками продолжительность работы.

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

Наиболее раннее время (минимальное) возможного наступления события j (T_j^p) равно максимальной длине пути из входа в j - событие.

Критическим временем (Т_кр) выполнения проекта называется время наступления последнего события.

То есть это минимальное время, в пределах которого коллектив исполнителей в состоянии выполнить весь комплекс работ сетевого графика.

М_j длина пути наибольшей протяженности от события j до события N. Тогда

М_j = j<N; M_N = 0

Величина T_jⁿ = T_кр - M_j соответствует наиболее позднему допустимому времени наступления j - го события, то есть самому позднему сроку начала всех работ, последующих за этим событием.

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

j	Tjp	i	Mi	k	Tjn	ri
0	0	-	22	1	0	0
1	2	0	20	2,3	2	0
2	3	0,1	19	4	3	0
3	6	1	16	5	6	0
4	8	2	12	6	10	2
5	11	3	11	7	11	0
6	11	4	9	7	13	2
7	15	5	7	8	15	0
8	22	7	0	-	22	0

Рассчитываем значения T_j^p в порядке роста номеров, т.е.

T₀^p = 0; T₁^p = 2+ T₀^p = 2(i=0);

T₂^p = max{3+ T₀^p; 1+ T₁^p }= max {3+ 0;2+ 1}=3 (i=0,1);

T₃^p = 10+ T₀^p = 10 (i=0)

T₃^p = T₁^p+4 = 2+4 =6 (i=1)

T₄^p = 5+ T₂^p = 5+3 =8 (i=2)

T₅^p = T₃^p + 5 = 6+5 = 11 (i=3)

T₆^p = 3+ T₄^p = 8+3 = 11 (i=4)

T₇^p = max {8+ T₂^p;4+ T₅^p;2+ T₆^p } = max {8+ 3;4+ 11; 2+11} = 15(i=5);

T₈^p = max {6+ T₅^p; 7+ T₇^p} = max {6+11^; 7+15} = 22 (i=7)

Затем рассчитываем значения М_j в порядке убывания номеров.

М₈= 0

М₇ = М₈ + 7 = 7(k= 8)

М₆ = М₇ + 2 = 7+2 = 9(k= 7)

М₅ = max {6+ М₈; 4+ М₇} = max {8+ 0; 4+7} = 11(k= 7)

М₄ = М₆ + 3 = 12(k= 6)

М₃ = М₅ + 5 = 16 (k= 5)

М₂ = max {8+ М₇; 5+ М₄} = max {8+ 7; 5+12} = 19 (k= 4);

М₁ = max {4+ М₃; 1+ М₂} = max {4+ 16; 1+19} = 20 (k= 2,3);

М₀ = max {1+ М₂; 2+ М₁ } = max {1+ 19; 2+20} = 22(k=1)

Критическое время T_кр = 22

Вычисляем наиболее позднему допустимому времени наступления j - го события:

T_jⁿ = 22 - M_j

Резерв времени событий находим по формуле

r_i = T_jⁿ - T_j^p

По информации из колонок 3 и 5 можно выявить критический путь с длиной 22: Р = {0; 1; 3; 5;7;8}. Найденный критический путь выделим на графике.

Размещено на http:\\www.allbest.ru\

22

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

Используют следующие резервы времени:

1. полный резерв

r_ij = T_jⁿ - T_i^p - t_ij

2. свободный резерв

r_ij = T_j^p - T_i^p - t_ij

3. независимый резерв

r_ij = max[T_j^p - T_i^п - t_ij, 0]

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

Полный резерв

r₀₁ = T₁ⁿ - T₀^p - t₀₁ = 2-0-2 = 0

r₀₂ = T₂ⁿ - T₀^p - t₀₂ = 3-0-3 = 0

r₁₂ = T₂ⁿ - T₁^p - t₁₂ = 3-2-1 = 0

r₁₃ = T₃ⁿ - T₁^p - t₁₃ = 6-2-4= 0

r₂₄ = T₄ⁿ - T₂^p - t₂₄ = 10-3-5 = 2

r₂₇ = T₇ⁿ - T₂^p - t₂₇ = 15-3-8 = 4

r₃₅ = T₅ⁿ - T₃^p - t₃₅ = 11-6-5 = 0

r₄₆ = T₆ⁿ - T₄^p - t₄₆ = 13-8-3 = 2

r₅₇ = T₇ⁿ - T₅^p - t₅₇ = 15-11-4 = 0

r₅₈ = T₈ⁿ - T₅^p - t₅₈ = 22-11-6 = 5

r₆₇ = T₇ⁿ - T₆^p - t₆₇ = 15-11-2 = 2

r₇₈= T₈ⁿ - T₇^p - t₇₈ = 22-17-7 = 0

свободный резерв

r₀₁ = T₁^р - T₀^p - t₀₁ = 2-0-2 = 0

r₀₂ = T₂^р - T₀^p - t₀₂ = 3-0-3 = 0

r₁₂ = T₂^р - T₁^p - t₁₂ = 3-2-1 = 0

r₁₃ = T₃^р - T₁^p - t₁₃ = 6-2-4= 0

r₂₄ = T₄^р - T₂^p - t₂₄ = 8-3-5 = 0

r₂₇ = T₇^р - T₂^p - t₂₇ = 15-3-8 = 4

r₃₅ = T₅^р - T₃^p - t₃₅ = 11-6-5 = 0

r₄₆ = T₆^р - T₄^p - t₄₆ = 11-8-3 = 0

r₅₇ = T₇^р - T₅^p - t₅₇ = 15-11-4 = 0

r₅₈ = T₈^р - T₅^p - t₅₈ = 22-11-6 = 5

r₆₇ = T₇^р - T₆^p - t₆₇ = 15-11-2 = 2

r₇₈= T₈^р - T₇^p - t₇₈ = 22-17-7 = 0

независимый резерв

r₀₁ = max [T₁^р - T₀^п - t₀₁;0]= max [2 - 0 - 2;0]= 0

r₀₂ = max [T₂^р - T₀^п - t₀₂;0]= max [3 - 0 - 3;0]= 0

r₁₂ = max [T₂^р - T₁^п - t₁₂;0]= max [3 - 2 - 1;0]= 0

r₁₃ = max [T₃^р - T₁^п - t₁₃;0]= max [6 - 2 - 4;0]=0

r₂₄ = max [T₄^р - T₂^п - t₂₄;0]= max [8 - 3 - 5;0]= 0

r₂₇ = max [T₇^р - T₂^p - t₂₇;0]= max [15 - 3 - 8;0]= 4

r₃₅ = max [T₅^р - T₃^п - t₃₅;0]= max [11 - 6 - 5;0]= 0

r₄₆ = max [T₆^р - T₄^п - t₄₆;0]= max [11 - 10 - 3;0]= 0

r₅₇ = max [T₇^р - T₅^п - t₅₇;0]= max [15 - 11 - 4;0]=0

r₅₈ = max [T₈^р - T₅^п - t₅₈;0]= max [22 - 11 - 6;0]=5

r₆₇ = max [T₇^р - T₆^п - t₆₇;0]= max [15 - 13 - 2;0]= 0

r₇₈ = max [T₈^р - T₇^п - t₇₈;0]= max [22 - 15 - 8;0]= 0

Результаты обработки сетевого графика представим следующей таблицей.

работа	Продолжи-тельность	Раннее время	Позднее время	Резервы времени
		начала	конца	начала	Конца	Полн.	Своб.	Незав
0-1	2	0	2	0	2	0	0	0
0-2	3	0	3	2	5	0	0	0
1-2	1	2	3	4	5	0	0	0
1-3	4	2	6	2	6	0	0	0
2-4	5	3	8	5	10	2	0	0
2-7	8	3	11	7	15	4	4	4
3-5	5	6	11	6	11	0	0	0
4-6	3	8	11	10	13	2	0	0
5-7	4	11	15	11	15	0	0	0
5-8	6	11	17	16	22	5	5	5
6-7	2	11	13	13	15	2	2	0
7-8	7	15	22	15	22	0	0	0

Задание 5

линейный программирование оптимизация сетевой график

В операционном отделении банка с одинаковой интенсивностью работает l операторов. Известно среднее время обслуживания клиента оператором (в мин.). Наблюдения показали, что в два часа в среднем банк посещают S клиентов. Проведите анализ работы операторов, рассчитав вероятность отсутствия работы для операторов; вероятность нахождения клиента в очереди, состоящей более чем из 3-х человек; среднее число клиентов, находящихся в очереди и на обслуживании, среднее число клиентов в очереди; среднее время пребывания клиента в очереди и на обслуживании; среднее время пребывания клиента в очереди. Определите оптимальное для Вашего варианта число операторов.

l=2, = 8мин, S=34

РЕШЕНИЕ

Имеем двухканальную СМО, на которую поступает поток заявок с интенсивностью

Интенсивность потока обслуживания

Приведенная интенсивность потока заявок (трафик) показывает среднее число заявок, приходящее за среднее время обслуживания одной заявки

Так как

= 1,14 > 1,

то очередь будет расти до бесконечности, предельные вероятности отсутствуют.

Вероятность отсутствия работы для операторов равна 0.

Размещено на allbest.ru