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

После ввода последнего ограничения вместо Добавить вводим ОК.

После нажатия кнопки Выполнить найденные значения переменных х₁, х₂, х₃ и y будут находится в искомых ячейках.

Результат нахождения оптимума (максимума) с помощью электронной  таблицы Excel представлен в таблице 18 приложения Б.

 

3 МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ  ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ С ПОМОЩЬЮ МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

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

В линейных моделях целевая функция и ограничения заданы линейными уравнениями

F(х₁, х₂,…, х_n) = c₁ + a₁∙х₁ + a₂∙х₂ +…+ a_n∙х_n             (44)

Поэтому частные производные целевой функции не равны нулю

, , …, ≠ 0.                 (45)

Следовательно, аналитическим  методом найти экстремум точки  невозможно. Как правило, экстремум точки находится на границе области, которая образована системой ограничений.

Для решения задач  линейного программирования необходимо сначало построить математическую модель:

1) выбрать целевую  функцию, которую необходимо минимизировать или максимизировать;

2) выбрать независимые  переменные х₁, х₂, …, х_n;

3) составить ограничения  и целевую функцию в зависимости  от условий задачи.

Составим математическую модель для нашей задачи линейного программирования. Производственное задание данной задачи представлено в таблице 1 приложения В.

F – прибыль от реализации продукции; F → max.

х₁ – количество платьев, которые необходимо изготовить;

х₂ – количество халатов, которые необходимо изготовить.

Составим целевую функцию:

F = 110∙х₁ + 88∙х₂ → max.                (46)

и ограничения для  нее:

                 (47)

3.2 Графический  метод решения задачи линейного  программирования

Математическая модель задана выражениями

F(х₁, х₂) = c₀ + с₁∙х₁ + с₂∙х₂ → extr               (46)

                  (47)

1. Построение на плоскости (х₁, х₂) множества точек, удовлетворяющих одновременно всем ограничениям.

2. Отыскание на построенном графике оптимальной точки, в которой находится Fmin или Fmax, определение ее координат и значения функции в этой точке.

При решении задач  линейного программирования возможны следующие варианты:

1) Множество допустимых  решений не существует, т.е. на  плоскости (х₁, х₂) нет ни одной точки, которая бы удовлетворяла одновременно всем ограничениям. В этом случае решения задачи линейного программирования не существует.

2) Множество допустимых  решений – одна точка, эта  же точка является оптимальной.

3) Множество допустимых  решений – замкнутый выпуклый многоугольник. В этом случае оптимальные точки находятся на границе данного многоугольника, т.е. в одной из его вершин. Анализируется каждая вершина, их координаты подставляются в целевую функцию и выбирается оптимальная.

4) Множество допустимых решений – разомкнутый выпуклый многоугольник. В этом случае оптимальное решение зависит от ориентации линий уровня целевой функции и направления, в котором его значения нарастают. Конечное решение либо существует, либо нет. Если конечное решение не существует, то это связано с недостаточной полнотой ограничения.

Решим графическим методом  данную задачу линейного программирования. Для этого строим на плоскости (х₁, х₂) ограничения (47), полученные в п.3.1.

Графическое представление  ограничений целевой функции представлено на рисунке 1.

Рисунок 1 – Область допустимых решений

                                                                                                                                                                                                                                                                                                                                                                                          

Находим оптимальное  решение целевой функции следующим способом. Определяем координаты краевых точек полученного выпуклого треугольника АВС, подставляем координаты в уравнение целевой функции и из всех значений целевой функции выбираем оптимальное.

Значение целевой функции  в точке А(0; 80):

F(A) = 110∙0 + 88∙80 = 7040.

Значение целевой функции  в точке В(56,6; 80):

F(В) = 110∙56,6 + 88∙0 = 6226.

Значение целевой функции  в точке С(0; 0):

F(С) = 0.

Таким образом, в точке  А целевая функция имеет оптимальное  значение. Так, при выпуске только халатов в количестве 80 штук получили максимальную прибыль 7040 руб.

3.3 Симплекс-метод  решения задачи линейного программирования

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

1. Определение вершин области допустимых значений как точка пересечения ограничений;

2. Определения значения  целевой функции в каждой вершине;

3. Вершина, в которой  целевая функция приобретает  оптимальное значение (max или min) является оптимальной вершиной.

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

Рассмотрим общую схему  решения задач линейного программирования. Пусть необходимо найти n неизвестных x₁, x₂, x₃ …, x_n, значения которых удовлетворяют следующим условиям:

                (48)

где j = 1, 2, …, n, и минимизируют целевую функцию:

F = с₁∙х₁ + с₂∙х₂ +…+ c_nx_n → min               (49)

Введем в задачу ряд  положительных переменных x_n+1, x_n+2, …, x_n+m, которые называются базисными. Они показывают на сколько правые части неравенств (48) больше, чем левые, т.е. показывают величину неиспользованного ресурса.

               (50)

Таким образом, неравенство (48) превращается в равенство (51).

               (51)

Таким образом, задача с  ограничениями в виде неравенств (48) сводится к задаче на отыскание неотрицательных значений переменных x₁, x₂, x₃ …, x_n,, которые называются свободными и x_n+1, x_n+2, …, x_n+m  (базисные), которые удовлетворяют системе уравнений (51) и минимальному значению целевой функции (49), которую можно записать в следующем виде

F = с₁∙х₁ + с₂∙х₂ + c_nx_n + 0∙x_{n +1} + 0∙x_{n +2} +…+ 0∙x_n+m → min           (52)

В полученной системе  за исходный опорный план можно принять:

1) значение свободных  переменных равняется нулю (x₁ = 0, x₂ = 0, …,    x_n = 0);

2) значения базисных  переменных равны:

x_n+1 = b₁;

x_n+2 = b₂;

…;

x_n+m = b_m.

3) с экономической  точки зрения, если продукция  не выпускается, то величина неиспользованного ресурса будет равна запасу данных ресурсов, при этом, целевая функция тоже равна нулю F = 0.

Так как первоначальный базис состоит из дополнительно  введенных переменных x_n+1, x_n+2, …, x_n+m, то итерации симплекс-метода сводятся к исключению из базиса базисных переменных и ввода свободных.

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

Математическая модель задачи ипредставлена выражениями (46) и (47)

Так как симплекс-метод  применяется только для нахождения минимума, то задача отыскания максимума сводится к задаче минимизации с противоположным знаком

F = –110∙х₁ – 88∙х₂ → min.                (53)

Преобразуем неравенство (47) в равенство, добавив в каждое уравнение базисную переменную

Чтобы минимизировать данную функцию, необходимо, чтобы все коэффициенты в ней были положительными. Тогда минимум будет в том случае, если переменные, входящие в уравнение равны нулю. Поэтому необходимо выразить свободные переменные через базисные и ввести базисные переменные в уравнение целевой функции.

Составим симплекс-таблицу 2 и внесем в нее исходные равенства. По мере нахождения оптимального значения F каждое новое решение вносим в симплекс-таблицу 2.

 

Таблица 2 – Симплекс-таблица

Базисная переменная	х1	х2	х3	х4	х5	Свободный член	Базисное решение
1	2	3	4	5	6	7	8
x3 x4 x5	2,12 1,3 1	1,5 1,4 1	1 0 0	0 1 0	0 0 1	120 130 80	120/2,12 = 56,604- min 130/1,3 = 100 80/1 = 80
F	– 110	– 88	0	0	0	0	F(0;0;120; 130; 80) = 0
x1	1	0,707	0,472	0	0	56,604	56,604/0,707 = 80,062
Продолжение таблицы 2
x4 x5	0 0	0,4809 0,293	- 0,6136 - 0,472	1 0	0 1	56,4148 23,396	56,4148/0,4809=117,3108 23,396/0,293 = 79,85-min
F	0	- 10,23	51,920	0	0	- 6226,44	F(56,604;0;0;56,4148; 23,396) = - 6226,44
x1	1	0	1,611	0	- 2,413	0,15
x4 x2	0 0	0 1	0,1614 - 1,611	1 0	- 1,641 3,413	18,0148 79,850
F	0	0	35,44	0	34,915	-7043,305	F(0,15;79,85;0;18,0148;0) = - 7043,305

 

Чтобы решить эту задачу в целевой функции выберем  опорный элемент при той переменной, которая в целевой функции  имеет отрицательное значение. Т.к. в нашем случае все переменные имеют отрицательные значения коэффициентов, то выберем переменную с наибольшим отрицательным коэффициентом, т.е. переменную x₁.

Далее смотрим из какой  строки выберем опорный элемент. Выбираем из той строки, в которой коэффициент является положительным. В нашем случае все коэффициенты положительны, поэтому делим свободные члены уравнения на коэффициент при x₁ для каждой строки и выбираем опорный элемент из той строки, где данное значение наименьшее.

Наименьшее базисное решение получили в 1-й строке, поэтому выражаем из этой строки x₁:

2,12x₁ + 1,5x₂ + x₃ = 120;

x₁ = 56,604 – 0,707x₂ – 0,472x₃.

Подставляем данное значение в оставшиеся ограничения и целевую  функцию.

Подставим в 2-е уравнение:

1,3(56,604 – 0,707x₂ – 0,472x₃) + 1,4x₂ + x₄ = 130;

0,4809x₂ – 0,6136x₃ + x₄ = 56,4148.

Подставим в 3-е уравнение:

56,604 – 0,707x₂ – 0,472x₃ + x₂ + x₅ = 80;

0,293x₂ – 0,472x₃ + x₅ = 23,396.

Подставим в целевую  функцию:

F = – 110(56,604 – 0,707x₂ – 0,472x₃) – 88x₂

F = – 10,23x₂ + 51,92x₃ – 6226,44.

Решение на втором этапе  не является оптимальным, т.к. в целевую  функцию F входит переменная x₂ с отрицательным коэффициентом.

Оптимальное решение  будет найдено, когда все коэффициенты в целевой функции будут положительны. Так как в целевой функции  отрицательным является коэффициент при x₂, то делим на него свободный коэффициент и выделяем минимальное решение.

Наименьшее базисное решение получили в 3-й строке, поэтому выражаем из этой строки x₂:

0,293x₂ – 0,472x₃ + x₅ = 23,396;

х₂ = 79,850 + 1,611x₃ – 3,413x₅.

Подставим в 1-е уравнение:

x₁ + 0,707(79,850 + 1,611x₃ – 3,413x₅) + 0,472x₃ = 56,604;

x₁ + 1,611x₃ – 2,413x₅ = 0,15.

Подставим в 2-е уравнение:

0,4809(79,850 + 1,611x₃ – 3,413x₅) – 0,6136x₃ + x₄ = 56,4148;

0,1614x₃ + x₄ – 1,641x₅ = 18,0148.

Подставим в целевую функцию:

F = –10,23(79,850 + 1,611x₃ – 3,413x₅) + 51,92x₃ –6226,44;

F = 35,44x₃ + 34,915x₅ – 7043,305.