Линейное программирование
Применение графического и симплексного методов, метода симплекс-таблиц, для решения задач линейного программирования заданных в различном виде. Составление двойственной задачи. Установление сопряженных пар переменных прямой и двойственной задачи.
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 28.02.2012 |
Размер файла | 532,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
РАСЧЕТНЫЙ РАЗДЕЛ
В расчетном разделе нужно выполнить следующее:
1. Решить задачу линейного программирования графическим методом.
Пример:
z=4x1+8x2>max(min)
1. Построим граничные линии
2. Найдём многогранник решений
Для этого возьмём точку (0;0),подставим её координаты в те неравенства полуплоскость которых мы определяем
0+2*0?-8 0+0?7 0?6 0+2*0?4
0?-8 -верно 0?7 - верно 0?6 - верно 0?4 - неверно
3.Построим прямую Z=4x1+8x2 при z=0
z=0;
4x1+8x2=0
x2=- *x1
4. Построим вектор
Для построения вектора в качестве начальной точки используем начало координат ,а в качестве конечной точки точку с координатами (4;8)
:(0;0)(4;8)
5. Найдём координаты точки максимума и минимума
Для нахождения максимума прямую перемещают ,вдоль вектора параллельным переносом по направлению данного вектора .
Для нахождения минимума, прямую перемещают вдоль вектора в обратном направлении параллельным переносом в обратную сторону.
B(0;2) - min
6. Найдём значение целевой функции в полученных точках.
Подставим координаты полученных точек в целевую функцию вместо неизвестных переменных в результате получим:
zmax=4*2+8*6=48
zmax=4*0+8*2=16
В результате решения получили график:
Точка максимума=(2,6); Точка минимума=(0,2);
Задание №1.2
Решение задачи линейного программирования симплекс-таблицами.
z=4x1+8x2>max(min)
Решение:
1.Заменим систему неравенств системой уравнений, добавив дополнительные переменные (базисные)
1 опорный план: (0,0,8,7,-4,6) - недопустимое базисное решение с двумя отрицательными компонентами.
Так как одна из дополнительных переменных имеет противоположный знак свободного члена то введём искусственную переменную y1 имеющую положительный знак.
2. Приведём задачу к канонической форме
h=-y1
y1=4-x1-2x2+x5
h=-(-4+x1+2x2-x5)
Запишем нуль-уравнение для функции z и h.
z=0-(-4x1-8x2)
h=-(-4+x1+2x2-x5)
h=-4-(x1+2x2-x5)
3.Составим первую симплексную таблицу
Базис |
Св.член |
Переменные |
Оц. Отношения |
|||||||
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
y1 |
||||
x3 |
8 |
-1 |
2 |
1 |
0 |
0 |
0 |
0 |
4 |
|
x4 |
7 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
7 |
|
x5 |
4 |
1 |
2 |
0 |
0 |
-1 |
0 |
1 |
2 |
|
x6 |
6 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
? |
|
z |
0 |
-4 |
-8 |
0 |
0 |
0 |
0 |
0 |
? |
|
h |
-4 |
-1 |
-2 |
0 |
0 |
1 |
0 |
0 |
В строке h все коэффициенты записи должны быть положительными, критерий оптимальности не выполняется.
Поэтому выбираем значение (-2) так как оно наибольшее по модулю отрицательное значение,х2 - разрешающий столбец и он идёт в базис вместо x5.
Составим оценочные отношения для этого значения свободного члена делим на значение разрешающего столбца.
В случае если в ячейках одного из этих столбцов будет стоять 0 или отрицательный коэффициент то оценочное отношение равно бесконечности.
В столбце оценочные отношения выбираем минимальный положительный элемент ,та строка в которой стоит этот элемент становится разрешающей строкой.
Элемент который стоит на пересечении разрешающего столбца и разрешающей строки называется разрешающий элемент.
Переходим к следующей таблице
Базис |
Св.член |
Переменные |
Оц. Отношения |
|||||||
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
y1 |
||||
x3 |
4 |
-2 |
0 |
1 |
0 |
1 |
0 |
-1 |
||
x4 |
5 |
0,5 |
0 |
0 |
1 |
0,5 |
0 |
-0,5 |
||
x5 |
2 |
0,5 |
1 |
0 |
0 |
-0,5 |
0 |
0,5 |
||
x6 |
6 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
||
z |
16 |
0 |
0 |
0 |
0 |
-4 |
0 |
4 |
||
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
В строке h все коэффициенты положительны, поэтому отбрасываем эту строку и столбец искусственной переменной y1.
Так как в строке z нет положительных элементов, то zmin=16
Переходим к следующей таблице
Базис |
Св.член |
Переменные |
Оц. Отношения |
||||||
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
||||
x3 |
4 |
-2 |
0 |
1 |
0 |
1 |
0 |
4 |
|
x4 |
5 |
0,5 |
0 |
0 |
1 |
0,5 |
0 |
10 |
|
x5 |
2 |
0,5 |
1 |
0 |
0 |
-0,5 |
0 |
? |
|
x6 |
6 |
1 |
0 |
0 |
0 |
0 |
1 |
? |
|
z |
16 |
0 |
0 |
0 |
0 |
-4 |
0 |
Дальше решаем до тех пор пока выполнится критерий оптимальности
Так как в строке z есть отрицательный элемент то столбец x5 становится разрешающим столбцом и уходит в базис вместо переменной x3 далее составляем оценочные отношения выбираем наименьший элемент и x3-разрешающяя строка.
Переходим к следующей таблице
Базис |
Св.член |
Переменные |
Оц. Отношения |
||||||
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
||||
x5 |
4 |
-2 |
0 |
1 |
0 |
1 |
0 |
? |
|
x4 |
3 |
1,5 |
0 |
-0,5 |
1 |
0 |
0 |
2 |
|
x2 |
4 |
-0,5 |
1 |
0,5 |
0 |
0 |
0 |
? |
|
x6 |
6 |
1 |
0 |
0 |
0 |
0 |
1 |
6 |
|
z |
32 |
-8 |
0 |
4 |
0 |
0 |
0 |
Так как в строке z есть отрицательный элемент то столбец x1 становится разрешающим столбцом и уходит в базис вместо переменной x4 далее составляем оценочные отношения выбираем наименьший элемент и x4-разрешающяя строка.
Переходим к следующей таблице:
Базис |
Св.член |
Переменные |
Оц. Отношения |
||||||
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
||||
x5 |
8 |
0 |
0 |
0,3333 |
1,33333 |
1 |
0 |
||
x4 |
2 |
1 |
0 |
-0,333 |
0,66667 |
0 |
0 |
||
x2 |
5 |
0 |
1 |
0,3333 |
0,33333 |
0 |
0 |
||
x6 |
4 |
0 |
0 |
0,3333 |
-0,6667 |
0 |
1 |
||
z |
48 |
0 |
0 |
1,3333 |
5,33333 |
0 |
0 |
Так как в строке z нет отрицательных элементов то критерий оптимальности выполняется.
zmax=48
zmin=16
Решить задачу симплекс-методом c использованием искусственного базиса на нахождение минимума линейной функции
zmin=4x1+8x2
1. Заменим систему неравенств, системой уравнений, и введем искусственный базис
2. Преобразуем функцию z
Z=4x1+8x2 + 0x3+0x4+0x5+0x6+y1M
3. Подставим y1 в функцию z
z=4x1+8x2+M(4-x1-2x2+x5)=4x1+8x2+4M-x1M-2x2M+x5M
z=x1(4-M)+x2(8-2M)+x5M+4M
z=4M-(x1(M-4)+x2(2M-8)-x5M)
4. Найдем 1 опорное решение
Пусть x1=x2=x5=0
y1=4 x3=8 x4=7 x6=6
(0,0,8,7,0,6,4)
zmin=4M
5. Так как переменная x2 имеет положительный знак, то она идёт в базис.
Выразим переменную x2 из всех уравнений
Пусть x1=x3=x4=x5=y1=0
Так как x2=2 минимальное значение, то x2 выражаем из третьего уравнения и вставляем в остальные.
x3=8+x1-2(2-x1+x5-y1)=8+x1-4+x1-x5+y1=4+2x1-x5+y1
x4=7-x1-2+x1-x5+y1=5-x1+y1
Подставим x2 в функцию z
z=4M-(x1(M-4)+2-x1+x5-y1)(2M-8)-x5M)=4M(x1(M-4)+4M-x1M+x5M-y1M-16+4x1-4x5+4y1-x5M)=16-(x1M-4x1-x1M+x5M-y1M+4x1-4x5+4y1-x5M)=16-(y1(4-M)-4x5)
Ответ: zmin=16
Задание №2
Построение математической модели задачи линейного программирования по исходным данным и решение ее симплекс-методом.
Для реализации 3-х групп товаров коммерческое предприятие располагает 3-мя видами ограниченных материально-денежных ресурсов в количестве B1,B2,B3 единиц. При этом для продажи первой группы товаров на 1тыс. руб. товарооборота расходится ресурса 1-го вида в количестве A11 единиц
Ресурса второго видав количестве A21 единиц ресурса третьего вида в количестве A31 единиц. Для продажи второй и третьей групп товаров на 1тыс.руб.товарооборота расходится соответственно ресурса первого вида в количестве A22,A23 единиц ,ресурсов третьего вида в количестве A32,A33 единиц
Прибыль от продажи трёх групп товаров на 1тыс.руб. товарооборота составляет соответственно c1,c2,c3(тыс.руб.).Определить плановый объём и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
изделия |
Нормы расхода ресурса на одну группу товаров |
Прибыль от продажи одной группы товаров(т.руб) |
|||
B1 |
B2 |
B3 |
|||
1 группа товаров |
10 |
5 |
10 |
8 |
|
2 группа товаров |
26 |
13 |
4 |
6 |
|
3 группа товаров |
3 |
4 |
2 |
6 |
|
Запасы сырья |
670 |
520 |
480 |
max |
Решение
Пусть х1- первая группа товаров ,x2 - вторая группа товаров,x3 - третья группа товаров
Тогда учитывая количество материально-денежных ресурсов получим систему ограничений
Z=8х1+6х2+6х3>max
Решим данную задачу используя метод симплекс-таблиц
1. Заменим систему неравенств системой уравнений, добавив дополнительные переменные (базисные)
2.Приведём задачу к канонической форме
10*x1+5*x2+10*x3+1*x4+0*x5+0*x6=670
26*x1+13*x2+4*x3+0*x4+1*x5+0*x6=520
3*x1+4*x2+2*x3+0*x4+0*x5+1*x6=48
Z=0-(-8*x1-6*x2-6*x3-0*x4-0*x5-0*x6)->max
Базис |
Св. член |
Переменные |
Оцен. отношения |
||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||
x4 |
670,00 |
10,00 |
5,00 |
10,00 |
1,00 |
0,00 |
0,00 |
67,00 |
|
x5 |
520,00 |
26,00 |
13,00 |
4,00 |
0,00 |
1,00 |
0,00 |
20,00 |
|
x6 |
480,00 |
3,00 |
4,00 |
2,00 |
0,00 |
0,00 |
1,00 |
160,00 |
|
z |
0,00 |
-8,00 |
-6,00 |
-6,00 |
0,00 |
0,00 |
0,00 |
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||
x4 |
-930,00 |
0,00 |
-8,33 |
3,33 |
1,00 |
0,00 |
-3,33 |
-279,00 |
|
x5 |
-3640,00 |
0,00 |
-21,67 |
-13,33 |
0,00 |
1,00 |
-8,67 |
273,00 |
|
x1 |
160,00 |
1,00 |
1,33 |
0,67 |
0,00 |
0,00 |
0,33 |
240,00 |
|
z |
1280,00 |
0,00 |
4,67 |
-0,67 |
0,00 |
0,00 |
2,67 |
||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||
x4 |
-1730,00 |
-5,00 |
-15,00 |
0,00 |
1,00 |
0,00 |
-5,00 |
||
x5 |
-440,00 |
20,00 |
5,00 |
0,00 |
0,00 |
1,00 |
-2,00 |
||
x3 |
240,00 |
1,50 |
2,00 |
1,00 |
0,00 |
0,00 |
0,50 |
||
z |
1440,00 |
1,00 |
6,00 |
0,00 |
0,00 |
0,00 |
3,00 |
Критерий оптимальности выполнен Zmax=1440.00
Задание №3. Решение двойственной задачи линейного программирования
Используя вариант задания 2, необходимо:
1. к прямой задаче планирования товарооборота, решаемой симплексным методом, составить двойственную задачу линейного программирования;
2. установить сопряженные пары переменных прямой и двойственной задач;
согласно сопряженным парам переменных, из решения прямой задачи получить решение двойственной задачи, в которой производится оценка ресурсов, затраченных на продажу товаров.
Решение
Составим задачу, двойственную следующей задаче:
Z=8х1+6х2+6х3>max
при ограничениях
Составим расширенную матрицу системы.
Найдем матрицу H3, транспонированную к А.
А'
Сформулируем двойственную задачу.
z=670y1+520y2+480y3>min
При ограничениях:
Решим данную задачу, используя метод симплекс-таблиц.
Введем искусственный базис.
Запишем нуль-уравнение для функции z и h.
z=0-(-670у1-520у2-480у3)
h=-(20-25y1-43y2-9y3+y4+y5+y6)=-20-(-25y1-43y2-9y3+y4+y5+y6)
Составим первую симплекс-таблицу.
Критерий оптимальности не выполним. Т.к. -43 наибольшее по модулю отрицательное число, y2 - разрешающий столбец, составим столбец оценочных отношений, разделив столбец свободных членов на разрешающий столбец. Получим следующую таблицу
Базис |
Св. член |
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
x1 |
x2 |
x3 |
Оц. Отн. |
|
у4 |
8,00 |
10,00 |
26,00 |
3,00 |
-1,00 |
0,00 |
0,00 |
1,00 |
0,00 |
0,00 |
0,31 |
|
у5 |
6,00 |
5,00 |
13,00 |
4,00 |
0,00 |
-1,00 |
0,00 |
0,00 |
1,00 |
0,00 |
0,46 |
|
у6 |
6,00 |
10,00 |
4,00 |
2,00 |
0,00 |
0,00 |
-1,00 |
0,00 |
0,00 |
1,00 |
1,50 |
|
z |
0,00 |
-670,00 |
-520,00 |
-480,00 |
0,00 |
0,00 |
0,00 |
0,00 |
0,00 |
0,00 |
||
h |
-20,00 |
-25,00 |
-43,00 |
-9,00 |
1,00 |
1,00 |
1,00 |
0,00 |
0,00 |
0,00 |
||
У2 |
0,31 |
0,38 |
1,00 |
0,12 |
-0,04 |
0,00 |
0,00 |
0,04 |
0,00 |
0,00 |
0,80 |
|
у5 |
2,00 |
0,00 |
0,00 |
2,50 |
0,50 |
-1,00 |
0,00 |
-0,50 |
1,00 |
0,00 |
? |
|
у6 |
4,77 |
8,46 |
0,00 |
1,54 |
0,15 |
0,00 |
-1,00 |
-0,15 |
0,00 |
1,00 |
0,56 |
|
z |
160,00 |
-470,00 |
0,00 |
-420,00 |
-20,00 |
0,00 |
0,00 |
20,00 |
0,00 |
0,00 |
||
h |
-6,76923 |
-8,4615 |
0 |
-4,038 |
-0,654 |
1 |
1 |
1,6538 |
0 |
0 |
||
У2 |
0,09 |
0,00 |
1,00 |
0,05 |
-0,05 |
0,00 |
0,05 |
0,05 |
0,00 |
-0,05 |
2,00 |
|
у5 |
2,00 |
0,00 |
0,00 |
2,50 |
0,50 |
-1,00 |
0,00 |
-0,50 |
1,00 |
0,00 |
0,80 |
|
У1 |
0,56 |
1,00 |
0,00 |
0,18 |
0,02 |
0,00 |
-0,12 |
-0,02 |
0,00 |
0,12 |
3,10 |
|
z |
424,91 |
0,00 |
0,00 |
-334,55 |
-11,45 |
0,00 |
-55,55 |
11,45 |
0,00 |
55,55 |
||
h |
-2 |
0 |
0 |
-2,5 |
-0,5 |
1 |
0 |
1,5 |
0 |
1 |
||
у2 |
0,05 |
0,00 |
1,00 |
0,00 |
-0,05 |
0,02 |
0,05 |
0,05 |
-0,02 |
-0,05 |
||
у3 |
0,80 |
0,00 |
0,00 |
1,00 |
0,20 |
-0,40 |
0,00 |
-0,20 |
0,40 |
0,00 |
||
у1 |
0,42 |
1,00 |
0,00 |
0,00 |
-0,02 |
0,07 |
-0,12 |
0,02 |
-0,07 |
0,12 |
||
z |
692,55 |
0,00 |
0,00 |
0,00 |
55,45 |
-133,82 |
-55,55 |
-55,45 |
133,82 |
55,55 |
||
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
Отбрасываем строку h и столбцы xi , т.к. в строке нет отрицательных элементов
Базис |
Своб. член |
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
Оценочные Отношения |
|
у2 |
0,05 |
0,00 |
1,00 |
0,00 |
-0,05 |
0,02 |
0,05 |
3 |
|
у3 |
0,80 |
0,00 |
0,00 |
1,00 |
0,20 |
-0,40 |
0,00 |
? |
|
у1 |
0,42 |
1,00 |
0,00 |
0,00 |
-0,02 |
0,07 |
-0,12 |
5,75 |
|
z |
692,55 |
0,00 |
0,00 |
0,00 |
55,45 |
-133,82 |
-55,55 |
||
у5 |
3,00 |
0,00 |
55,00 |
0,00 |
-3,00 |
1,00 |
2,50 |
? |
|
у2 |
2,00 |
0,00 |
22,00 |
1,00 |
-1,00 |
0,00 |
1,00 |
? |
|
у1 |
0,20 |
1,00 |
-4,00 |
0,00 |
0,20 |
0,00 |
-0,30 |
1 |
|
z |
1094,00 |
0,00 |
7360,00 |
0,00 |
-346,00 |
0,00 |
279,00 |
||
у5 |
6,00 |
15,00 |
-5,00 |
0,00 |
0,00 |
1,00 |
-2,00 |
? |
|
у2 |
3,00 |
5,00 |
2,00 |
1,00 |
0,00 |
0,00 |
-0,50 |
? |
|
у4 |
1,00 |
5,00 |
-20,00 |
0,00 |
1,00 |
0,00 |
-1,50 |
? |
|
z |
1440,00 |
1730,00 |
440,00 |
0,00 |
0,00 |
0,00 |
-240,00 |
Критерий оптимальности выполнен.
zmin=1440.00
Fmin=Zmax
1440.00=1440.00
Ресурсы y1, y2, y3 являются дефицитными, следовательно, их ограниченный запас сдерживает рост максимальной прибыли исходной задачи. Ресурсы x4, x5, x6 являются избыточными, следовательно, увеличение объема этих ресурсов не влияет на оптимальный план выпуска продукции и на максимальную прибыль.
симплекс линейное программирование
Заключение
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать.
В ходе данной работы я научился применять графический метод для решения задач линейного программирования заданных в различном виде, симплексный метод, метод симплекс таблиц, а так же научился составлять для прямой задачи - двойственную.
Установил сопряженные пары переменных прямой и двойственной задачи.
Согласно сопряженным парам переменных из решения прямой задачи получил решение двойственной задачи, в которой производится оценка ресурсов затраченных на продажу товара.
Список литературы
1) Бакаев А.А - Математические методы в планировании и экономических расчетах
2) Карманов Б.Г - Математическое программирование
3) Кузнецов А.В - Руководство к решению задач по математическому программированию (стр.58-82)
4) Попов И.И. Партыка Т.Л. Математические методы. - Профессиональное образование,2000(стр.77-81)
5) Шикин Е.В - Математические методы и модели управления
Размещено на Allbest.ru
Подобные документы
Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Основы математического моделирования экономических процессов. Общая характеристика графического и симплексного методов решения прямой и двойственной задач линейного программирования. Особенности формулирования и методика решения транспортной задачи.
курсовая работа [313,2 K], добавлен 12.11.2010Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа [268,0 K], добавлен 17.02.2010Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.
контрольная работа [81,9 K], добавлен 14.09.2010Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат [583,3 K], добавлен 15.06.2010Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014