Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
_
Челябинск
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. Записать условия задачи в матричной форме.