Решение задачи оптимального планирования работы технологических линий
Определение наиболее выгодного суточного объема выпуска изделий, обеспечивающего максимум прибыли. Построение математической модели задачи, ее решение графическим методом и в среде MS Excel. Расчет диапазона дефицитности ресурсов и дрейфа оптимума.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.02.2013 |
| Размер файла | 994,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
1. Содержательная постановка оптимизационной задачи
2. Математическая модель в аналитическом и информационном виде
3. Графический метод решения
4. Определение диапазона дефицитности ресурсов bj, динамики ОДР и дрейфа оптимума
5. Решение задачи табличным симплекс-методом
6. Решение задачи в среде MS Excel
7. Факторы эффективности решения задачи исследования и оптимального планирования операций
Литература
1. Содержательная постановка оптимизационной задачи
В цеху по сборке изделий А, В, С, D работают четыре линии. Во время сборки изделия А линию 1 не используют, а во время сборки изделия D используют только линии 1 и 3. Эти технологические линии имеют ограничение времени работы в сутки: линия 1 - 1000 мин, линия 2 - 600 мин, линия 3 - 780 мин, линия 4 - 800 мин.
В таблице 1 приведены продолжительности технологических операций на линиях во время сборки изделий каждого вида.
Таблица 1
|
Изделие |
Продолжительность технологической операции, мин/изд. |
||||
|
Линия 1 |
Линия 2 |
Линия 3 |
Линия 4 |
||
|
A |
- |
1 |
3 |
1 |
|
|
B |
2 |
5 |
1 |
10 |
|
|
C |
3 |
4 |
10 |
20 |
|
|
D |
50 |
- |
12 |
- |
Прибыль от продажи изделий: A - 6 y.e.; B - 5 y.e.; C - 6 y.e.; D - 5 y.e.
Определить наиболее выгодный суточный объем выпуска изделий каждого вида, обеспечивающий максимум прибыли.
2. Математическая модель в аналитическом и информационном виде
сj - норма расхода i-го вида ресурсов на управляющую переменную xj
xj - управляющая переменная
bi - виды ресурсов
3. Графический метод решения
Для данной системы ограничения построим область допустимых решений (ОДР) которая образуется путем пересечения всех полуплоскостей системы ограничений, т.е. любая точка ОДР (на границе и внутри области) является допустимым решением задачи.
Пересечения полуплоскостей строим по точкам пересечения границ полуплоскостей с осями координат.
При данных условиях ограничения, для построения области необходимо отбросить две переменные (х3, х4).
Построим ОДР и целевую функцию, соответствующую данным ограничениям.
Решение задачи методом обхода вершин ОДР
|
Вершина ОДР |
Координаты вершины |
Значения целевой функции F |
Примечание |
||
|
x1 |
x2 |
||||
|
A |
0 |
0,8 |
4 |
||
|
B |
2,414 |
0,559 |
17,279 |
Max F |
|
|
C |
2,6 |
0 |
15,6 |
||
|
D |
0 |
0 |
0 |
Min F |
Сравнивая значения целевой функции F в вершинах ОДР, видим, что в точке B (x1=2,414; x2=0,559) целевая функция достигает своего максимума. Следовательно, оптимальным планом производства является выпуск изделий в объеме x1=241,4, x2=55,9, при этом прибыль будет максимальной F=1727,9 у.е.
Решение задачи методом касательной.
Функция F представляет собой пучок параллельных прямых, каждая из которых соответствует определенному значению функционала. Например, при 4,1x1+4,3x2=5 целевая функция соответствует прямой, пересекающей ОДР. Значение целевой функции возрастает при параллельном перемещении прямой по направлению стрелки и достигает максимального значения в вершине С, в которой график целевой функции является касательной к ОДР.
Оптимальным решением задачи является значение:
х1 = 2,414, х2 = 0,559
f(2,414;0,559) = 17,279*100=1727,9 у.е.,
при этом ЦФ достигает своего максимума.
Определим устойчивость данного оптимального решения при изменении коэффициентов целевой функции. То есть определим диапазон изменения коэффициентов целевых функций, при которых оптимум остается неизменным (х1 = 2,414, х2 = 0,559).
Точка оптимума образуется пересечением дефицитных ограничений 3 и 4.
Определим диапазон устойчивости коэффициента C1.
С2=const=5.
Построим графики ЦФ
при С1=0,5 F1=0,5x1+5x2=4
при С1=15 F2=15x1+5x2=39
Правая часть ЦФ вычисляется путем подстановки координат точки оптимума B(2,414,0,559) в данные уравнения.
Значение ЦФ меняется в интервале от 4 до 39, образуется центральный пучок целевых функций с центром в вершине B(2,414;0,559), при котором точка оптимума устойчива. За пределами диапазона устойчивости С1 точка оптимума будет меняться. При С1<0,5 угол наклона ЦФ становится таким, что оптимум из вершины B дрейфует в вершину C. При С1>15 оптимум из вершины B дрейфует в вершину A.
Определим диапазон устойчивости коэффициента C2.
С1=const=6
Построим графики ЦФ
при С2=2 F3=6x1+2x2=15,6
при С2=60 F4=6x1+60x2=48
Значение ЦФ меняется в интервале от 15,6 до 48, образуется центральный пучок целевых функций с центром в вершине B(2,414;0,559), при котором точка оптимума устойчива. За пределами диапазона устойчивости С1 точка оптимума будет меняться. При С1<2 угол наклона ЦФ становится таким, что оптимум из вершины B дрейфует в вершину A. При С1>60 оптимум из вершины B дрейфует в вершину C.
4. Определение диапазона дефицитности ресурсов bj, динамики ОДР и дрейфа оптимума
Точка оптимума, вершина B, образована пересечением двух дефицитных ресурсов b3 и b4. Определим диапазон дефицитности ресурса b3 b3min?b3?b3max и определим дрейф точки оптимума.
При уменьшении b3 прямая перемещается параллельно самой себе и достигает точки касания к вершине ОДР. При этом точка B дрейфует вдоль (4) и перемещается в B1`, B1``, B1```. Дальнейшее уменьшение ресурса b3 находится за пределами ОДР и он становится не дефицитным. Ресурс, уменьшаясь, образует пучок параллельных прямых, b3min=0,8. Увеличивая правую часть b3 строим пучок параллельных прямых, приходим в B2`.
b3max= 13,1, отсюда следует 80?b3?1310
Определим диапазон дефицитности ресурса b4 b4min?b4?b4max и определим дрейф точки оптимума.
При уменьшении b4, образуется пучок параллельных прямых, предельное значение b4 определяется в вершине касания b4 с ОДР. За пределами вершины касания b4 становится недефицитным. b4min=2,5. Точка оптимума перемещается вдоль ограничения (3) и достигает точки B2`.
Увеличивая правую часть b4 строим пучок параллельных прямых, приходим в B1`.
b4max= 10,3, отсюда следует 250?b4?1030
5. Решение задачи табличным симплекс-методом
Решим задачу табличным симплекс-методом, для этого запишем исходную задачу в каноничной форме.
Запишем исходные данные канонической формы в компактную симплекс-таблицу.
(СТ №1)
|
Базис |
bj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Элем. преобр. |
|
|
X3 |
1000 |
0 |
2 |
1 |
0 |
0 |
0 |
- |
|
|
X4 |
600 |
1 |
5 |
0 |
1 |
0 |
0 |
- |
|
|
X5 |
780 |
3 |
1 |
0 |
0 |
1 |
0 |
РС/3 |
|
|
X6 |
800 |
1 |
10 |
0 |
0 |
0 |
1 |
- |
|
|
- Cj |
0 |
-6 |
-5 |
0 |
0 |
0 |
0 |
- |
Из СТ №1 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».
X1 = (0,0,1000,600,780,800); F1=0
Базис не оптимален, так как существуют Cj < 0
Переходим к новому базису:
1. Вводим в базис переменную х1 т.к. Сj < 0. Выбираем из них наименьшее.
2. Определяем разрешающий элемент, т.е. переменную, которая вытесняется из базиса.
|
Базис |
bj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Элем. преобр. |
|
|
X3 |
1000 |
0 |
2 |
1 |
0 |
0 |
0 |
- |
|
|
X4 |
600 |
1 |
5 |
0 |
1 |
0 |
0 |
II-PC |
|
|
X1 |
260 |
1 |
0,333 |
0 |
0 |
0,333 |
0 |
РС |
|
|
X6 |
800 |
1 |
10 |
0 |
0 |
0 |
1 |
IV-PC |
|
|
- Cj |
0 |
-6 |
-5 |
0 |
0 |
0 |
0 |
V+PC*6 |
(СТ №2)
|
Базис |
bj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Элем. преобр. |
|
|
X3 |
1000 |
0 |
2 |
1 |
0 |
0 |
0 |
- |
|
|
X4 |
340 |
0 |
4,667 |
0 |
1 |
-0,333 |
0 |
- |
|
|
X1 |
260 |
1 |
0,333 |
0 |
0 |
0,333 |
0 |
- |
|
|
X6 |
540 |
0 |
9,667 |
0 |
0 |
0 |
1 |
РС/9,667 |
|
|
- Cj |
1560 |
0 |
-3 |
0 |
0 |
2 |
0 |
- |
Из СТ №2 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».
X2 = (260,0,1000,340,0,540); F2=1560
Базис не оптимален, так как существуют Cj < 0
Переходим к новому базису:
3. Вводим в базис переменную х2 т.к. Сj < 0. Выбираем из них наименьшее.
4. Определяем разрешающий элемент, т.е. переменную, которая вытесняется из базиса.
|
Базис |
bj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Элем. преобр. |
|
|
X3 |
1000 |
0 |
2 |
1 |
0 |
0 |
0 |
I-PC*2 |
|
|
X4 |
340 |
0 |
4,667 |
0 |
1 |
-0,333 |
0 |
II-PC*4,667 |
|
|
X1 |
260 |
1 |
0,333 |
0 |
0 |
0,333 |
0 |
III-PC*0,33 |
|
|
X2 |
55,862 |
0 |
1 |
0 |
0 |
-0,034 |
0,103 |
РС |
|
|
- Cj |
1560 |
0 |
-3 |
0 |
0 |
2 |
0 |
V+PC*3 |
(СТ №3)
|
Базис |
bj |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
Элем. преобр. |
|
|
X3 |
888,276 |
0 |
0 |
1 |
0 |
0,069 |
-0,207 |
- |
|
|
X4 |
79,31 |
0 |
0 |
0 |
1 |
-0,172 |
-0,483 |
- |
|
|
X1 |
241,379 |
1 |
0 |
0 |
0 |
0,345 |
-0,034 |
- |
|
|
X2 |
55,862 |
0 |
1 |
0 |
0 |
-0,034 |
0,103 |
- |
|
|
- Cj |
1727,586 |
0 |
0 |
0 |
0 |
1,897 |
0,31 |
- |
Базис оптимален так как нет Cj < 0
Из СТ №3 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».
X3 = (241,379; 55,862; 888,276; 79,31; 0; 0);
F3=1727,586 - максимальное значение F.
6. Решение задачи в среде MS Excel
прибыль математический дефицитность оптимум
Проведем расчеты исходной задачи в Excel, с помощью «Поиска решений». При этом математическая модель остается та же.
Составим табличную модель.
После составления табличной модели выбираем вкладку Данные Поиск решения. Здесь мы указываем все необходимые параметры и ограничения, после чего выбираем целевую ячейку H4 и нажимаем «Выполнить».
В результате получаем:
Полученное нами с помощью сервиса «Поиск решения» в Excel значение совпадает с полученным решением табличного симплекс-метода. Исходя из него, максимальное значение нашей функции составляет 1727,586 у.е.
Ответ: наиболее выгодный суточный объем выпуска изделий, при котором максимальная прибыль составит 1727,586 у.е., будет получен при изготовлении 241,38 ед. изделий А, 55,86 ед. изделий В, 0 ед. изделий С и 0 ед. изделий D.
7. Факторы эффективности решения задачи исследования и оптимального планирования операций
Анализируя полученное решение, можно прийти к выводу, что ограничение времени работы в сутки линии 3 является ограничивающим фактором в получении прибыли. Если увеличить время работы третьей линии на 460 минут, будет получена суммарная прибыль в размере 2600 у.е.
Литература
1. Экономико-математические методы и модели в управлении морским транспортом. Под редакцией Воевудского Е.Н. - М. Транспорт, 1988 - 384 с.
2. Громовой Э.П. Математические модели и методы в планировании и управлении на морском транспорте - М. Транспорт, 1979 - 360 с.
3. Воевудский Е.Н. Управление на морском транспорте - М. Транспорт, 1993 - 366 с.
Размещено на Allbest.ru
Подобные документы
Составление математической модели и решение задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли. Нахождение оптимального решения двойственной задачи с указанием дефицитной продукции при помощи теорем двойственности.
контрольная работа [232,3 K], добавлен 02.01.2012Определение оптимальных объемов производства по видам изделий за плановый период и построение их математической модели, обеспечивающей максимальную прибыль предприятию. Решение задачи по минимизации затрат на перевозку товаров средствами модели MS Excel.
курсовая работа [3,4 M], добавлен 26.05.2013Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.
контрольная работа [80,8 K], добавлен 13.12.2010Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Определение оптимального выпуска товаров, обеспечивающего максимум прибыли. Построение модели, описывающей зависимость между факторами и объемом продажи. Нахождение нового объема продаж при измененных факторах. Вычисление неизвестных параметров модели.
контрольная работа [279,8 K], добавлен 16.04.2013Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Составление линейной оптимизационной модели и ее решение графическим методом. Сетевое и календарное планирование, расчет и представление на графике временных характеристик событий. Управление запасами, расчет наиболее выгодного режима работы завода.
контрольная работа [1,5 M], добавлен 15.11.2010Построение математической модели и решение задачи математического программирования в средах MathCad и MS Excel. Решение систем с произвольными векторами свободных коэффициентов. Определение вектора невязки. Минимизация и максимизация целевой функции.
отчет по практике [323,5 K], добавлен 01.10.2013Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014
