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

Так как в целевой  функции все коэффициенты положительны, то приравниваем переменные x₃ и x₅ к нулю и получаем оптимальное значение функции:

F_min = – 7043,305;

F_max = 7043,305.

Значения остальных  переменных находим из уравнений при условии, что x₃ = 0 и x₅ = 0 из соответствующего уравнения.

Таким образом, при выпуске  только 80 халатов достигается максимальная прибыль 7043 руб. При этом ткань первого артикула будет использована полностью (x₃ = 0), ткань второго артикула останется в количестве 18 м. и никаких других изделий изготавливаться не будет (x₅ = 0).

3.4 Решение  двойственной задачи линейного программирования

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

Исходная задача:

                (54)

где x₁, x₂, x₃ …, x_n ≥ 0.

Целевая функция:

F = с₁∙х₁ + с₂∙х₂ +…+ c_nx_n → mах               (55)

Тогда двойственная задача имеет следующий вид

                (56)

где y₁, y₂, …, y_n ≥ 0.

Целевая функция двойственной задачи:

f = b₁y₁ + b₂y₂ + … + b_my_m → min.               (57)

Сравнивая обе задачи, получаем

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

Матрица исходной задачи

А =                  (58)

Матрица двойственной задачи

А’ = .                 (59)

2. В исходной задаче n переменных, m ограничений, в двойственной – m переменных, n ограничений.

3. В правых частях  систем ограничений (54) и (56) в каждой из задач стоят коэффициенты целевой функции, взятые из другой задачи.

4. В систему ограничений  исходной задачи входят неравенства  типа ≤. Причем в задаче  требуется максимизировать целевую функцию F. В систему ограничений двойственной задачи входят неравенства типа ≥ и требуется минимизировать целевую функцию f.

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

 

Таблица 3 – Преобразование исходной задачи в двойственную

	x1	x2	…	xn	bi
y1 y2 … ym ci	a11 a21 … am1 c1	a12 a22 … am2 c2	… … … … …	a1n a2n … amn cn	b1 b2 … bm

 

При этом устанавливается  такое соответствие:

1) переменной х₁ исходной задачи соответствует 1-е ограничение двойственной задачи, переменной х₂ – 2-е ограничение двойственной задачи и т.д.;

2) переменной у₁ двойственной задачи соответствует 1-е ограничение исходной задачи, переменной у₂ - 2-е ограничение исходной задачи и т.д.;

3) если система ограничений  исходной задачи на максимум, кроме ограничений типа ≤, содержит неравенство типа ≥, то перед построением двойственной задачи первые части неравенства типа ≥ необходимо умножить на (-1) и поменять знак на ≤; а в задачах на минимум для неравенств типа ≤ также необходимо умножить правую часть на (-1) и поменять знак на ≥;

4) если в исходной  задаче имеются ограничения, заданные  равенствами, то каждая из них заменяется двумя ограничениями-неравенствами, а затем, в зависимости от типа задач, поступают как было сказано в п.3.

Решим двойственную задачу на нашем примере.

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

Cоставим таблицу 4 перехода от исходной задачи к двойственной.

 

Таблица 4 – Преобразование исходной задачи в двойственную

	x1	x2	bi
y1 y2 ym ci	2,12 1,3 1 110	1,5 1,4 1 88	120 130 80

 

Руководствуясь таблицей, составим модель двойственной задачи:

                (60)

f = 120y₁ + 130y₂ + 80y₃ → min               (61)

Решаем двойственную задачу симплекс-методом. Для этого  введем базисные переменные для каждого ограничения (60).

Базисные переменные вводим со знаком “–”, т.к. они показывают на сколько правая часть ограничения меньше, чем левая.

                (62)

Первое решение не можем взять за оптимальное, т.к. у₄ и y₅ отрицательные. Оптимальным будет решение, когда все коэффициенты целевой функции положительны и значения у положительны.

Составим симтлекс-таблицу 5.

 

Таблица 5 – Симплекс-таблица двойственной задачи

Базисная переменная	y1	y2	y3	y4	y5	Свободный член	Базисное решение
1	2	3	4	5	6	7	8
y4 y5	2,12 1,5	1,3 1,4	1 1	-1 0	0 -1	110 88	110/1 = 110 88/1 = 88 - min
f	120	130	80	0	0	0	f(0;0;0;-110;-88) = 0
y4 y3	0,62 1,5	-0,1 1,4	0 1	-1 0	1 -1	22 88
f	0	18	0	0	80	7040	f(0;0;-88;-22;0;) = 7040

 

Из таблицы выбираем опорный элемент при той переменной, которая в целевой функции  имеет наименьший коэффициент – при у₃.

Выражаем у₃ из 2-ой строки:

у₃ = 88 + у₅ – 1,5у₁ – 1,4у₂.

Подставим в 1-ю строку:

- у₄ + 2,12у₁ + 1,3у₂ + 88 + у₅ – 1,5у₁ – 1,4у₂ = 110;

0,62у₁ – 0,1у₂ – у₄ + у₅ = 22.

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

f = 120y₁ + 130y₂ + 80(88 + у₅ – 1,5у₁ – 1,4у₂);

f = 18y₂ + 80y₅ + 7040.

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

х₁ = у₄ = 0;

x₂ = у₅ = 80.

То есть для получения  наибольшей прибыли 7040 руб. необходимо изготовить 80 халатов и ни одного платья. При этом ткань первого артикула будет использована полностью (у₁ = 0), ткань второго артикула останется в количестве 18 м. (у₂ = 18)и никаких других изделий изготавливаться не будет (у₃ = 0).

3.5 Решение  задачи линейного программирования  с помощью электронной таблицы Excel

1. Для решения данной задачи линейного программирования в Excel вводим условия в форме таблицы 8 приложения В.

2. В созданную форму вводим исходные данные.

3. В созданную форму вводим зависимости из математической модели.

31. Вводим зависимость для целевой функции, для этого выделяем ячейку ЦФ, вызываем Мастер функций, в окне Категория выбираем Математические, в окне Функции – СУММПР0ИЗВ:

– в массив 1 - вводим номера ячеек, где будут находиться Значения переменных Х₁ и Х₂.

– в массив 2 - номера ячеек, где находятся Коэф.в ЦФ этих переменных.

3.2. Вводим зависимости для левых частей ограничений. Выделяем ячейку для левой части соответствующего ограничения, выбираем функцию СУММПРОИЗВ:

– в массив 1 - вводим номера ячеек, где будут находиться Значения переменных Х₁ и Х₂;

– в массив 2 - номера ячеек, где находятся коэффициенты при данных переменных в соответствующих ограничениях.

Для поиска решения выделяем ячейку ЦФ, в главном меню выбираем <span class="dash041e_0431_044b_0447_043d_044b_0439_0020_0028_0432_0435_0431_0029__Char" style=" font-size: 14pt; font