Симплексный метод

Задача 1.

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

Вариант 3.

Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях

Симплексный метод2x1 + x2 + x3 Ј 2

x1 - x2 + x3 Ј 1,

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

Решение.

Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5 і 0.

f(X) = - x1 - x2 + 2x3 ® max

Симплексный метод2x1 + x2 + x3 + x4 = 2

x1 - x2 + x3 + x5 = 1,

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

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

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

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


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

Cj


Ci

B -1 -1 2 0 0 Q




A1 A2 A3 A4 A5
0 A4 0 2 2 1 1 1 0 2:1 = 1

A5 0 1 1 -1 1 0 1 1:1 = 1

j - 0 1 1 -2 0 0
1 A4 0 1 1 2 0 1 -1 1:2 = 1/2

A3 2 1 1 -1 1 0 1

j - 2 3 -1 0 0 2
2 A2 -1 1/2 1/2 1 0 1/2 -1/2

A3 2 3/2 3/2 0 1 1/2 1/2

j - 5/2 7/2 0 0 1/2 3/2

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

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

х1 = 0, х2 = 1/2 = 0,5; х3 = 3/2 = 1,5; fmax = -1Ч0 - 1Ч0,5 + 2Ч1,5 = 2,5.

Задача 2.

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

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

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

Вариант 3.

Из 505 м2 ткани нужно сшить не более 150 женских и не более 100 детских платьев. На пошив одного женского и детского платья требуется соответственно 3 м2 и 1 м2 ткани. При реализации каждого женского платья получают 10 ден. единиц прибыли, а детского – 5 ден. единиц. Сколько нужно сшить женских и детских платьев, чтобы получить наибольшую прибыль?

Решение.

Задание 1.

Обозначим x1 и x2 количество женских и детских платьев, соответственно (план пошива). Очевидно, x1,2 і 0 и целые. Так как женских платьев должно быть не более 150, то x1 Ј 150, аналогично, для детских платьев получаем x2 Ј 100. Расход ткани на план пошива (x1, x2) составит 3x1 + x2 м2, эта величина не должна превышать запаса ткани 505 м2. Следовательно, должно выполняться неравенство 3x1 + x2 Ј 505.

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

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

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

f(X) = 10x1 + 5x2 ® max

3x1 + x2 Ј 505

x1 Ј 150

x2 Ј 100

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

Задание 2.

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

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

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

Проведем прямую x1 = 150 и выберем левую полуплоскость.

Проведем прямую x2 = 100 и выберем нижнюю полуплоскость.

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

Построим линию уровня целевой функции f(X) = 10x1 + 5x2 10x1 + 5x2 = 0 через точки (0; 0 ) и (-10; 20). Вектор-градиент {10; 5} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение.

Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку В.

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

Симплексный метод3x1 + x2 = 505,

x2 = 100.

Симплексный методx1 = 135,

x2 = 100.

fmах = 10 Ч135 + 5 Ч100 = 1850 ден. единиц.

Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане пошива следует сшить женских платьев 135 шт., детских – 100 шт. При этом прибыль составит 1850 ден. единиц и будет наибольшей.


Симплексный метод


Задание 3.

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

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

g(Y) = 505y1 + 150y2 + 100y3 ® min

3y1 + y2 і 10

y1 + y3 і 5

y1,2,3 і 0.

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

3Ч135 + 1Ч100 = 505

135 < 150

100 = 100.

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


Симплексный метод


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

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

Симплексный методy2 = 0

3y1 + y2 = 10

y1 + y3 = 5.

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

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

g(Y) = 505Ч10/3 + 150Ч0 + 100Ч5/3 = 5550/3 = 1850.

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

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

Задача 3.

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

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

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

Вариант 3.

Картофель из четырех районов должен быть перевезен в три хранилища. Запасы картофеля в районах соответственно равны 400 т, 500 т, 800 т и 500 т. Возможности хранилищ соответственно равны 700 т, 800 т и 700 т. Затраты на перевозку одной тонны картофеля из первого района в каждое из хранилищ равны соответственно 1, 4 и 3 ден. единиц; аналогичные затраты на перевозку из второго района составляют 7, 1 и 5 ден. единиц, из третьего - 4, 8 и 3 ден. единиц, из четвертого - 6, 2 и 8 ден. единиц. Найти план перевозок картофеля из районов в хранилища, при котором транспортные расходы были бы минимальными.

Решение.

Задание 1.


Мощности

поставщиков

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

700 800 700
400 1 4 3
500 7 1 5
800 4 8 3
500 6 2 8

Сумма мощностей поставщиков (запасы картофеля в всех районах) 400+500+800+500 = 2200, сумма мощностей потребителей (возможности всех хранилищ) 700+800+700 = 2200. Суммы равны, данная задача является транспортной задачей закрытого типа.

Задание 2.

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

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

х11 + х21 + х31 + х41 = 700

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

х13 + х23 + х33 + х43 = 700

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

х11 + х12 + х13 = 400

х21 + х22 + х23 = 500 (2)

х31 + х32 + х33 = 800

х41 + х42 + х43 = 500

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

F(X) = х11 + 4х12 + 3х13 +

+ 7х21 + х22 + 5x23 +

+ 4х31 + 8х32 + 3х33 +

+ 6х41 + 2х42 + 8х43 .

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

Задание 3.

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

Заполняем клетку (1; 1) х11 = min {700, 400} = 400, от поставщика 1 вывезено все, в строке 1 больше поставок нет. Заполняем клетку (2; 2) х22 = min {800, 500} = 500, от поставщика 2 вывезено все, в строке 2 больше поставок нет. Клетка (4; 2) х42 = min {800 - 500, 500} = 300, потребителю 2 все завезено, в столбец 2 больше поставок нет. Клетка (3; 3) х33 = min {700, 800} = 700, потребителю 3 все завезено, в столбец 3 больше поставок нет. Далее клетка (3; 1) х31 = 100. Клетка (4; 1) х41 = 200. Все клетки, в которые даны поставки, считаем занятыми, остальные – свободными. Первоначальный план перевозок задается таблицей 1.

Таблица 1.

Мощности

поставщиков

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

700 800 700
400

1

400

4 3 0
500 7

1

500

5 -4
800

4

100

8

3

700

-3
500

6

200

2

300

8 -5
vj 1 -3 0

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

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

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

Симплексный метод

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

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

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

F(X1) = 1*400 + 1*500 + 4*100 + 3*700 + 6*200 + 2*300 = 5200 ден. единиц будут минимальными при:

x11 = 400, x22 = 500, x31 = 100, х33 = 700, x41 = 200, x42 = 300, остальные xij = 0.

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

из первого района в первое хранилище - 400 т;

из второго района во второе хранилище - 500 т;

из третьего района в первое хранилище - 100 т,

в третье хранилище - 700 т;

из четвертого района в первое хранилище - 200 т,

во второе хранилище - 300 т.

Задача 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). Результаты моделирования и прогнозирования отразить на графике.

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

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


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

Решение.

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


Симплексный метод


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





Таблица 1.
Сглаживание ряда динамики
t Факт Y(t) Скользящая сумма Скользящее среднее
1 8,2 - -
2 8,6 24,6 8,20
3 7,8 23,6 7,87
4 7,2 22,5 7,50
5 7,5 21,5 7,17
6 6,8 20,4 6,80
7 6,1 18,1 6,03
8 5,2 16,7 5,57
9 5,4 15,3 5,10
10 4,7 - -

Симплексный метод


Задание 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 = 10.

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




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

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

Симплексный метод; Симплексный метод.

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

Получили трендовую модель: Симплексный метод.

Задание 4.

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











Таблица 3.
Расчетные величины для оценки адекватности модели










t Y(t) Yр(t) E(t) k E(t)2 E(t)-E(t-1) (E(t)-E(t-1))2 E(t)*E(t-1) IE(t)I:Y(t)*100
1 8,2 8,69 -0,48
0,24


5,915
2 8,6 8,26 0,35 1 0,12 0,83 0,69 -0,17 4,012
3 7,8 7,83 -0,03 0 0,00 -0,37 0,14 -0,01 0,321
4 7,2 7,40 -0,20 1 0,04 -0,17 0,03 0,00 2,708
5 7,5 6,97 0,54 1 0,29 0,73 0,53 -0,10 7,133
6 6,8 6,54 0,27 0 0,07 -0,27 0,07 0,14 3,897
7 6,1 6,11 -0,01 0 0,00 -0,27 0,07 0,00 0,082
8 5,2 5,68 -0,48 1 0,23 -0,47 0,22 0,00 9,135
9 5,4 5,25 0,15 1 0,02 0,63 0,40 -0,07 2,87
10 4,7 4,82 -0,12
0,01 -0,27 0,07 -0,02 2,447
S 67,5 67,5 0,00 5 1,01
2,22 -0,22 38,520

а) Близость математического ожидания остаточной компоненты нулю.

Сумма остатков равна 0. Расчетное значение критерия Стьюдента


Симплексный метод0.


Критическое значение ta = 2,23 больше расчетного, следовательно, математическое ожидание остаточной компоненты равно нулю.

б) Проверка остатков E(t) на случайность.

Критическое количество поворотных точек для n =10 равно 2.


Симплексный метод2.


Для данного ряда количество таких точек k = 5. Это больше 2, поэтому остатки E(t) случайные.

в) Проверка остатков E(t) на независимость.

Независимость (отсутствие автокорреляции) проверим, используя критерий Дарбина-Уотсона:


Симплексный метод, Симплексный метод2,20.


d > 2, преобразуем d' = 4 - d = 4 - 2,20 = 1,80, получили 1,36 < d' = 1,80 < 2. Это означает, что остатки не зависимы.

г) Проверка остатков на соответствие нормальному закону распределения.

Используется RS - критерий:

Симплексный метод, где Симплексный метод0,36.


Симплексный метод2,87,


RSт = 2,7 - 3,7; так как расчетное значение RS - критерия RSрасч = 2,87 попадает внутрь интервала от 2,7 до 3,7, то остатки E(t) подчиняются по нормальному закону распределения.

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

Задание 5.

Определим точность модели.

Среднее квадратическое отклонение от линии тренда


Симплексный метод0,36.


Средняя относительная ошибка


Симплексный метод.


Так как 3,85% < 5%, то точность модели высокая.

Задание 6.

Точечный прогноз для Y получим, подставляя в трендовую модель t =11 и t = 12.

Симплексный метод4,385; Симплексный метод3,955.

Для интервального прогноза найдем ширину интервала


Симплексный метод.


Для числа степеней свободы k = n -2 = 10 - 2 = 8 и уровня значимости a = 0,05 ta = 2,31.

Симплексный метод1,00; Симплексный метод1,04.

Границы интервалов прогноза: НГ = Yn+k - U(k), ВГ = Yn+k + U(k).

Результаты прогноза представлены таблицей 4.





Таблица 4.
Точечный и интервальный прогноз
t U(k) Yn+k p НГ ВГ
10 1,00 4,39 3,39 5,38
11 1,04 3,96 2,91 5,00

Построим график.


Симплексный метод


Задача 5.

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


Потребляющие отрасли Производящие отрасли Конечная продукция

1 2 3
1 200+10N 50+10N 300+10N 200+10N
2 150+10N 250+10N 0+10N 100+10N
3 230+10N 50+10N 150+10N 300+10N

Задание 1. Рассчитать объемы валовой продукции отраслей (форму­ла (6.2) учебника на с. 237).

Задание 2. Рассчитать матрицу коэффициентов прямых затрат А = (aij) (формула (6.4) учебника на с. 238).

Задание 3. Найти матрицу коэффициентов полных затрат B = (bij), используя формулу (6.16) учебника на с. 244.

Задание 4. Рассчитать объемы условно чистой продукции отраслей Zj, используя формулу (6.1) учебника на с. 236.

Задание 5. Представить в таблице полную схему межотраслевого баланса (в соответствии с принципиальной схемой МОБ; табл. 6.1 учебника на с.234).

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





Таблица 1.
Потребляющие отрасли Производящие отрасли Конечная продукция

1 2 3
1 230 80 330 230
2 180 280 30 130
3 260 80 180 330

Решение.

Задание 1.

Объем валовой продукции находим по формуле


Симплексный метод.


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


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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

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