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

Содержание

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

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

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

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

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

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

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

Литература

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

В цеху по сборке изделий А, В, С, D работают четыре линии. Во время сборки изделия А линию 1 не используют, а во время сборки изделия D используют только линии 1 и 3. Эти технологические линии имеют ограничение времени работы в сутки: линия 1 - 1000 мин, линия 2 - 600 мин, линия 3 - 780 мин, линия 4 - 800 мин.

В таблице 1 приведены продолжительности технологических операций на линиях во время сборки изделий каждого вида.

Таблица 1

Прибыль от продажи изделий: A - 6 y.e.; B - 5 y.e.; C - 6 y.e.; D - 5 y.e.

Определить наиболее выгодный суточный объем выпуска изделий каждого вида, обеспечивающий максимум прибыли.

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

с_j - норма расхода i-го вида ресурсов на управляющую переменную x_j

x_j - управляющая переменная

b_i - виды ресурсов

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

Для данной системы ограничения построим область допустимых решений (ОДР) которая образуется путем пересечения всех полуплоскостей системы ограничений, т.е. любая точка ОДР (на границе и внутри области) является допустимым решением задачи.

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

При данных условиях ограничения, для построения области необходимо отбросить две переменные (х_3, х₄).

Построим ОДР и целевую функцию, соответствующую данным ограничениям.

Решение задачи методом обхода вершин ОДР

Сравнивая значения целевой функции F в вершинах ОДР, видим, что в точке B (x1=2,414; x2=0,559) целевая функция достигает своего максимума. Следовательно, оптимальным планом производства является выпуск изделий в объеме x1=241,4, x2=55,9, при этом прибыль будет максимальной F=1727,9 у.е.

Решение задачи методом касательной.

Функция F представляет собой пучок параллельных прямых, каждая из которых соответствует определенному значению функционала. Например, при 4,1x₁+4,3x₂=5 целевая функция соответствует прямой, пересекающей ОДР. Значение целевой функции возрастает при параллельном перемещении прямой по направлению стрелки и достигает максимального значения в вершине С, в которой график целевой функции является касательной к ОДР.

Оптимальным решением задачи является значение:

х₁ = 2,414, х₂ = 0,559

f(2,414;0,559) = 17,279*100=1727,9 у.е.,

при этом ЦФ достигает своего максимума.

Определим устойчивость данного оптимального решения при изменении коэффициентов целевой функции. То есть определим диапазон изменения коэффициентов целевых функций, при которых оптимум остается неизменным (х₁ = 2,414, х₂ = 0,559).

Точка оптимума образуется пересечением дефицитных ограничений 3 и 4.

Определим диапазон устойчивости коэффициента C₁.

С₂=const=5.

Построим графики ЦФ

при С₁=0,5 F₁=0,5x₁+5x₂=4

при С₁=15 F₂=15x₁+5x₂=39

Правая часть ЦФ вычисляется путем подстановки координат точки оптимума B(2,414,0,559) в данные уравнения.

Значение ЦФ меняется в интервале от 4 до 39, образуется центральный пучок целевых функций с центром в вершине B(2,414;0,559), при котором точка оптимума устойчива. За пределами диапазона устойчивости С₁ точка оптимума будет меняться. При С₁<0,5 угол наклона ЦФ становится таким, что оптимум из вершины B дрейфует в вершину C. При С₁>15 оптимум из вершины B дрейфует в вершину A.

Определим диапазон устойчивости коэффициента C₂.

С₁=const=6

Построим графики ЦФ

при С₂=2 F₃=6x₁+2x₂=15,6

при С₂=60 F₄=6x₁+60x₂=48

Значение ЦФ меняется в интервале от 15,6 до 48, образуется центральный пучок целевых функций с центром в вершине B(2,414;0,559), при котором точка оптимума устойчива. За пределами диапазона устойчивости С₁ точка оптимума будет меняться. При С₁<2 угол наклона ЦФ становится таким, что оптимум из вершины B дрейфует в вершину A. При С₁>60 оптимум из вершины B дрейфует в вершину C.

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

Точка оптимума, вершина B, образована пересечением двух дефицитных ресурсов b₃ и b₄. Определим диапазон дефицитности ресурса b₃ b₃^min?b₃?b₃^max и определим дрейф точки оптимума.

При уменьшении b₃ прямая перемещается параллельно самой себе и достигает точки касания к вершине ОДР. При этом точка B дрейфует вдоль (4) и перемещается в B₁`, B<sub>1</sub>``, B<sub>1</sub>```. Дальнейшее уменьшение ресурса b<sub>3</sub> находится за пределами ОДР и он становится не дефицитным. Ресурс, уменьшаясь, образует пучок параллельных прямых, b<sub>3</sub><sup>min</sup>=0,8. Увеличивая правую часть b<sub>3</sub> строим пучок параллельных прямых, приходим в B<sub>2</sub>`.

b₃^max= 13,1, отсюда следует 80?b₃?1310

Определим диапазон дефицитности ресурса b₄ b₄^min?b₄?b₄^max и определим дрейф точки оптимума.

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

Увеличивая правую часть b₄ строим пучок параллельных прямых, приходим в B₁`.

b₄^max= 10,3, отсюда следует 250?b₄?1030

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

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

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

(СТ №1)

Из СТ №1 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».

X1 = (0,0,1000,600,780,800); F₁=0

Базис не оптимален, так как существуют C_j < 0

Переходим к новому базису:

1. Вводим в базис переменную х₁ т.к. С_j < 0. Выбираем из них наименьшее.

2. Определяем разрешающий элемент, т.е. переменную, которая вытесняется из базиса.

(СТ №2)

Из СТ №2 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».

X2 = (260,0,1000,340,0,540); F₂=1560

Базис не оптимален, так как существуют C_j < 0

Переходим к новому базису:

3. Вводим в базис переменную х₂ т.к. С_j < 0. Выбираем из них наименьшее.

4. Определяем разрешающий элемент, т.е. переменную, которая вытесняется из базиса.

(СТ №3)

Базис оптимален так как нет C_j < 0

Из СТ №3 непосредственно получаем решение: в базис входят только те переменные, которые имеют «Жорданово исключение».

X3 = (241,379; 55,862; 888,276; 79,31; 0; 0);

F₃=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 с.