Исследование операций и теория систем
Исследование операций и теория систем
Исследование операций и теория систем
содержание
Задача 1. 4
Задача 2. 6
Задача 3. 8
Задача 4. 11
Список используемой литературы.. 15
Задача 1
x – количество тысяч деталей, выпускаемых цехами a, b, c i-го склада, где i – номер склада.
xa1 — количество тысяч деталей, выпускаемых цехом a c 1-го склада
xa2 — количество тысяч деталей, выпускаемых цехом a c 2-го склада
xa3 — количество тысяч деталей, выпускаемых цехом a c 3-го склада
xa4 — количество тысяч деталей, выпускаемых цехом a c 4-го склада
xb1 — количество тысяч деталей, выпускаемых цехом b c 1-го склада
xb2 — количество тысяч деталей, выпускаемых цехом b c 2-го склада
xb3 — количество тысяч деталей, выпускаемых цехом b c 3-го склада
xb4 — количество тысяч деталей, выпускаемых цехом b c 4-го склада
xc1 — количество тысяч деталей, выпускаемых цехом c c 1-го склада
xc2 — количество тысяч деталей, выпускаемых цехом c c 2-го склада
xc3 — количество тысяч деталей, выпускаемых цехом c c 3-го склада
xc4 — количество тысяч деталей, выпускаемых цехом c c 4-го склада
Так как производительность цехов в день известна, то можно записать следующее
Зная пропускную способность складов за день, запишем
Запишем целевую функцию, при которой стоимость перевозок будет минимальна
Имеем классическую транспортную задачу с числом базисных переменных, равным n+m–1 , где m–число пунктов отправления, а n – пунктов назначения. В решаемой задаче число базисных переменных равно 4+3-1=6
Число свободных переменных соответственно 12-6=6
Примем переменные x1a, x1b, x2a, x1с, x4с, x3b в качестве базисных, а переменные x2c, x3c, x2b, x3а, x4а, x4b в качестве свободных.
Далее в соответствии с алгоритмом Симплекс метода необходимо выразить базисные переменные через свободные
В задании требуется найти минимум функции L. Так как коэффициент при переменной x3a меньше нуля, значит найденное решение не является оптимальным.
Составим Симплекс таблицу
Ответ при перевозке x3a=4, х1b=4, х1с=16, х2а=35, х3b=26, х4с=8, х1а=х4а=x2b=x4b=x2c=x3c=0 тыс/изд стоимость будет минимальна и составлять 86 тыс/руб.
Задача 2
7 9
-9 3
5 -3
2 1
-1
2 —
3 1
3
-1 —
6 -3
3 -1
2 1
Так как все , то это опорное решение.
Найдем оптимальное решение.
16
3
2
3
1
—
3
-1
3
Данное решение является оптимальным, так как все коэффициенты при переменных в целевой функции положительные.
Ответ , ,
Задача 3
Заданная задача – транспортная задача с неправильным балансом (избыток заявок).
Необходимо ввести фиктивный пункт отправления Аф с запасом
Для нахождения опорного плана используем метод «Северо-западного угла».
В1
В2
В3
А1
12 600
42
25
600
А2
21 100
18 100
35
200
А3
25
15 200
23
200
А4
21
30 100
40
100
А5
20
32 400
50
400
АФ
0
0 200
0 300
500
700
1000
300
2000
Решение является опорным.
В1
В2
В3
А1
12 600
42
25
600
А2
21
18 200
35
200
А3
25
15 200
23
200
А4
21 100
30
40
100+
А5
20
32 400-
50
400-
АФ
0
0 200
0 300
500
700
1000
300
2000
Решение является опорным, но вырожденным. Для того чтобы свести вырожденный случай к обычному решению, изменим запасы на малую положительную величину так, чтобы общий баланс не нарушился.
В1
В2
В3
А1
12 600
42
25
600
А2
21
18 200
35
200
А3
25
15 200
23
200
А4
21
30 100+
40
100+
А5
20 100
32 300-
50
400-
АФ
0
0 200
0 300
500
700
1000
300
2000
Получили оптимальное решение.
Проверим правильность решения задачи методом потенциалов.
Пусть , тогда
Так как среди найденных чисел нет положительных, то найденный план является оптимальным.
Ответ 28400
Задача 4
Найти
При ограничениях
1) Определение стационарной точки
2) Проверка стационарной точки на относительный максимум или минимум
, , следовательно, стационарная точка является точкой относительного максимума.
3) Составление функции Лагранжа
Применяем к функции Лагранжа теорему Куна-Таккера.
I
II
4) Нахождение решение системы I. Оставим все свободные переменные в правой части.
(1)
(из II)
Система уравнений II определяется условиями дополняющей нежесткости
5) Введем искусственные переменные , в первые два уравнения системы (1) со знаками, совпадающими со знаками соответствующих свободных членов
Проверяем условие выполнения дополняющей не жесткости
Все четыре условия выполняются
Ответ Решения и являются оптимальным решением квадратичного программирования.
Тогда
Список используемой литературы
1. Волков И. К., Загоруйко Е. А. Исследование операций. – Москва Издательство МГТУ имени Баумана Н. Э., 2000г. – 436с.
2. Кремер Н. Ш. Исследование операций в экономике. – Москва Издательское объединение «ЮНИТИ», 1997г. – 407с.
3. Курс лекций Плотникова Н.В.