Реферат: Линейное программирование

Задача 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 -4 -M Q

A1

A2

A3

A4

P1

A4

-4 3 1 -1 1 1 3:1 = 3

P1

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

j

- -5M-12 -M-5 -M+4 -2M-4 1

A4

-4 1/2 1/2 -3/2 1 1/2:1/2=1

A3

5/2 1/2 1/2 1 5/2:1/2=1 

j

- -2 -3 6 2

A1

1 1 1 -3 2

A3

2 2 1 -1  2:2=1

j

- 1 -3 6 3

A1

1 4 1 3/2 1/2

A2

1 1 1/2 -1/2

j

- 4 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,<sub/>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<sub/>³ 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

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<sub/>= 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<sub/>:

/>

Среди оценок естьотрицательная, следовательно план перевозок Х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

5

2

50

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<sub/>= 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<sub/>:

/>

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

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

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<sub/>принять равными при уровне значимости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 3 1 4 1 5 6 1 7 1 8 1 9 10 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.