3. Обоснование вычислительной процедуры

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

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

4. Решение задачи оптимизации на основе симплекс-метода

Для решения задачи симплекс методом приведем построенную математическую модель к стандартному виду. Для этого в ограничение “больше либо равно” введём избыточные переменные:

6 000 ∙ X₁+8 000 ∙ X₂ +11 000 ∙ X₃ = 12 000 000;

X₁ – X₄ = 100;

X₂ – X₅ = 200;

X₃ – X₆ = 300;

– E = – 12 ∙ X₁ – 15 ∙ X₂ – 24 ∙ X₃ → max.

Однако в ограничениях отсутствуют базисные переменные, введем искусственные переменные:

6 000 ∙ X₁+8 000 ∙ X₂ +11 000 ∙ X₃ + X₇= 12 000 000;

X₁ – X₄ + X₈ = 100;

X₂ – X₅ + X₉ = 200;

X₃ – X₆ + X₁₀ = 300.

Искусственная целевая функция будет подвержена минимизации и имеет вид:

W = X₇ + X₈ + X₉ + X₁₀ → min.

Далее необходимо выразить искусственную целевую функцию через небазисные переменные, то есть, выразим переменные X₇, X₈, X₉, X₁₀ через небазисные и подставим в выражение для искусственной целевой функции, а также для приведения задачи к стандартной форме ее необходимо подвергнуть максимизации:

X₇ = 12 000 000 – 6 000 X₁ – 8 000 ∙ X₂ –11 000 ∙ X₃;

X₈ = 100 –X₁ + X₄;

X₉ = 200 – X₂ + X₅;

X₁₀ = 300 – X₃ + X₆;

W = 12 000 600 – 6 001 X₁ – 8 001 X₂ – 11 001 X₃ + X₄+ X₅+ X₆→ min;

–W = –12 000 600+6 001 X₁ + 8 001 X₂ + 11 001 X₃– X₄ – X₅ – X₆→max;

В итоге полная математическая модель будет иметь вид:

6 000 ∙ X₁+8 000 ∙ X₂ +11 000 ∙ X₃ + X₇= 12 000 000;

X₁ – X₄ + X₈ = 100;

X₂ – X₅ + X₉ = 200;

X₃ – X₆ + X₁₀ = 300;

–W = –12 000 600+6 001 X₁ + 8 001 X₂ + 11 001 X₃– X₄ – X₅ – X₆→max;

– E = – 12 ∙ X₁ – 15 ∙ X₂ – 24 ∙ X₃ → max.

Первый этап.

Приступим к составлению исходной симплекс-таблицы (таблица 1.1) которая включает в себя строку искусственной целевой функции и столбцы с искусственными переменными.

Таблица 1.1 – Первая симплекс-таблица.

Базис	X 1	X 2	X 3	X 4	X 5	X 6	X 7	X 8	X 9	X 10	Решение
-E	12	15	24	0	0	0	0	0	0	0	0
-W	-6001	-8001	-11001	1	1	1	-1	0	0	0	-12000600
X 7	1	0	0	-1	0	0	1	0	0	0	100
X 8	0	1	0	0	-1	0	0	1	0	0	200
X 9	0	0	1	0	0	-1	0	0	1	0	300
X 10	6000	8000	11000	0	0	0	0	0	0	1	12000000

Однако решение данной симплекс-таблицы не удовлетворяет условию, то есть условие о выпуске седанов, пикапов и спортивных автомобилей, так как X₁, X₂, X₃ = 0, а необходимо выпустить не менее 100, 200, 300 автомобилей соответственно.

Приступим к решению задачи двухэтапным методом. На первом этапе приступим к минимизации искусственной целевой функции. Для этого преобразуем таблицу 1.1. Выбирается переменная для включения в базис: это переменная X₃, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.

Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 300/1=300, 12000000/11000=1090.

Минимальное симплексное отношение соответствует переменной X₉; значит, эта переменная исключается из базиса.

В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 1.2).

Таблица 1.2 – Первое допустимое решение.

Базис	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Решение
-E	12	15	0	0	0	24	0	0	-24	0	-7200
-W	-6001	-8001	0	1	1	-11000	-1	0	11001	0	-8700300
X7	1	0	0	-1	0	0	1	0	0	0	100
X8	0	1	0	0	-1	0	0	1	0	0	200
X3	0	0	1	0	0	-1	0	0	1	0	300
X10	6000	8000	0	0	0	11000	0	0	-11000	1	8700000

Однако решение данной симплекс-таблицы не удовлетворяет условию, то есть условие о выпуске седанов, пикапов и спортивных автомобилей, так как X₁, X₂= 0, а необходимо выпустить не менее 100, 200 автомобилей соответственно.

Преобразуем таблицу 1.2. Выбирается переменная для включения в базис: это переменная X₆, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.

Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 8700000/11000=791. Минимальное симплексное отношение соответствует переменной X₁₀; значит, эта переменная исключается из базиса.

В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 1.3).

таблица 1.3

Базис	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Решение
-E	-1,091	-2,455	0	0	0	0	0	0	0	-0,002182	-26181,81818
-W	-1	-1	0	1	1	0	-1	0	1	1	-300
X7	1	0	0	-1	0	0	1	0	0	0	100
X8	0	1	0	0	-1	0	0	1	0	0	200
X3	0,5455	0,7273	1	0	0	0	0	0	0	0	1090,909091
X6	0,5455	0,7273	0	0	0	1	0	0	-1	9,09E-05	790,9090909

Однако решение данной симплекс-таблицы не удовлетворяет условию, то есть условие о выпуске седанов, пикапов и спортивных автомобилей, так как X₁, X₂= 0, а необходимо выпустить не менее 100, 200 автомобилей соответственно.

Преобразуем таблицу 1.3. Выбирается переменная для включения в базис: это переменная X₁, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.

Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 100/1=100, 1091/0,5455=2000, 791/0,5455=1450. Минимальное симплексное отношение соответствует переменной X₇; значит, эта переменная исключается из базиса.

В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 1.4).

Базис	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Решение
-E	0	-2,455	0	-1,09	0	0	1,091	0	0	-0,002182	-26072,72727
-W	0	-1	0	0	1	0	0	0	1	1	-200
X1	1	0	0	-1	0	0	1	0	0	0	100
X8	0	1	0	0	-1	0	0	1	0	0	200
X3	0	0,7273	1	0,55	0	0	-0,55	0	0	0	1036,363636
X6	0	0,7273	0	0,55	0	1	-0,55	0	-1	0	736,3636364

Однако решение данной симплекс-таблицы не удовлетворяет условию, то есть условие о выпуске седанов, пикапов и спортивных автомобилей, так как X₂= 0, а необходимо выпустить не менее 200 автомобилей соответственно.

Преобразуем таблицу 1.4. Выбирается переменная для включения в базис: это переменная X₂, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.

Для определения переменной, исключаемой из базиса, найдем симплексные отношения: 200/1=200, 1036/0,7273=1424, 736/0,7273=1012. Минимальное симплексное отношение соответствует переменной X₈; значит, эта переменная исключается из базиса.

В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 1.5).

таблица 1.5

Базис	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	Решение
-E	0	0	0	-1,09	-2,45	0	1,091	2,45	0	-0,002182	-25581,81818
-W	0	0	0	0	0	0	0	1	1	1	0
X1	1	0	0	-1	0	0	1	0	0	0	100
X2	0	1	0	0	-1	0	0	1	0	0	200
X3	0	0	1	0,55	0,727	0	-0,55	-0,7	0	0	890,9090909
X6	0	0	0	0,55	0,727	1	-0,55	-0,7	-1	0	590,9090909

Как видно из таблицы 1.5, искусственная целевая функция равна нулю и все искусственные переменные исключены из базиса. Получено допустимое решение. В том, что это решение допустимое можно убедиться путем подстановки полученных переменных (X₁ = 100, X₂ = 200, X₃ = 37) в математическую модель. Таким образом, первый этап двухэтапного метода завершен. Искусственная целевая функция и искусственные переменные исключаются из симплекс-таблицы.

таблица 1.6

Базис	X1	X2	X3	X4	X5	X6	Решение
-E	0	0	0	-1,09	-2,45	0	-25581,81818
X1	1	0	0	-1	0	0	100
X2	0	1	0	0	-1	0	200
X3	0	0	1	0,55	0,727	0	890,9090909
X6	0	0	0	0,55	0,727	1	590,9090909

Второй этап.

Преобразуем таблицу 1.6. Выбирается переменная для включения в базис: это переменная X₅, так как ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции.

Для определения переменной, исключаемой из базиса, найдем симплексные отношения. Минимальное симплексное отношение соответствует переменной X₆, значит эта переменная исключается из базиса.

В результате преобразований по правилам симплекс-метода будет получена следующая симплекс-таблица (таблица 1.7).

таблица 1.7

Базис	X1	X2	X3	X4	X5	X6	Решение
-E	0	0	0	0,75	0	3,38	-23587,5
X1	1	0	0	-1	0	0	100
X2	0	1	0	0,75	0	1,38	1012,5
X3	0	0	1	0	0	-1	300
X5	0	0	0	0,75	1	1,38	812,5

Получено оптимальное решение (признак его оптимальности – отсутствие отрицательных коэффициентов в строке целевой функции). Основные переменные задачи приняли следующие значения: X₁ = 100 ед., X₂ = 1012,5 ед. и X₃ = 300 ед. Это означает, что необходимо выпустить 100 автомобиля класса седан, 1012,5 автомобилей пикап и 300 автомобилей спортивного класса. Значение целевой функции Е = 23587,5 показывает, что срок окупаемости затрат, необходимых для запуска автомобилей в производство составит 23587,5час.

Переменные не приняли целочисленные значения, поэтому будем использовать метод ветвей и границ. В результате его использования было получено следующее оптимальное решение:

таблица 1.8

Минимум целевой функции равен 23589
Переменная	X1	X2	X3	X4	X5	X6
Значение	102	1011	300	2	811	0

Получено оптимальное целочисленное решение. Основные переменные задачи приняли следующие значения: X₁ = 102 ед., X₂ = 1011 ед. и X₃ = 300 ед. Это означает, что необходимо выпустить 102 автомобиля класса седан, 1011 автомобилей пикап и 300 автомобилей спортивного класса. Значение целевой функции Е = 23589 показывает, что срок окупаемости затрат, необходимых для запуска автомобилей в производство составит 23589 час.

Избыточная переменная X₄ = 2 означает, что автомобилей класса седан было произведено на 2 ед. больше минимально необходимого количества.

Избыточная переменная X₅ = 812,5 означает, что автомобилей класса пикап было произведено на 811 ед. больше минимально необходимого количества.

Избыточная переменная X₆ = 0 означает, что автомобилей спортивного класса было произведено минимальное необходимое количество.

Рабочий лист с результатами решения задачи с использованием табличного процессора Excel приведен в приложении Б.