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

Задача 1.

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

Вариант 2.

Найти наибольшее значение функции f(X) = x1 – 4x4 при ограничениях


Линейное программированиеx1 – x2 + x3 + x4 = 3

x1 + x2 + 2x3 = 5,

xj і 0, j = 1, 2, 3, 4.


Решение.

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

Для нахождения опорного плана переходим к М-задаче:


f(X) = x1 – 4x4 – Мy1 ® max

Линейное программированиеx1 – x2 + x3 + x4 = 3

x1 + x2 + 2x3 + y1 = 5,

xj і 0, j = 1, 2, 3, 4; y1і 0.


Очевидное начальное опорное решение (0; 0; 0; 3; 5).

Решение осуществляется симплекс-методом с искусственным базисом.

Расчеты оформим в симплекс-таблицах


Номер симплекс-таблицы Базис

Cj


Ci

B 1 0 0 -4 -M Q




A1 A2 A3 A4 P1
0 A4 -4 3 1 -1 1 1 0 3:1 = 3

P1 -M 5 1 1 2 0 1 5:2 = 2,5

j - -5M-12 -M-5 -M+4 -2M-4 0 0
1 A4 -4 1/2 1/2 -3/2 0 1
1/2:1/2=1

A3 0 5/2 1/2 1/2 1 0
5/2:1/2=1

j - -2 -3 6 0 0

2 A1 1 1 1 -3 0 2


A3 0 2 0 2 1 -1
2:2=1

j - 1 0 -3 0 6

3 A1 1 4 1 0 3/2 1/2


A2 0 1 0 1 1/2 -1/2


j - 4 0 0 3/2 9/2


Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в D - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P1, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P1 выводим из базиса, а А3 - вводим в базис.

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

После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в D - строке есть отрицательные значения, в столбце А1.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А1 - вводим в базис.

После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в D - строке есть отрицательные значения, в столбце А2. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А3. В качестве направляющей строки возьмем А3. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А3 выводим из базиса, а А2 - вводим в базис.

После пересчета получаем симплекс-таблицу 3. Опорное решение, соответствующее симплекс-таблице 3 (4; 1; 0; 0; 0) – оптимально, так как в D - строке нет отрицательных значений.

Отбрасывая значения переменной y1, получаем оптимальное решение исходной задачи:

х1 = 4, х2 = 1; х3 = 0; х4 = 0; fmax = 1Ч4 + 0Ч1 + 0Ч0 – 4Ч0 = 4.

Задача 2.

Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.

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

Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

Вариант 2.

Предприятие производит полки для ванных комнат двух размеров А и Б. Служба маркетинга определили, что на рынке может быть реализовано до 550 полок в неделю, а объем поставляемого на предприятие материала, из которого делаются полки, равен 1200 м2 в неделю. Для каждой полки типов А и Б требуется 2 м2 и 3 м2 материала соответственно, а затраты станочного времени на обработку одной полки типа А и Б составляют соответственно 12 и 30 минут. Общий недельный объем станочного времени равен 160 часов, а прибыль от продажи каждой полки типа А и Б составляет 3 и 4 ден. единиц соответственно. Определить, сколько полок каждого типа следует выпускать в неделю для получения наибольшей прибыли.

Решение.

Задание 1.

Обозначим x1 и x2 количество полок типа А и Б, соответственно (план выпуска). Очевидно, x1, x2 і 0 и целые.

Так как объем реализации в неделю составляет до 550 полок, то x1 + x2 Ј 550.

Расход материала составит 2x1 + 3x2 м2, эта величина не должна превышать запаса материала 1200 м2. Следовательно, должно выполняться неравенство 2x1 + 3x2 Ј 1200.

Затраты станочного времени составят 0,2x1 + 0,5x2 час. и не могут быть больше недельного объема 160 час. Следовательно, должно выполняться неравенство 0,2x1 + 0,5x2 Ј 160. Чтобы не было дробей, умножим его на 10 и получим 2x1 + 5x2 Ј 1600.

Прибыль от реализации полок составит f(X) = 3x1 + 4x2 ден. единиц, и она должна быть наибольшей

Получаем экономико-математическую модель задачи:

Найти максимум функции f(X) при заданных ограничениях

f(X) = 3x1 + 4x2 ® max

x1 + x2 Ј 550

2x1 + 3x2 Ј 1200

2x1 + 5x2 Ј 1600

x1, x2 і 0, целые.

Задание 2.

Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.

Прямые ограничения x1,2 і 0 выделяют первую четверть плоскости.

Проведем прямую x1 + x2 = 550 через точки (0; 550) и (550; 0). Подставим в первое неравенство координаты точки (0; 0): 1Ч0 +1Ч0 = 0 < 550, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x1 + 3x2 = 1200 через точки (0; 400) и (600; 0). Подставим в первое неравенство координаты точки (0; 0): 2Ч0 + 3Ч0 = 0 < 1200, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x1 + 5x2 = 1600 через точки (0; 320) и (800; 0). Подставим в первое неравенство координаты точки (0; 0): 2Ч0 + 5Ч0 = 0 < 1600, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Множество допустимых решений – это многоугольник ABCDO.

Построим линию уровня целевой функции f(X) = 3x1 + 4x2

3x1 + 4x2 = 0 через точки (200; -150 ) и (-200; 150).

Вектор-градиент {3; 4} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение. На чертеже построен вектор, пропорциональный градиенту (60; 80), так как сам градиент имеет малый масштаб на чертеже.

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

Координаты этой точки найдем из системы

Линейное программирование x1 + x2 = 550,

2x1 + 3x2 = 1200.

Первое уравнение умножим на 2 и вычтем из второго, получаем x2 = 100 и x1 = 450

fmах = 3 Ч450 + 4 Ч100 = 1750 ден. единиц.

Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане выпуска следует произвести полок типа А 450 шт., а полок типа Б – 100 шт.При этом прибыль от реализации составит 1750 ден. единиц и будет наибольшей.


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


Задание 3.

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

Найти минимум функции g(Y) при ограничениях:

g(Y) = 550y1 + 1200y2 + 1600y3 ® min

y1 + 2y2 + 2y3 і 3

y1 + 3y2 + 5y3 і 4

y1,2,3 і 0.

Оптимальное решение прямой задачи Х = (450; 100). Подставим его в ограничения этой задачи

1Ч450 + 1Ч100 = 550

2Ч450 + 3Ч100 = 1200

2Ч450 + 5Ч100 = 1400 < 1600

Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:

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


Так как для оптимального решения прямой задачи треть ограничение выполняется как неравенство, то в оптимальном решении двойственной задачи y3 = 0.

Так как для оптимального решения прямой задачи х1 > 0и х2 > 0, то оба ограничения двойственной задачи выполняются как равенство. Для нахождения решения двойственной задачи получаем систему


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

y1 + 2y2 + 2y3 = 3

y1 + 3y2 + 5y3 = 4


Получаем решение: y1 =, y2 = 1, y3 = 0.

Найдем значение целевой функции двойственной задачи:

g(Y) = 550Ч1 + 1200Ч1 + 1600Ч0 = 1750.

Получили gmin = fmax = 1750 ден. единиц.

Так как значения прямой и двойственной функций равны, то Y = (1; 1; 0) является оптимальным решением двойственной задачи (по первой теореме двойственности).

Задача 3.

Задание 1. Записать исходные данные задачи в виде транспортной таблицы, определить, открытой или закрытой является транспортная задача.

Задание 2. Сформулировать экономико-математическую модель исходной транспортной задачи.

Задание 3. Найти оптимальный план перевозок, отметив при этом единственность или неединственность оптимального плана.

Вариант 3.

На складах A, B, C, Д находится соответственно 50 т, 40 т, 40 т и 70 т муки, которую нужно доставить четырем хлебозаводам. Первому хлебозаводу требуется 50 т муки, второму – 40 т, третьему – 50 т и четвертому – 60 т муки. Стоимость доставки одной тонны муки со склада А каждому хлебозаводу соответственно равны 8, 3, 5 и 2 ден. единиц, со склада В – 7, 4, 9 и 8 ден. единиц, со склада С – 6, 3, 3 и 1 ден. единиц, со склада Д – 2, 4, 1 и 5 ден. единиц. Составить план перевозки муки, обеспечивающий минимальные транспортные расходы.

Решение.

Задание 1.


Мощности

поставщиков

Мощности потребителей

50 40 50 60
50 8 3 5 2
40 7 4 9 8
40 6 3 3 1
70 2 4 1 5

Сумма мощностей поставщиков (запасы муки на всех складах) 50+40+40+70 = 200, сумма мощностей потребителей (потребности всех хлебозаводов) 50+40+50+60 = 200. Суммы равны, данная задача является транспортной задачей закрытого типа.

Задание 2.

Обозначим xij объем поставок муки от i – го поставщика (склада) j – му потребителю (хлебозаводу), i = 1, 2, 3, 4; j = 1, 2, 3, 4. Очевидно, xij і 0. В закрытой транспортной задаче все ограничения являются равенствами.

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

х11 + х21 + х31 + х41 = 50

х12 + х22 + х32 + х42 = 40 (1)

х13 + х23 + х33 + х43 = 50

х14 + х24 + х34 + х44 = 60

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

х11 + х12 + х13 + х14 = 50

х21 + х22 + х23 + х24 = 40 (2)

х31 + х32 + х33 + х34 = 40

х41 + х42 + х43 + х44 = 70

Затраты на транспортировку составят

F(X) = 8х11 + 3х12 + 5х13 + 2х14+

+ 7х21 + 4х22 + 9x23 + 8х24+

+ 6х31 + 3х32 + 3х33 + 1х34+

+ 2х41 + 4х42 + 1х43 + 5х44+.

Требуется найти неотрицательное решение системы уравнений (1) – (2), на котором целевая функция затрат F(X) принимает минимальное значение.

Задание 3.

Начальный план перевозок находим методом минимальной стоимости:

Заполняем клетку (3; 4) х34 = min {60, 40} = 40, от поставщика 3 вывезено все, в строке 3 больше поставок нет. Заполняем клетку (4; 3) х43 = min {50, 70} = 50, потребителю 3 все завезено, в столбец 3 больше поставок нет. Клетка (1; 4) х14 = min {60 - 40, 50} = 20, потребителю 4 все завезено, в столбец 4 больше поставок нет. Клетка (4; 1) х41 = min {50, 70 - 50} = 20, от поставщика 4 вывезено все, в строке 4 больше поставок нет. Клетка (1; 2) х12 = min {40, 50 - 20} = 30, от поставщика 1 вывезено все, в строке 1 больше поставок нет. Клетка (2; 2) х22 = min {40 - 30, 40} = 10, потребителю 2 все завезено, в столбец 2 больше поставок нет. Клетка (2; 1) х21 = 30. Все клетки, в которые даны поставки, считаем занятыми, остальные – свободными. Первоначальный план перевозок задается таблицей 1.

Таблица 1.

Мощности

поставщиков

Мощности потребителей ui

50 40 50 60
50

8


3

30

5

2

20

0
40

7

30

4

10

9 8 -1
40 6 3 3

1

40

1
70

2

20

4

1

50

5 4
vj 6 3 5 2

Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: vj = cij + ui.

Пусть u1 = 0; по клетке (1; 2) находим v2 = 3; по клетке (1; 4) находим v4 = 2; по клетке (2; 2) находим u2 = -1; по клетке (2; 1) находим v1 = 6; по клетке (3; 4) находим u3 = 1; по клетке (4; 1) находим u4 = 4; по клетке (4; 3) находим v3 = 5.

Для всех клеток матрицы перевозок найдем оценки клеток dij = (ui + cij) - vj :

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

Среди оценок есть отрицательная, следовательно план перевозок Х0 (таблица 1) не оптимальный. Наименьшая оценка в клетке (3; 3).

Составим цикл пересчета и пометим клетки поочередно знаками «+» и «-»:

+ - + - + - + -

(3; 3), (3; 4), (1; 4), (1; 2), (2; 2), (2; 1), (4; 1), (4; 3).

В клетки с «+» переместим из клеток с «-» величину min{40; 30; 30; 50} = 30. В этом случае план перевозок станет таким ( таблица 2).


Таблица 2.

Мощности

поставщиков

Мощности потребителей ui

50 40 50 60
50

8


3

0

5

2

50

0
40

7


4

40

9 8 -1
40 6 3

3

30

1

10

1
70

2

50

4

1

20

5 3
vj 5 3 4 2

Освободилось две клетки (1; 2) и (2; 1). Клетку (1; 2) считаем занятой с нулевой поставкой.

Среди оценок нет отрицательных, следовательно план перевозок Х0 (таблица 1) оптимальный.

Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: vj = cij + ui.

Пусть u1 = 0; по клетке (1; 2) находим v2 = 3; по клетке (1; 4) находим v4 = 2; по клетке (2; 2) находим u2 = -1; по клетке (3; 4) находим u3 = 1; по клетке (3; 3) находим v3 = 4; по клетке (4; 3) находим u4 = 3; по клетке (4; 1) находим v1 = 5.

Для всех клеток матрицы перевозок найдем оценки клеток dij = (ui + cij) - vj :

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

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

Общие затраты на перевозки

F(X1) = 2*50 + 4*40 + 3*30 + 1*10 + 2*50 + 1*20 = 480 ден. единиц

будут минимальными при:

x14 = 50, x22 = 40, x33 = 30, х34 = 10, x41 = 50, x43 = 20, остальные xij = 0.

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

со склада А на четвертый хлебозавод - 50 т;

со склада В на второй хлебозавод - 40 т;

со склада С на третий хлебозавод - 30 т;

на четвертый хлебозавод - 10 т;

со склада Д на первый хлебозавод - 50 т;

на третий хлебозавод - 20 т.

Задача 4

В таблице приведены годовые данные о трудоемкости производства I т цемента (нормо-смен) (N —последняя цифра зачетной книжки студента):


Текущий номер года (t) 1 2 3 4 5 6 7 8 9 10
Трудоемкость 1 т цемента (yi) 7,9+0,N 8,3+0,N 7,5+0,N 6,9+0,N 7,2+0,N 6,5+0,N 5,8+0,N 4,9+0,N 5,1+0,N 4,4+0,N

Задание 1. Сгладить временной ряд методом простой скользящей средней, выбрав длину интервала сглаживания m = 3; результаты отра­зить на графике.

Задание 2. Определить наличие тренда во временном ряду методом Фостера - Стьюарта. Табличные значения статистики Стьюдента ta принять равными при уровне значимости a = 0.05 ta = 2,23 , а при a = 0,30 - ta = 1,09; другие необходимые табличные данные приведены в таблице 4.5 учебника на с.153 (описание метода Фостера - Стьюар­та см. учебник с. 151- 153).

Задание 3. Для исходного временного ряда построить линейную трендовую модель Линейное программирование, определив ее параметры на основе метода наименьших квадратов (соответствующую систему нормальных уравнений см. в учебнике на с. 196 формула (5.5)).

Задание 4. Оценить адекватность построенной модели на основе исследования

а) близости математического ожидания остаточной компоненты (ряда остатков) нулю; критические значения r-критерия принять равным тому числу, как указанно в задании 2;

б) случайности отклонений остаточной компоненты по критерию пиков (поворотных точек); Расчеты выполнить на основе соотношения 5.9. учебника на с. 200;

в) независимости уровней ряда остатков (отсутствие автокорреляции) на основе критерия Дарбина — Уотсона (см. учебник с. 203— 204), используя в качестве критических значений dl = 1.08 и d2 = 1,36; если критерий Дарбина — Уотсона ответа не дает, исследование независимости провести по первому коэффициенту автокорреляции:


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


где ei -- уровни остаточной компоненты;

Модуль первого коэффициента автокорреляции сравнить с критическим уровнем этого коэффициента, значение которого принять равным 0,36;

г) нормальности закона распределения уровней остаточной компоненты на основе RS-критерия;

В качестве критических значений принять интервал от 2,7 до 3,7 (см. учебник, стр. 201—-202).

Задание 5. Оценить точность построенной трендовой линейной модели, используя показатели среднего квадратического отклонения от линии тренда (формула (5,17) учебника на с. 210, k = 1) и средней относительной ошибки аппроксимации (формула (5.14) учебника на с. 204).

Задание 6. Построить точечный и интервальный прогноз трудоемкости производства 1 т цемента на два шага вперед (формула (5.18) учебника на с. 210). Результаты моделирования и прогнозирования отразить на графике.

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

Вариант 2. Условия при N = 2


Текущий номер года (t) 1 2 3 4 5 6 7 8 9 10
Трудоемкость 1 т цемента (yi) 8,1 8,5 7,7 7,1 7,4 6,7 6,0 5,1 5,3 4,6

Решение.

Задание 1. Сглаживание ряда Y(t) произведем по простой скользящей средней


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


Результаты в таблице 1.




Таблица 1.
Сглаживание ряда динамики
t Факт Y(t) Скользящая сумма Скользящее среднее
1 8,1 - -
2 8,5 24,3 8,10
3 7,7 23,3 7,77
4 7,1 22,2 7,40
5 7,4 21,2 7,07
6 6,7 20,1 6,70
7 6,0 17,8 5,93
8 5,1 16,4 5,47
9 5,3 15,0 5,00
10 4,6 - -

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


Задание 2.

Этап 1. Строим две числовые последовательности kt и lt


t kt lt
2 1 0
3 0 1
4 0 1
5 0 0
6 0 1
7 0 1
8 0 1
9 0 0
10 0 1

Этап 2. Находим величины


Линейное программирование7; Линейное программирование1 – 6 = -5.


Этап 3. Для n = 10 выпишем табличные значения m = 3,858; s1 = 1,288; s2 = 1,964.

Вычисляем


Линейное программирование2,44; Линейное программирование2,55.


Этап 4.

Так как расчетные значения ts = 2,44 и td = 2,55 больше табличного значения ta = 2,23, то в данном временном ряду присутствуют тренд и тенденция в дисперсии ряда.

Из таблицы 1 видно, что ряд Y(t) имеет тенденцию к снижению.

Задание 3. Линейную трендовую модель ищем в виде Линейное программирование. Параметры модели а0, а1 найдем, решив систему уравнений


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


n = 9.

Составим расчетную таблицу 2.




Таблица 2
t y t2 yt
1 8,1 1 8,1
2 8,5 4 17,0
3 7,7 9 23,1
4 7,1 16 28,4
5 7,4 25 37,0
6 6,7 36 40,2
7 6 49 42,0
8 5,1 64 40,8
9 5,3 81 47,7
10 4,6 100 46,0
55 66,5 385 330,3

Получаем систему

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

Получили 1,5а1 = -0,64, а1 = -0,64:1,5 = -0,43; а0 = 6,65 - 5,5а1 = 6,65 - 5,5Ч(-0,43) = 9,02.

Получили трендовую модель: Линейное программирование.

Задание 4.

Оценим качество модели. Для этого найдем расчетные значения Yp(t), подставляя t =1, …, 10 в трендовую модель, найдем отклонения расчетных значений от исходных E(t) = Y(t) - Yp(t). Для исследования модели на адекватность составим таблицу 3.


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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: