Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-12-21 | 116 |
5.00
из
|
Заказать работу |
|
|
Кафедра прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине «Прикладная математика»
Выполнил(а) ………………..
Институт
Отделение
Курс II
Группа ……………….
Руководитель ……………….
Дата сдачи на проверку..............................
Дата защиты..............................
Оценка..............................
Подпись руководителя..............................
Москва - 2002
Оглавление
Линейная производственная задача.............................................................................................. 3
Двойственная задача....................................................................................................................... 7
Транспортная задача..................................................................................................................... 12
Метод динамического программирования................................................................................. 15
Динамическая задача управления производством и запасами............................................... 18
Матричная модель сотрудничества и конкуренции............................................................... 25
Задача о максимальном потоке в сети...................................................................................... 28
Список литературы....................................................................................................................... 32
Линейная производственная задача
Постановка задачи
Сформулировать линейную производственную задачу и составить ее математическую модель.
Преобразовать данную задачу к виду основной задачи линейного программирования, решить ее методом направленного перебора базисных допустимых решений, обосновывая каждый шаг процесса, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать “узкие места” производства.
В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения
|
H = Q-1 * B.
Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить графически.
Исходные данные
Предприятие выпускает 4 вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:
А = | ||||
Известен вектор B объемов ресурсов, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:
В = | |
Также известен вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции j-го вида:
С = |
Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль при имеющихся ограниченных ресурсах.
Решение
Математическая модель задачи: найти производственную программу
(х1, х2, х3, х4),
максимизирующую прибыль
Z = 34 * х1 + 20 * х2 + 8 * х3 + 23 * х4
при ограничениях по ресурсам
2 * х1 | + | 2 * х3 | + | 3 * х4 | <= | ||||
х1 | + | 5 * х2 | + | 4 * x3 | + | 2 * х4 | <= | (1) | |
3 * х1 | + | 4 * х2 | + | х4 | <= |
где по смыслу задачи
x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0
Введя дополнительные неотрицательные неизвестные х5, х6, х7, заменяем неравенства (1) уравнениями вида:
2 * х1 | + | 2 * х3 | + | 3 * х4 | + | х5 | = | |||
х1 | + | 5 * х2 | + | 4 * x3 | + | 2 * х4 | + | х6 | = | |
3 * х1 | + | 4 * х2 | + | х4 | + | х7 | = |
Решаем полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений) (см. Таблицу 1).
|
Таблица 1
C | Базис | Hi | х1 | х2 | х3 | х4 | х5 | х6 | х7 |
х5 | |||||||||
х6 | |||||||||
х7 | |||||||||
z – z0 | -34 | -20 | -8 | -23 | |||||
х5 | 182/3 | -8/3 | 7/3 | -2/3 | |||||
х6 | 178/3 | 11/3 | 5/3 | -1/3 | |||||
х1 | 122/3 | 4/3 | 1/3 | 1/3 | |||||
z – z0 | 4148/3 | 76/3 | -8 | -35/3 | 34/3 | ||||
х4 | -8/7 | 6/7 | 3/7 | -2/7 | |||||
х6 | 18/7 | -5/7 | 1/7 | ||||||
х1 | -2/7 | -1/7 | 3/7 | ||||||
z – z0 |
Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид
х1 = 32, х2 = 0, х3 = 0, х4 = 26,
а максимальная прибыль равна
Zmax = 1686
При этом 1-й и 3-й ресурсы будут исчерпаны полностью (х5=0, х7=0), а 2-й ресурс будет иметь остаток х6 = 8 единиц.
Обращенный базис, отвечающий оптимальной производственной программе, содержится в последней симплексной таблице:
3/7 | -2/7 | ||
Q –1 = | -5/7 | 1/7 | |
-1/7 | 3/7 |
Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:
3/7 | -2/7 | 426/7 – 244/7 | |||||||
Q-1 * В = | -5/7 | 1/7 | * | = | -710/7 + 100 + 122/7 | = | |||
-1/7 | 3/7 | -142/7 + 366/7 |
Следовательно, полученное решение верно.
Так как х2 = 0, х3= 0, можно составить математическую модель задачи с двумя переменными (х1 и х4):
Z = | 34 * х1 | + | 23 * х4 | -> | max |
2 * х1 | + | 3 * х4 | <= | ||
х1 | 2 * x4 | <= | |||
3 * х1 | + | х4 | <= |
Графическое решение такой модели изображено на Рисунке 1.
Рисунок 1
Решая систему двух линейных уравнений, получаем оптимальный результат:
2 * х1 | + | 3 * х4 | = | |
3 * х1 | + | х4 | = |
х1 | = | |
х3 | = | |
Zmax | = |
Полученный графическим методом результат совпадает с тем, который был получен ранее при использовании симплекс-метода.
Двойственная задача
Постановка задачи
Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости). Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.
|
Применить найденные двойственные оценки ресурсов к решению следующей задачи.
Сформулировать задачу о расшивке “узких мест” производства и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о “расшивке узких мест производства” при условии, что дополнительно можно получить от поставщиков не более 1/3 первоначального объема ресурса каждого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.
Исходные данные – см. Задачу 1.
Решение
При решении двойственной задачи требуется найти оценку единицы каждого вида ресурса. Это - задача линейного программирования, постановка которой формулируется следующим образом.
Найти вектор двойственных оценок
(у1, у2, у3),
минимизирующий общую всех ресурсов
f = 142 * y1 + 100 * y2 + 122 * y3
при условии, что по каждому виду продукции суммарная оценка ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции
2 * у1 | + | у2 | + | 3 * y3 | >= | |
5 * у2 | + | 4 * у3 | >= | |||
2 * у1 | + | 4 * y2 | >= | |||
3 * у1 | + | 2 * y2 | + | у3 | >= |
причем оценки ресурсов не могут быть отрицательными
у1 >= 0, у2 >= 0, у3 >= 0.
Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х1,х2,х3) и у(у1,у2,у3) пары двойственных задач необходимо и достаточно выполнение условий
х1 * ( | 2 * у1 | + | у2 | + | 3 * y3 | - | ) = 0 | |
х2 * ( | 5 * у2 | + | 4 * у3 | - | ) = 0 | |||
х3 * ( | 2 * у1 | + | 4 * y2 | - | ) = 0 | |||
х4 * ( | 3 * у1 | + | 2 * y2 | + | у3 | - | ) = 0 |
у1 * ( | 2 * х1 | + | 2 * х3 | + | 3 * х4 | - | ) = 0 | |||
у2 * ( | х1 | + | 5 * х2 | + | 4 * x3 | + | 2 * х4 | - | ) = 0 | |
у3 * ( | 3 * х1 | + | 4 * х2 | + | х4 | - | ) = 0 |
|
Ранее (см. Задачу 1) было найдено, что в решении исходной задачи х1>0 и х4>0. Поэтому
2 * у1 | + | у2 | + | 3 * y3 | - | = 0 | |
3 * у1 | + | 2 * y2 | + | у3 | - | = 0 |
Если же учесть, что 2-й ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю:
y2 = 0
то приходим к системе уравнений
2 * у1 | + | 3 * y3 | - | = 0 | |
3 * у1 | + | у3 | - | = 0 |
откуда следует
у1 = 5,
у3 = 8.
Таким образом, получили двойственные оценки ресурсов
у1 = 5, у2 = 0, у3 = 8,
причем общая оценка всех ресурсов равна
fmin = 1686
Заметим, что это решение содержалось в последней строке симплексной таблицы исходной задачи.
Экономический смысл
Двойственная оценка 1-го ресурса у1 = 5 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 5 единиц, двойственная оценка 3-го ресурса у3 = 8 - что добавление одной единицы 3-го ресурса обеспечит прирост прибыли в 8 единиц. Двойственная оценка 2-й технологии D2 = 12 показывает, что если произвести одну единицу продукции 2-го вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц, оценка 3-й технологии D3 = 18 - что производство одной единицы продукции 3-го вида снизит прибыль на 18 единиц.
При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть T(t1, t2, t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие
H + Q-1 * T >= 0
Задача состоит в том, чтобы найти вектор
T (t1, t2, t3)
максимизирующий суммарный прирост прибыли
w = 5 * t1 + 8 * t3 (1)
при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)
3/7 | -2/7 | t1 | |||||||
+ | -5/7 | 1/7 | * | >= | (2) | ||||
-1/7 | 3/7 | t3 |
предполагая, что дополнительно можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида
t1 | |||||
=< | 1/3 | * | (3) | ||
t3 |
причем по смыслу задачи
t1 >= 0, t3 >= 0 (4)
Переписав неравенства (2) и (3) в виде
-3 * t1 | + | 2 * t3 | =< | ||
5 * t1 | - | t3 | =< | ||
t1 | - | 3 * t3 | =< | (5) | |
t1 | =< | 47.33 | |||
t3 | =< | 40.67 |
приходим к задаче линейного программирования: максимизировать (1) при условиях (4), (5).
Эту задачу решаем графическим методом (см. Рисунок 2).
Рисунок 2
|
Решаем систему уравнений:
5 * t1 | - | t3 | = | ||
t3 | = | 40.67 |
Программа “расшивки” имеет вид
t1 = 30.53, t2 = 0, t3 = 40.67
и прирост прибыли составит
w = 478.01
Сводка результатов приведена в Таблице 2.
Таблица 2
cj | bi | x4+i | yi | ti | ||||
30.53 | ||||||||
aij | ||||||||
40.67 | ||||||||
xj | 478.01 | |||||||
D j |
Транспортная задача
Постановка задачи
Составить математическую модель транспортной задачи. Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.
Исходные данные
Стоимости перевозок:
Вектор объемов производства:
А = (80, 60, 30).
Вектор объемов потребления:
В = (34, 40, 38, 53).
Решение
Так как размеры объемов производства превышают размеры объемов потребления на 5 единиц, вводим фиктивного b5=5 потребителя и определяем первоначальный опорный план методом северо-западного угла:
b1=34 | b2=40 | b3=38 | b4=53 | b5=5 | |
a1=80 | |||||
a2=60 | |||||
a3=30 |
Находим оптимальное решение транспортной задачи методом потенциалов.
b1=34 | b2=40 | b3=38 | b4=53 | b5=5 | ||
a1=80 | - 7 | + 2 | p1 = 0 | |||
a2=60 | + 5 * | - 4 | p2 = 2 | |||
a3=30 | p3 = 1 | |||||
q1 = 2 | q2 = 7 | q3 = 2 | q4 = 0 | q5 = -1 | ||
D21 = 3 | D22 = 4 | D33 = -3 | D14 = -3 | D15 = -1 | ||
D31 = 0 | D32 = 4 | D25 = 1 | ||||
Zmin = |
b1=34 | b2=40 | b3=38 | b4=53 | b5=5 | ||
a1=80 | - 7 | + 0 * | p1 = 0 | |||
a2=60 | + 5 | - 2 | p2 = -2 | |||
a3=30 | + 1 | - 0 | p3 = -3 | |||
q1 = 2 | q2 = 7 | q3 = 2 | q4 = 4 | q5 = 3 | ||
D21 = -1 | D32 = 0 | D13 = -4 | D14 = 1 | D15 = 3 | ||
D31 = -4 | D33 = -7 | D25 = 0 | ||||
Zmin = |
b1=34 | b2=40 | b3=38 | b4=53 | b5=5 | ||
a1=80 | - 7 | + 3 * | p1 = 0 | |||
a2=60 | + 5 | - 2 | p2 = -2 | |||
a3=30 | p3 = -3 | |||||
q1 = 2 | q2 = 7 | q3 = 2 | q4 = 4 | q5 = 0 | ||
D21 = 0 | D32 = 0 | D23 = -4 | D14 = 1 | D25 = -2 | ||
D31 = -4 | D33 = -7 | D35 = -3 | ||||
Zmin = |
b1=34 | b2=40 | b3=38 | b4=53 | b5=5 | ||
a1=80 | p1 = 0 | |||||
a2=60 | p2 = -1 | |||||
a3=30 | p3 = -2 | |||||
q1 = 2 | q2 = 6 | q3 = 2 | q4 = 3 | q5 = 0 | ||
D21 = 0 | D12 = -1 | D23 = -3 | D25 = -1 | |||
D31 = -3 | D32 = 0 | D33 = -6 | D35 = -2 | |||
Zmin = |
Все потенциалы свободных клеток Dij неположительные, следовательно, решение, представленное в последней таблице, является оптимальным, причем минимальная стоимость всех перевозок составляет 423 единицы.
Постановка задачи
Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб. (выделяемые суммы кратны 100 тыс. руб.).
Исходные данные
Значения функции fj(хj) приведены в Таблице 1 (считаем их заданными, их определение - довольно трудоемкая экономическая задача):
Таблица 1
xj | ||||||||
f1(xj) | ||||||||
f2(xj) | ||||||||
f3(xj) | ||||||||
f4(xj) |
Решение
Воспользуемся методом динамического программирования для решения этой задачи.
Введем параметр состояния x - количество рублей, выделяемых нескольким предприятиям, и определим функцию состояния Fk(x) - максимальная прибыль на первых k предприятиях, если они вместе получат хk рублей.
Табулируя последовательно функции Fk(x), получим решение, ход которого приведен в Таблицах 2-6.
Таблица 2
x-х2 | |||||||||
х2 | F(x-x2) f2(x2) | ||||||||
22* | 42* | ||||||||
57* | 70* | ||||||||
82* | |||||||||
92* | 101* | ||||||||
101* | |||||||||
Таблица 3
x | ||||||||
F2(x) | ||||||||
x2(x) | 400/500 |
Таблица 4
x-х3 | |||||||||
х3 | F(x-x3) f3(x3) | ||||||||
0* | 22* | 42* | 57* | ||||||
71* | 86* | 99* | |||||||
99* | 112* | ||||||||
Таблица 5
x | ||||||||
F2(x) | ||||||||
x2(x) | 200/300 |
Таблица 6
x-х4 | |||||||||
х4 | F(x-x4) f4(x4) | ||||||||
115* | |||||||||
Zmax = 115 тыс. руб.,
причем четвертому предприятию должно быть выделено
х4* = х4(700) = 100 тыс. руб.
На долю остальных трех предприятий остается 600 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено
1) х3* = х3(700 - х4*) = х3(600) = 200 тыс. руб.
2) х3* = х3(700 - х4*) = х3(600) = 300 тыс. руб.
Продолжая обратный процесс, находим
1) х2* = х2(700 - х4* - х3*) = х2(400) = 200 тыс. руб.
2) х2* = х2(700 - х4* - х3*) = х2(300) = 200 тыс. руб.
На долю первого предприятия останется
1) х1* = 700 - х4* - х3* - х2* = 200 тыс. руб.
2) х1* = 700 - х4* - х3* - х2* = 100 тыс. руб.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
1) х1* = 200; х2* = 200; х3* = 200; х4* = 100
2) х1* = 100; х2* = 200; х3* = 300; х4* = 100
Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 115 тыс. руб.
В качестве проверки правильности решения задачи можно использовать равенство
f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax
1) f1(200) + f2(200) + f3(200) + f4(100) = 33 + 37 + 29 + 16 = 115 = Zmax
2) f1(100) + f2(200) + f3(300) + f4(100) = 20 + 37 + 42 + 16 = 115 = Zmax
Следовательно, полученные решения верны.
Постановка задачи
Рассмотреть динамическую задачу управления производством и запасами.
Исходные данные
Спрос (заявки) потребителей на продукцию составляют: на первый этап d1 = 5 единиц, на второй – d2 = 1, на третий - d3 = 2 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y1=4. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1 = 2, h2 = 1, h3 = 1. Затраты на производство xj единиц продукции на j-м этапе определяются функцией
jj(xj) = 2 * xj2 + 6 (1)
т.е. а = 2; b = 0; с = 6. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.
Решение
Воспользовавшись рекурентными соотношениями, последовательно вычисляем F1 (x = y2), F2 (x = y3),..., Fk (x = yk+1),... и соответственно находим 1 (x= y2), 2 (x = y3),..., ` k (x = yk+1),...
Положим k = 1. Тогда имеем
F1(x= y2) = min{2 * xj2 + 6 + 2 * y2} (2)
Учтем, что параметр состояния x = у2 может принимать целые значения на отрезке
0 у2 d2 + d3
0 y2 3
т.е.
у2 = 0, 1, 2, 3
При этом каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием
0 х1 d1 + у2
0 х1 5 + у2
Из балансового уравнения
х1 + у1 - d1 = у2
непосредственно следует, что объем производства связан со значением параметра состояния x= у2 соотношением
x1 = y2 + d1 - y1 = y2 + 5 - 4 = y2 + 1 (3)
Каждому значению у2 отвечает единственное значение х1 и потому
F1(x = y2) = W1 (x1, y2)
Придавая у2 различные целые значения от 0 до 3 и учитывая (3), находим
y2 = 0, x1 = 1, W1 (1;0) = 2 * 12 + 6 + 2 * 0 = 8
y2 = 1, x1 = 2, W1 (2;1) = 2 * 22 + 6 + 2 * 1 = 16
y2 = 2, x1 = 3, W1 (3;2) = 2 * 32 + 6 + 2 * 2 = 28
y2 = 3, x1 = 4, W1 (4;3) = 2 * 42 + 6 + 2 * 3 = 44
Значения функции состояния F1(x) представлены в Таблице 1.
Таблица 1
x = y2 | ||||
F1 (x = y2) | ||||
x1(x=y2) |
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2(x = y3):
F2(x = y3) = min W1 (x1, y2) = min{a * x22 + b * x2 + c + h2 * y3 + F1(y2)} =
= min {2 * x22 + 6 + y3 + F1(y2)} (4)
Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах
0 £ x2 £ d2 + y3 или 0 £ x2 £ 1 + y3 (5)
где верхняя граница зависит от параметра состояния x = у3, который принимает значения на отрезке
0 £ y3 £ d3, т.е. 0 £ y3 £ 2 (6)
а аргумент у2 в последнем слагаемом справа в соотношении (4) связан с х2 и у3 балансовым уравнением
x2 + y2 - d2 = y3
откуда следует
y2 = y3 + d2 - x2 = y3 + 1 - x2 (7)
Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять W2 (x2, x), а затем определять F2(x) и 2(x).
Положим x = у3 = 0. Тогда, согласно (5),
0 £ x2 £ 1,
т.е. переменная х2 может принимать значения 0, 1, которым отвечает значение у2, вычисляемое по формуле (7):
у2 = 1 - х2
Последовательно находим:
x2 = 0, y2 = 1 - 0 = 1, W2 (0,0) = 2 * 02 + 6 + 0 + F1(1) = 6 + 16 = 22
x2 = 1, y2 = 1 - 1 = 0, W2 (1,0) = 2 * 12 + 6 + 0 + F1(0) = 8 + 8 = 16*
Наименьшее из полученных значений W2 есть F2 (0), т.е.
F2 (x = y3 = 0) = min W2 (x2,0) = min (22, 16) = 16,
x2
причем минимум достигается при значении х2, равном
` 2 (x = y3 = 0) = 1
Положим x = у3 = 1. Тогда, согласно (5),
0 £ x2 £ 2,
т.е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (7)
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!