Исследование операций

_PAGE _

Министерство образования и науки Российской Федерации

Южно-Уральский государственный университет

Кафедра системы управления

Курсовая работа

по дисциплине: исследование операций

Вариант 9

_

Челябинск

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

Меняем n₁ и n_5.

Таблица 1.2

Меняем n₅ и n_6.

Таблица 1.3

Меняем n₄ и n₆.

Таблица 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= 0×1+5×2+x3 -x4+x5 >max

Приведем систему ограничений к виду основной задачи линейного программирования.

_ EMBED Equation.3 ___

Пусть х1, х2, х3, х4, х5 — свободные переменные, х6, х7, х8 — базисные.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

Q= 0-(-5×2-x3 +x4- x5)

_ EMBED Equation.3 ___

Составим симплекс-таблицу:

Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.

Таблица 2.1

Меняем x₂ и x_6.

Таблица 2.2

Меняем x₅ и x_8.

Таблица 2.3

Меняем x₅ и x_1.

Таблица 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=23 800

Ответ:

Задание 4

Задача 54

Условие:

Определить экстремум целевой функции вида

(= (11(12+(22(22+(12(1(2+(1(1+(2(2

при условиях:

(11(1+(12(2<=>(1

(21(1+(22(2<=>(2 .

Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.

Составить функцию Лагранжа.

Получить систему неравенств в соответствии с теоремой Куна-Таккера.

Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.

Дать ответ с учетом условий дополняющей нежесткости.

Решение:

1) Целевая функция: F=4×12−2×22 +1,5x1x2−7×1−2×2>min

Рассмотрим F'=-4×12+2×22 -1,5x1x2+7×1+2×2>max

Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ >_ EMBED Equation.3 ___

Определим относительный максимум функции F', для этого определим стационарную точку (х10, х20):

_ EMBED Equation.3 ___> _ EMBED Equation.3 ___> _ EMBED Equation.3 ___

2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:

F'11 (х10, х20) = -8 < 0

F'12 (х10, х20) = -1,5

F'21 (х10, х20) = -1,5

F'22 (х10, х20) = 4

_ EMBED Equation.3 ___

Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки

3) Составляем функцию Лагранжа:

L (x, u)=F'(x)+u1g1(x)+u2g2(x)=

=-4×12+2×22 -1,5x1x2+7×1+2×2+u1(_ EMBED Equation.3 ___)+u2(_ EMBED Equation.3 ___)

Получим уравнения седловой точки, применяя теорему Куна-Таккера:

_ EMBED Equation.3 ___ i=1;2

Объединим неравенства в систему А, а равенства в систему В:

Система А:

_ EMBED Equation.3 ___

Система В:

_ EMBED Equation.3 ___

Перепишем систему А:

_ EMBED Equation.3 ___

4)Введем новые переменные

V={v1,v2}?0; W={w1,w2}?0

в систему, А для того, чтобы неравенства превратить в равенства:

_ EMBED Equation.3 ___

Тогда

_ EMBED Equation.3 ___.

Значит, система В примет вид:

_ EMBED Equation.3 ___ - это условия дополняющей нежесткости.

5) Решим систему, А с помощью метода искусственных переменных.

Введем переменные Y={y1; y2} в 1 и 2 уравнения системы

_ EMBED Equation.3 ___

Затем создадим псевдоцелевую функцию Y=My1+My2>min

Y'=-Y= -My1-My2>max.

Пусть свободные переменные: х1, х2, v1, v2, u1, u2;

а базисные y1, y2, w1, w2.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

_ EMBED Equation.3 ___

_ EMBED Equation.3 ___

Решим с помощью симплекс-таблицы. Найдем опорное решение:

Т. о, u2=x2=y1=y2=v1=v2=0; x1=0,967; u1=0,367; w1=19,93; w2=12,87;

б) Условия дополняющей нежесткости выполняются (u2w2=0), значит решения исходной задачи квадратичного программирования существует.

ОТВЕТ: существует.

Курс лекций Плотникова Н. В.