Курсовой проект - Решение задач симплекс-методом
Подождите немного. Документ загружается.
Факультет дистанционного обучения
Томский государственный университет
систем управления и радиоэлектроники (ТУСУР)
Кафедра автоматизации обработки информации
Курсовой проект
по дисциплине «Системный анализ и исследование операций»
по учебно-методическому пособию Л.П.Турунтаева
Вариант №1
2010г
1
Содержание
1. Постановка задачи.................................................................................................................................3
2. Построение математической модели задачи.....................................................................................3
3. Математическая задача в числовой форме........................................................................................4
4. Решение симплекс-методом................................................................................................................5
5. Результаты решения..............................................................................................................................7
2
1. Постановка задачи.
Задача: «На заводе ежемесячно скапливается А тонн отходов металла, из которого
можно штамповать мелкие детали 6 типов. Месячная потребность завода в деталях i-го типа
равна
i
b
тыс. шт. Недостающее количество деталей i-го типа закупается на других предприятиях
по цене
i
c
рублей за тысячу штук. Расход металла на тыс. деталей i-го типа составляет
i
a
кг.
Для изготовления деталей используются 3 пресса, на каждом из которых за смену можно
изготовить
i
d
тыс. деталей i-го типа. В месяц каждый пресс работает не более 52 смен. Найти
план производства деталей из отходов завода, обеспечивающий минимум расходов на
приобретение таких деталей у других предприятий.
Вариант 1.
Таблица исходных данных.
А а1 а2 а3 а4 а5 а6 b1 b2 b3 b4 b5 b6
12 30 45 22 11 74 51 62 99 17 29 34 99
c1 c2 c3 c4 c5 c6 d1 d2 d3 d4 d5 d6
13 15 9 7 18 22 1,4 1,3 2,9 2,1 0,8 1,5
Общее количество металла A = 12 000 кг.
i
c
– расход денежных средств на покупку детали i-того типа;
i
a
– расход металла на производство детали i-того типа;
i
b
– необходимое количество деталей i-того типа;
i
d
– количество деталей i-того типа, производящихся на 1 станке за 1 смену.
2. Построение математической модели задачи.
За переменные примем количество смен, потраченных на производство деталей одного
конкретного вида.
Пусть
x
i
– суммарное количество потраченных на производство деталей i-того типа на 3-х
станках.
Запишем целевую функцию.
min
i
ii
yc
,
где
i
c
- затраты на покупку деталей i-того типа, а
i
y
- количество деталей i-того типа,
которых не хватило для выполнения плана. Выразим
i
y
через
i
x
:
iiii
xdby
Тогда целевая функция принимает вид
min)(
i
iiii
xdbc
3
Зададим ограничения.
Ограничение на потребность завода в деталях i-того типа, учитывая то, что за смену может
быть изготовлено
i
d
деталей:
iii
bxd
Ограничение на суммарный объем материала. С учетом затрат на производство детали i-
того типа:
Axda
iii
,
где
ii
xd
- количество деталей.
Ограничение на количество смен:
156
i
x
Итак, необходимо найти минимум функции:
min)(
i
iiii
xdbc
при ограничениях:
iii
bxd
Axda
iii
156
i
x
0
i
x
3. Математическая задача в числовой форме.
По исходным данным составляем математическую задачу в числовой форме. Находим
числовое выражение целевой функции.
)5.199(22)8.034(18
)1.229(7)9.217(9)3.199(15)4.162(13)(
65
4321
xx
xxxxxdBc
i
iiii
min)334.1 47.1 41.2 65.192.18(5437)(
654321
xxxxxxxdBc
i
iiii
Максимальное значение целевой функции равно 5437, если покупать все детали.
Очевидно, такое решение не является оптимальным.
Ограничения:
995.1
348.0
291.2
179.2
993.1
625.1
6
5
4
3
2
1
x
x
x
x
x
x
120005.762.591.238.635.5842
654321
xxxxxx
156
654321
xxxxxx
0;0;0;0;0;0
654321
xxxxxx
4
4. Решение симплекс-методом.
Будем решать задачу симплекс-методом, поскольку он прост и нагляден.
Для решения симплекс-методом необходимо преобразовать неравенства к равенствам.
Для этого вводим дополнительные переменные.
7
x
- количество рабочих смен, которых не хватило для выполнения плана производства
деталей 1-го типа. При
0
7
x
план выполнен, т.е. дополнительно закупать ничего не надо.
8
x
- количество рабочих смен, которого не хватило для выполнения плана производства
деталей 2-го типа. При
0
8
x
план выполнен, т.е. дополнительно закупать ничего не надо.
Аналогично вводим переменные
1211109
,,, xxxx
13
x
- количество рабочих смен, которого не хватило для выработки всех ресурсов. При
0
13
x
все ресурсы выработаны.
995.1
348.0
291.2
179.2
993.1
625.1
126
115
104
93
82
71
xx
xx
xx
xx
xx
xx
120005.762.591.238.635.5842
13654321
xxxxxxx
156
14654321
xxxxxxx
Составляем начальную таблицу, выбирая в качестве опорного такой план, при котором на
производство деталей каждого типа будет затрачено по одной смене. Такой план, очевидно, не
является оптимальным, и будет улучшаться при следующих итерациях.
СТ-1.
1
x
2
x
3
x
4
x
5
x
6
x
i
b
7
x
1.5 0 0 0 0 0 62
8
x
0 1.3 0 0 0 0 99
9
x
0 0 2.9 0 0 0 17
10
x
0 0 0 2.1 0 0 29
11
x
0 0 0 0 0.8 0 34
12
x
0 0 0 0 0 1.5 99
13
x
42 58.5 63.8 23.1 59.2 76.5 12000
14
x
1 1 1 1 1 1 156
f
18.2 19.5 26.1 14.7 14.4 33 5437
Значение целевой функции показано красным цветом. В нижней строке присутствуют
положительные числа, поэтому продолжаем уменьшать значение целевой функции.
СТ-2.
1
x
2
x
3
x
4
x
5
x
12
x
i
b
7
x
1.5 0 0 0 0 0 62
8
x
0 1.3 0 0 0 0 99
9
x
0 0 2.9 0 0 0 17
5
10
x
0 0 0 2.1 0 0 29
11
x
0 0 0 0 0.8 0 34
6
x
0 0 0 0 0 0.67 66
13
x
42 58.5 63.8 23.1 59.2 -51 6951
14
x
1 1 1 1 1 -0.67 90
f
18.2 19.5 26.1 14.7 14.4 -22 3259
В нижней строке присутствуют положительные числа, поэтому продолжаем уменьшать
значение целевой функции.
СТ-3.
1
x
2
x
9
x
4
x
5
x
12
x
i
b
7
x
1.5 0 0 0 0 0 62
8
x
0 1.3 0 0 0 0 99
3
x
0 0 0.34 0 0 0 5.86
10
x
0 0 0 2.1 0 0 29
11
x
0 0 0 0 0.8 0 34
6
x
0 0 0 0 0 0.67 66
13
x
42 58.5 -22 23.1 59.2 -51 6577
14
x
1 1 -0.34 1 1 -0.67 84.14
f
18.2 19.5 -9 14.7 14.4 -22 3106
В нижней строке присутствуют положительные числа, поэтому продолжаем уменьшать
значение целевой функции.
СТ-4.
1
x
8
x
9
x
4
x
5
x
12
x
i
b
7
x
1.5 0 0 0 0 0 62
2
x
0 0.77 0 0 0 0 76.15
3
x
0 0 0.34 0 0 0 5.86
10
x
0 0 0 2.1 0 0 29
11
x
0 0 0 0 0.8 0 34
6
x
0 0 0 0 0 0.67 66
13
x
42 -45 -22 23.1 59.2 -51 2122
14
x
1 -0.77 -0.34 1 1 -0.67 7.98
f
18.2 -15 -9 14.7 14.4 -22 1621
В нижней строке присутствуют положительные числа, поэтому продолжаем уменьшать
значение целевой функции.
СТ-5.
14
x
8
x
9
x
4
x
5
x
12
x
i
b
7
x
0.63 1.15 0.52 -1.5 -1.5 1 50.02
2
x
0 0.77 0 0 0 0 76.15
3
x
0 0 0.34 0 0 0 5.86
10
x
0 0 0 2.1 0 0 29
11
x
0 0 0 0 0.8 0 34
6
x
0 0 0 0 0 0.67 66
6
13
x
-17.2 -12.69 -7.54 -18.9 17.2 -23 1786.67
1
x
1 -0.77 -0.34 1 1 -0.67 7.98
f
-2.5 -1 -2.72 -3.5 -3.8 -9.87 1475.69
В нижней строке нет положительных чисел, значит оптимальное решение найдено.
Значение целевой функции равно 1475.69
5. Результаты решения
Получено оптимальное решение, при котором полностью должны быть сделаны детали 3-
го и 6-го типов. Детали второго типа делаются частично.
Значение целевой функции
69.1475L
98.7
1
x
- количество рабочих смен на производство 1 типа деталей.
15.76
2
x
- количество рабочих смен на производство 2 типа деталей.
86.5
3
x
- количество рабочих смен на производство 3 типа деталей.
0
4
x
- количество рабочих смен на производство 4 типа деталей.
0
5
x
- количество рабочих смен на производство 5 типа деталей.
66
6
x
- количество рабочих смен на производство 6 типа деталей.
Ответ:
69.1475L
руб.
7