_PAGE _
Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
Вариант 9
_
Челябинск
2004 г.Содержание
- Задание 1 3
- Задание 2 6
- Задание 3 9
- Задание 4 11
- Литература 17
- Задание 1
Задача 9
Условие:
Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. - вещества В и c ед. - вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.
|
|
Вещество
|
Количество единиц вещества, содержащегося в 1 кг сырья
|
|
|
1
|
2
|
3
|
|
|
А
|
d11
|
d12
|
d13
|
|
|
В
|
d21
|
d22
|
d23
|
|
|
С
|
d31
|
d32
|
d33
|
|
|
Цена 1 кг сырья
|
D1
|
D2
|
D3
|
|
|
|
|
№ вар.
|
d11
|
d12
|
d13
|
d21
|
d22
|
d23
|
d31
|
d32
|
d33
|
|
|
9
|
1
|
1
|
0
|
2
|
0
|
3
|
1
|
2
|
4
|
|
|
D1
|
D2
|
D3
|
а
|
b
|
c
|
|
|
5
|
6
|
7
|
26
|
30
|
24
|
|
|
Решение:
Составим математическую модель задачи.
Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.
Тогда, целевая функция будет
L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 >min
Система ограничений:
_ EMBED Equation.3 ___
Приведем систему ограничений к виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L, и новые переменные n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.
L=0-(5n1+ 6n2+7n3) >max
_ EMBED Equation.3 ___
Выберем n1, n2, n3 свободными переменными, а n4, n5, n6 - базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L=0-(5n1+ 6n2+7n3)
_ EMBED Equation.3 ___
Составим симплекс-таблицу.
Это решение не опорное, т.к. свободные члены не положительны.
Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент - n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).
Таблица 1.1
|
|
|
b
|
n1
|
n2
|
n3
|
|
|
|
L
|
0
|
|
5
|
|
6
|
|
7
|
|
|
|
|
|
-75
|
|
2,5
|
|
0
|
|
-8
|
|
|
|
n4
|
-26
|
|
-1
|
|
-1
|
|
0
|
|
26/1=26
|
|
|
|
15
|
|
-1
|
|
0
|
|
1,5
|
|
|
|
n5
|
-30
|
|
-2
|
|
0
|
|
-3
|
|
30/2=15min
|
|
|
|
15
|
|
-1
|
|
0
|
|
1,5
|
|
|
|
n6
|
-24
|
|
-1
|
|
-2
|
|
-4
|
|
24/1=24
|
|
|
|
15
|
|
-1
|
|
0
|
|
1,5
|
|
|
|
Меняем n1 и n5.
Таблица 1.2
|
|
|
b
|
n5
|
n2
|
n3
|
|
|
|
L
|
-75
|
|
2,5
|
|
6
|
|
-0,5
|
|
|
|
|
|
-45
|
|
5
|
|
-10
|
|
25
|
|
|
|
n4
|
-11
|
|
-0,5
|
|
-1
|
|
1,5
|
|
11/0,5=22
|
|
|
|
9
|
|
-1
|
|
2
|
|
-5
|
|
|
|
n1
|
15
|
|
-0,5
|
|
0
|
|
1,5
|
|
|
|
|
|
9
|
|
-1
|
|
2
|
|
-5
|
|
|
|
n6
|
-9
|
|
-0,5
|
|
-2
|
|
-2,5
|
|
9/0,5=18min
|
|
|
|
18
|
|
-2
|
|
4
|
|
5
|
|
|
|
Меняем n5 и n6.
Таблица 1.3
|
|
|
b
|
n6
|
n2
|
n3
|
|
|
L
|
-120
|
|
5
|
|
-4
|
|
25
|
|
|
|
|
-10
|
|
5
|
|
5
|
|
-18
|
|
|
n4
|
-2
|
|
-1
|
|
1
|
|
-4
|
|
|
|
|
2
|
|
-1
|
|
-1
|
|
2,5
|
|
|
n1
|
24
|
|
-1
|
|
2
|
|
-3
|
|
|
|
|
2
|
|
-1
|
|
-1
|
|
3,5
|
|
|
n5
|
18
|
|
-2
|
|
4
|
|
5
|
|
|
|
|
4
|
|
-2
|
|
-2
|
|
7
|
|
|
Меняем n4 и n6.
Таблица 1.4
|
|
|
b
|
n4
|
n2
|
n3
|
|
|
L
|
-130
|
|
5
|
|
1
|
|
7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n6
|
2
|
|
-1
|
|
-1
|
|
3,5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n1
|
26
|
|
-1
|
|
-1
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n5
|
22
|
|
-2
|
|
2
|
|
12
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.
Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс-таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,
где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,
(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).
|
|
№ вар.
|
С1
|
с2
|
с3
|
с4
|
с5
|
с6
|
b1
|
b2
|
b3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
29
|
0
|
5
|
1
|
-1
|
1
|
0
|
2
|
2
|
10
|
|
|
|
|
Знаки ограничений
|
a11
|
a12
|
a13
|
a14
|
|
|
1
|
2
|
3
|
|
|
|
|
|
|
|
|
-1
|
1
|
1
|
0
|
|
|
|
|
a15
|
a16
|
a21
|
a22
|
a23
|
a24
|
a25
|
a26
|
|
|
0
|
0
|
1
|
-2
|
0
|
1
|
0
|
0
|
|
|
|
|
a31
|
a32
|
a33
|
a34
|
a35
|
a36
|
Тип экстрем.
|
|
|
2
|
1
|
1
|
1
|
2
|
0
|
max
|
|
|
Решение:
Составим систему:
_ EMBED Equation.3 ___
Целевая функция Q= 0x1+5x2+x3 -x4+x5 >max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3 ___
Пусть х1, х2 , х3, х4, х5 - свободные переменные, х6, х7, х8 - базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3 ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
|
|
|
b
|
x1
|
x2
|
x3
|
x4
|
x5
|
|
|
|
Q
|
0
|
|
0
|
|
-5
|
|
-1
|
|
1
|
|
-1
|
|
|
|
|
|
10
|
|
-5
|
|
5
|
|
5
|
|
0
|
|
0
|
|
|
|
x6
|
2
|
|
-1
|
|
1
|
|
1
|
|
0
|
|
0
|
|
2/1=2min
|
|
|
|
2
|
|
-1
|
|
1
|
|
1
|
|
0
|
|
0
|
|
|
|
x7
|
2
|
|
1
|
|
-2
|
|
0
|
|
1
|
|
0
|
|
|
|
|
|
4
|
|
-2
|
|
2
|
|
2
|
|
0
|
|
0
|
|
|
|
x8
|
10
|
|
2
|
|
1
|
|
1
|
|
1
|
|
2
|
|
10/2=5
|
|
|
|
-2
|
|
1
|
|
-1
|
|
-2
|
|
0
|
|
0
|
|
|
|
Меняем x2 и x6.
Таблица 2.2
|
|
|
b
|
x1
|
x6
|
x3
|
x4
|
x5
|
|
|
Q
|
10
|
|
-5
|
|
5
|
|
4
|
|
1
|
|
-1
|
|
|
|
|
4
|
|
1,5
|
|
-1
|
|
-1
|
|
0,5
|
|
0,5
|
|
|
x2
|
2
|
|
-1
|
|
1
|
|
1
|
|
0
|
|
0
|
|
|
|
|
0
|
|
0
|
|
0
|
|
0
|
|
0
|
|
0
|
|
|
x7
|
6
|
|
-1
|
|
2
|
|
2
|
|
1
|
|
0
|
|
|
|
|
0
|
|
0
|
|
0
|
|
0
|
|
0
|
|
0
|
|
|
x8
|
8
|
|
3
|
|
-1
|
|
-1
|
|
1
|
|
2
|
|
|
|
|
4
|
|
6
|
|
-2
|
|
-2
|
|
2
|
|
0,5
|
|
|
Меняем x5 и x8.
Таблица 2.3
|
|
|
b
|
x1
|
x6
|
x3
|
x4
|
x8
|
|
|
Q
|
14
|
|
-3.5
|
|
4,5
|
|
3,5
|
|
1,5
|
|
0,5
|
|
|
|
|
21
|
|
5,25
|
|
-2,625
|
|
-2,625
|
|
2,625
|
|
2,625
|
|
|
x2
|
2
|
|
-1
|
|
1
|
|
1
|
|
0
|
|
0
|
|
|
|
|
8/3
|
|
2/3
|
|
-1/3
|
|
-1/3
|
|
1/3
|
|
1/3
|
|
|
x7
|
6
|
|
-1
|
|
2
|
|
2
|
|
1
|
|
0
|
|
|
|
|
8/3
|
|
2/3
|
|
-1/3
|
|
-1/3
|
|
1/3
|
|
1/3
|
|
|
x5
|
4
|
|
1,5
|
|
-0,5
|
|
-1
|
|
0,5
|
|
0,5
|
|
|
|
|
8/3
|
|
2/3
|
|
-1/3
|
|
-1/3
|
|
1/3
|
|
1/3
|
|
|
Меняем x5 и x1.
Таблица 2.4
|
|
b
|
x5
|
x6
|
x3
|
x4
|
x8
|
|
|
Q
|
35
|
5,25
|
1,875
|
0,875
|
4,125
|
3,125
|
|
|
x2
|
14/3
|
2/3
|
2/3
|
2/3
|
1/3
|
1/3
|
|
|
x7
|
26/3
|
2/3
|
5/3
|
5/3
|
4/3
|
1/3
|
|
|
x1
|
8/3
|
2/3
|
-1/3
|
-1/3
|
1/3
|
1/3
|
|
|
Получили оптимальное решение, т.к. все коэффициенты положительны.
Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица 1
|
|
№вар.
|
а1
|
а2
|
а3
|
1
|
2
|
3
|
4
|
5
|
с11
|
с12
|
с13
|
|
|
9
|
300
|
700
|
1000
|
200
|
100
|
400
|
600
|
200
|
23
|
40
|
10
|
|
|
|
|
с14
|
с15
|
с21
|
с22
|
с23
|
с24
|
с25
|
с31
|
с32
|
с33
|
с34
|
с35
|
|
|
12
|
21
|
25
|
21
|
20
|
50
|
18
|
15
|
30
|
32
|
25
|
50
|
|
|
Решение:
Составим таблицу транспортной задачи.
Таблица 2
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
a
|
|
|
A1
|
|
|
|
|
|
|
|
|
23
|
40
|
10
|
12
|
21
|
300
|
|
|
A2
|
|
|
|
|
|
|
|
|
25
|
21
|
20
|
50
|
18
|
700
|
|
|
A3
|
|
|
|
|
|
|
|
|
15
|
30
|
32
|
25
|
50
|
1000
|
|
|
b
|
200
|
100
|
200
|
600
|
200
|
|
|
|
Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
В6
|
a
|
|
|
A1
|
|
|
|
300
|
|
|
|
|
|
23
|
40
|
10
|
12
|
21
|
0
|
300
|
|
|
A2
|
|
100
|
200
|
|
200
|
200
|
|
|
|
25
|
21
|
20
|
50
|
18
|
0
|
700
|
|
|
A3
|
200
|
|
|
300
|
|
500
|
|
|
|
15
|
30
|
32
|
25
|
50
|
0
|
1000
|
|
|
b
|
200
|
100
|
200
|
600
|
200
|
700
|
2000
|
|
|
Это будет опорный план.
Количество заполненных ячеек - 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___
Таблица 4
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
В6
|
a
|
|
|
A1
|
|
|
|
300
|
|
|
300
|
|
|
23
|
40
|
10
|
12
|
21
|
0
|
|
|
Страницы: [1] | 2 |
|
