Главная Учебники - Разные Лекции (разные) - часть 32
|
Министерство образования и науки Российской Федерации Южно-Уральский государственный университет
Кафедра системы управления
по дисциплине: исследование операций
_ Челябинск 2004 г. Задание 1 3 Задание 2 6 Задание 3 9 Задание 4 11 Литература 17 Задание 1 Задача 9 Условие: Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость. Решение: Составим математическую модель задачи. Обозначим через 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 Меняем n1
и n5.
Таблица 1.2 Меняем n5
и n6.
Таблица 1.3 Меняем n4
и n6
. Таблица 1.4 Т.к. коэффициенты при всех 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). Решение: Составим систему: _ 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 Меняем x2
и x6.
Таблица 2.2 Меняем x5
и x8.
Таблица 2.3 Меняем x5
и x1.
Таблица 2.4 Получили оптимальное решение, т.к. все коэффициенты положительны. Следовательно 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 Решение: Составим таблицу транспортной задачи. Таблица 2 Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000. Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены. Таблица 3 Это будет опорный план. Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___ Таблица 4 Проверим методом потенциалов: Примем α1=0, тогда βj = cij – αi (для заполненных клеток). Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0 Очевидно, что Δij =0 для заполненных клеток. В результате получим следующую таблицу: Таблица 5 Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных. Тогда сумма всех перевозок: L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800 Ответ: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||