Исследование операций и принятие решения
Краткое сожержание материала:
20
Министерство общего и профессионального образования РФ
Южно-Уральский государственный университет
Кафедра «Системы управления»
Курсовая работа по дисциплине исследование операций
Вариант 4
Группа ПС-317
Выполнил: Гречишникова Л.А.
Проверил: Плотникова Н.В.
Челябинск 2004
Содержание
- ЗАДАНИЕ N1 3
- Условие 3
- Решение 4
- Ответ 11
- ЗАДАНИЕ N2 12
- Условие 12
- Решение 12
- Ответ 14
- ЗАДАНИЕ N3 15
- Условие 15
- Решение 15
- Ответ 19
- ЗАДАНИЕ N4 20
- Условие 20
- Решение 20
- Ответ 25
- Литература 26
ЗАДАНИЕ N1
Условие
На швейной фабрике «Шанель» для изготовления четырех видов изделий может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. Там же указаны имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида. Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной.
Артикул ткани |
Норма расхода ткани (м) на одно изделие вида |
Общее коли- чество ткани |
||||
1 |
2 |
3 |
4 |
|||
I |
а11 |
а12 |
а13 |
а14 |
b1 |
|
II |
а21 |
а22 |
а23 |
а24 |
b2 |
|
III |
а31 |
а32 |
а33 |
а34 |
b3 |
|
Цена одного изделия (руб.) |
с1 |
с2 |
с3 |
с4 |
№ вар. |
а11 |
а12 |
а13 |
а14 |
а21 |
а22 |
а23 |
а24 |
а31 |
а32 |
а33 |
а34 |
b1 |
b2 |
b3 |
с1 |
с2 |
с3 |
с4 |
|
1 |
1 |
0 |
2 |
1 |
0 |
1 |
3 |
2 |
4 |
2 |
0 |
4 |
180 |
210 |
800 |
9 |
6 |
4 |
7 |
Решение
1. Выберем элементы решения.
За элементы решения примем xi- количество i-го товара (элементов решений 4) i =
2. Составление системы ограничений
bj ,j = имеем 3 ограничения
3. Запишем целевую функцию.
L= max
4. Опираясь на условие задания и на перечисленные выше пункты, запишем математическую модель задачи.
L = 9*x1+6*x2+4*x3+7*x4 max
Приведем нашу математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств. Так как имеем неравенство вида меньше/ равно, тодобавочные переменные вводим в левую часть со знаком “+”. Получаем следующее:
ОЗЛП
L = 9*x1+6*x2+4*x3+7*x4 max
Теперь определимся с существованием решения найденной ОЗЛП. Подсчитаем число уравнений(m) и число переменных(n), найдем их разность(k) и сделаем вывод. Итак, m=3, n=7, k=n-m=4. Так как число линейно независимых уравнений(m) меньше числа переменных(n),то система совместна и у нее существует бесчисленное множество решений. При этом (n-m) переменным мы можем придавать произвольные значения (свободные) и остальные m переменных (базисные) будем выражать через свободные.
Свободные: x1, x2, x3, x4
Базисные: x5, x6, x7
L = 9*x1+6*x2+4*x3+7*x4 max
опорное решение
Так как в L коэффициент при x1 больше 0 и больше всех остальных коэффициентов при переменных, то переменную x1 будем увеличивать. Определим границу увеличения x1 следующим образом: возьмем два уравнения из системы ограничений;
x5 = -x1-2x3-x4+180
x7=-4x1-2x2-4x4+800
Определим значения x1, при которых каждая из переменных x5 , x7 обратится в 0.
x5 =0
x7=0
Увеличивать x1 можно до наименьшего из найденных значений необходимо поменять местами переменные x1 и x5.
Новое решение будет следующим:
Свободные: x2, x3, x4, x5 =0
Базисные: x1, x6, x7
L=9*(180-2*x3-x4-x5)+6*x2+4*x3+7*x4=1620-18*x3-9*x4-9*x5+6*x2+4*x3+7*x4 =1620+6*x2-14*x3-2*x4-9*x5max
L = 1620+6*x2-14*x3-2*x4-9*x5max
Так как в L коэффициент при x2 больше 0, то переменную x2 будем увеличивать. Определим границу увеличения x2 по уже описанной выше схеме.
x6 = 210-x2-3x3-2x4
x7 = 80-2x2+8x3+4x5
x6 =0
x7=0
необходимо поменять местами переменные x2 и x7.
Новое решение будет следующим:
Свободные: x7, x3, x4, x5 =0
Базисные: x1, x6, x2
L = 1620+6*(40-0,5*x7+4*x3+2*x5)-14*x3-2*x4-9*x5= 1620+240-3*x7+24* x3+12*x5-14*x3-2*x4-9*x5= 1860+10* x3-2*x4+3* x5-3*x7
L = 1860+10* x3-2*x4+3* x5-3*x7
Так как в L коэффициент при x3 больше 0, то переменную x3 будем увеличивать. Определим границу увеличения x3 по уже описанной выше схеме.
x6=170-2x4-7x3-2x5+0.5x7
x2=40-0.5x7+4x3+2x5
x6 =0
x2=0
необходимо поменять местами переменные x3 и x2.
Новое решение будет следующим:
Свободные: x7, x2, x4, x5 =0
Базисные: x1, x6, x3
Видно, что получается отрицательная базисная переменная х3, поэтому очевидно, что x3 увеличивать нельзя. Поработаем с х5.
x1=180-2x3-x4-x5
x6=170-7x3-2x4-2x5+0.5x7
x2=40+4x3+2x5-0.5x7
x1 =0
x6=0
x2=0
Видим, что необходимо поменять местами х2 и х5
Новое решение будет следующим:
Свободные: x7, x3, x4, x2 =0
Базисные: x1, x6, x5
x6=170-7x3-2x4-2x5+0.5x7 x5= -40+x2-4x3+0.5x7
Видно, что получается отрицательная базисная переменная х5, поэтому очевидно, что x5 и х2 менять нельзя. Поменяем х5 с х6.
L=1860+10x3-2x4+3(85-3.5x3-x4-0.5x6+0.25x7)-3x7=2115-0.5x3-5x4-1.5x6-2.25x7
5. Симплекс-таблицы.
L = 9*x1+6*x2+4*x3+7*x4 L = 0 - (-9*x1-6*x2-4*x3-7*x4)
b |
||||||
L |
||||||