Исследование операций
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Министерство общего и профессионального образования РФ
Южно-Уральский Государственный Университет
Кафедра Системы управления
КУРСОВАЯ РАБОТА
ПО ИССЛЕДОВАНИЮ ОПЕРАЦИЙ
Вариант 14
Группа ПС-317
Выполнил: Родионова Е.В.
Проверил: Плотникова Н.В.
Челябинск, 2004
Содержание
Задача 12
Задача 24
Задача 36
Задача 48
Задача 1
№14
Условие:
Нефтеперерабатывающий завод получает 4 полуфабриката: x1 тыс. л. алкилата, x2 тыс. л. крекинг-бензина, x3 тыс. л. бензина прямой перегонки и x4 тыс. л. изопентана. В результате смешивания этих четырех компонентов в разных пропорциях образуется три сорта авиационного бензина: бензин А (а1:а2:а3:а4), бензин В (b1:b2:b3:b4) и бензин С (с1:с2:с3:с4).
Стоимость 1 тыс. л. бензина каждого сорта равна y1 руб., y2 руб. и y3 руб.
Определить соотношение компонентов, при котором будет достигнута максимальная стоимость всей продукции.
№ вар.x1x2x3x4y1y2y3а1а2а3а4b1b21400250350100120100150235231
№ вар.b1b2c1c2c3c41212213
Решение:
Составим математическую модель задачи.
Обозначим через t1 количество бензина А;
через t2 количество бензина В;
через t3 количество бензина С.
Тогда, целевая функция будет
L=y1t1+ y2t2+ y3t3=120t1+100t2+150t3 >max
Система ограничений:
Приведем систему ограничений к виду основной задачи линейного программирования (введем новые переменные t4 , t5 ,t6 ,t7, которые входят в целевую функцию с нулевыми коэффициентами):
Выберем t1 , t2 ,t3 свободными переменными, а t4 , t5 ,t6 ,t7 базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L=0-(-120t1-100t2-150t3)
Составим симплекс-таблицу.
Это решение опорное, т.к. все свободные члены положительны.
Т. к. все коэффициенты в целевой функции отрицательные, то можно взять любой столбец разрешающим (пусть t1). Выберем в качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это t7)
bt1t2t3L0-120-100-15060006060180t4400232400/2=200-100-1-1-3t5250312250/3=83,3-150-1,5-1,5-4,5t6350521350/5=70-250-2,5-2,5-7,5t7100213100/2=50500,50,51,5
Далее меняем t2 и t1 .
bt7t2t3L600060-403040004080120t4300-12-1300/2=150-200-2-4-6t5100-1,5-0,5-2,5500,51-4,5t650-2,5-0,5-6,5500,51-7,5t1500,50,51,550/0,5=100100121,5
bt7t1t3L1000010080150t4100-3-4-7t5150-11-1t6100-21-5t2100123
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Таким образом, t1 = t3 =0; t2=100; L=10000.
Т.е. для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.
ОТВЕТ: для получения максимальной прибыли следует производить только бензин В (100 тыс. л.), при этом выручка составит 10000 руб.
Задача 2
№34
Условие:
С помощью симплекстаблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax B,
где = 1 2 . . . 6 , В = b1 b2 . . . b6 ,
= 1 2 . . . 6 , А= (=1,6; =1,3).
№ вар.с1с2с3с4с5с6b1b2b3Знаки ограниченийa11a12a13a14123343311004415===2031№ вар.a15a16a21a22a23a24a25a26a31a32a33a34a35a36Тип экстрем.
- 3400101230336360max Решение: Исходная система: Целевая функция Q= x1+3x2+x3+3x5. Пусть х3, х4 свободные переменные, х1, х2, х5 базисные. Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Составим симплекс-таблицу:
bx3x4Q99/2-1/22/3-5/61x123/21/22/0,5=4-2/35/6-1x27/34/30000x52/3-5/61/22/3 : 1/2=4/34/3-5/32
Это опорное решение, т.к. свободные члены положительны.
Т.к. коэффициент при х4 отрицательный, то это и будет разрешающий столбец. В качестве разрешающего элемента тот, для которого отношение к нему свободного члена будет минимально (это х5).
bx3x5Q29/311/31x14/32/3-1x27/34/30x44/3-5/32
Т.к. коэффициенты при переменных в целевой функции положительны, следовательно, это оптимальное решение.
Т. о. Q=29/3
x3=x5=0; x1=4/3; x2=7/3; x4=4/3.
ОТВЕТ: Q=29/3ж
x3=x5=0; x1=4/3; x2=7/3; x4=4/3.
Задача 3
№14
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
№вар.а1а2а312345с11с12с13149050301545455015456040с14с15с21с22с23с24с25с31с32с33с34с356095353055304050403530100
Решение:
Составим таблицу транспортной задачи и заполним ее методом северо-западного угла:
B1B2B3B4B5aA1456040609590154530A23530553040501535A350403530100301515b1545455015170
Это будет опорный план.
Количество заполненных ячеек r=m+n-1=6.
- Рассмотрим цикл (1,2)-(1,3)-(2,3)-(3,2):
с1,2+с2,3>c1.3+c3.2 (60+55>30+40)
Количество единиц товара, перемещаемых по циклу: min (с1,2 ; с2,3)=15
- Рассмотрим цикл (2,4)-(2,5)-(3,5)-(3,4):
c2,4+с3,5>c2.5+c3.4 (30+40>30+100)
Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15
В результате получится следующий план:
B1B2B3B4B5aA1456040609590153045A2353055304050152015A3504035301003030b1545455015170
Больше циклов с отрицательной ценой нет, значит, это оптимальное решение.
Проверим методом потенциалов:
Примем ?1=0, тогда ?j = cij ?i (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы ?ij = cij (?i+ ?j) ? 0
Очевидно, что ?ij =0 для заполненных клеток.
В результате получим следующую таблицу:
?1=45?2=60?3=40?4=60?5=70?1=04560406095901530450+?2= -30353055304050+15+2015?3= -305040353010030+++30+1545455015170
?1,4=0 показывает, что существует