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

  • Вид работы:
    Контрольная работа
  • Предмет:
    Менеджмент
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    730,43 Кб
  • Опубликовано:
    2013-02-16
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

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

Содержание

1. Содержательная постановка оптимизационной задачи

. Математическая модель в аналитическом и информационном виде

. Графический метод решения

. Определение диапазона дефицитности ресурсов bj, динамики ОДР и дрейфа оптимума

. Решение задачи табличным симплекс-методом

. Решение задачи в среде MS Excel

. Факторы эффективности решения задачи исследования и оптимального планирования операций

Литература

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

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`.3max= 13,1, отсюда следует 80≤b3≤1310

Определим диапазон дефицитности ресурса b4 b4min≤b4≤b4max и определим дрейф точки оптимума.


При уменьшении b4, образуется пучок параллельных прямых, предельное значение b4 определяется в вершине касания b4 с ОДР. За пределами вершины касания b4 становится недефицитным. b4min=2,5. Точка оптимума перемещается вдоль ограничения (3) и достигает точки B2`.

Увеличивая правую часть b4 строим пучок параллельных прямых, приходим в B1`.4max= 10,3, отсюда следует 250≤b4≤1030

5. Решение задачи табличным симплекс-методом


Решим задачу табличным симплекс-методом, для этого запишем исходную задачу в каноничной форме.


Запишем исходные данные канонической формы в компактную симплекс-таблицу.

 

(СТ №1)

Базис

bj

x1

x2

x3

x4

x5

x6

Элем. преобр.

X3

1000

0

2

1

0

0

0

-

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 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».= (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

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

1560

0

-3

0

0

2

0

-

 

Из СТ №2 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».= (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 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».= (241,379; 55,862; 888,276; 79,31; 0; 0);3=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 с.

.        Воевудский Е.Н. Управление на морском транспорте - М. Транспорт, 1993 - 366 с.

Похожие работы на - Решение задачи оптимального планирования работы технологических линий

 

Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!