Задача №1
Предприятие выпускает продукцию трех видов. На изготовление каждого i -ого вида продукции затрачивается три различных видов ресурсов (j): энергетические, финансовые и сырьевые. Причем на каждый вид продукции затрачивается разное количество каждого ресурса (aji). Прибыль от реализации каждого i -ого изделия различна (zi). Определить максимальную прибыль предприятия исходя из условий ограниченности каждого вида ресурса (bj) и принимая во внимание тот факт, что предприятие должно выпустить минимальное количество всех видов изделий (b 4).
Алгоритм составления математической модели оптимизационной задачи
1) Составление целевой функции.
Так как по условию задачи необходимо найти максимальную прибыль предприятия, то этот экономический критерий необходимо выразить целевой функцией. Так как на предприятии, исходя из условия задачи, выпускается три вида продукции и известна стоимость каждого вида продукции, то обозначив количество выпускаемой продукции каждого вида через x 1, x 2, x 3 и умножив это количество на стоимость каждого вида продукции z 1, z 2, z 3 получим прибыль от реализации каждого изделия. При этом сумма прибыли от реализации каждого изделия должна стремиться к максимальному значению. Поэтому целевая функция будет иметь следующий вид:
2) Составление ограничений.
По условию задачи известно, что на каждый вид продукции затрачивается три вида ресурсов. На примере первого ресурса, энергетического, на каждый вид продукции затрачивается a 11, a 12, a 13. Суммарное количество затрат энергетического ресурса на каждый вид продукции составит: 
единиц энергии. При этом данный вид ресурса ограничен на предприятии количеством b 1. Таким образом, моет быть введено ограничение по энергетическому ресурсу которое выглядит следующим образом:
Аналогично ограничения должны быть составлены для каждого из ресурсов.
Исходя из условия об ограничении минимального количества выпускаемой продукции (b 4) должно быть введено дополнительное ограничение имеющее вид:
При составлении ограничений должен быть учтен тот факт, что количество выпускаемой продукции каждого вида не может быть отрицательным.
Полученные в п.1 и п.2 выражения представляют собой математическую модель поставленной оптимизационной задачи. Так как эти выражения являются линейно зависимыми, то данная оптимизационная задача относится к классу линейных задач и может быть решена методами линейного программирования (графическим методом, алгебраическим преобразованием системы линейных уравнений и симплекс-методом).
Алгоритм решения задачи 1 ЛП (линейного программирования симплекс-методом)
1. Необходимо выполнить разделение переменных на свободные и базисные. Для этого преобразовать составленную систему ограничений по количеству ресурсов к виду:
2. Записать полученную систему ограничений и целевую функцию в виде таблицы:
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x7 | b |
| a 11 | a 12 | a 13 | b1 | ||||
| a 21 | a 22 | a 23 | b2 | ||||
| a 31 | a32 | a 33 | b3 | ||||
| a 41 | a 42 | a 43 | b5 | ||||
| z 1 | z 2 | z 3 | -Z |
3. Записать исходное решение, в котором свободные переменные равны нулю, базисные переменные равны свободным членам ограничений, значение целевой функции равно нулю.
4. Просмотреть столбец b (свободных членов). Если выполняется условие 
, то решение является допустимым, тогда переходим к п.7 алгоритма. Если есть свободные члены удовлетворяющие условию 
, то выбирается член с максимальным значением и строка содержащая этот член становится разрешающей.
5. Просмотреть коэффициенты aji разрешающей строки. Если все коэффициенты данной строки положительные, то задача не имеет решения. Если среди коэффициентов aji разрешающей строки есть отрицательные, то выбирается наибольший из этих коэффициентов и столбец содержащий выбранный коэффициент становится разрешающим.
6. Выполнить пересчет всех коэффициентов таблицы, включая значение целевой функции, которое имеет противоположный знак. Перейти к п.4.
7. Просмотреть коэффициенты zi строки целевой функции. Если все коэффициенты удовлетворяют условию 
, то текущее решение будет оптимальным. Вычисления заканчиваются.
8. Если в строке целевой функции есть коэффициенты удовлетворяющие условию 
, то необходимо выбрать наибольший из них и столбец содержащий этот коэффициент становится разрешающим. Выполняется вычисление отношений свободных членов bj к положительным коэффициентам aji разрешающего столбца. Строка, отвечающая минимальному из этих отношений будет разрешающей.
9. Выполнить пересчет всех коэффициентов таблицы и перейти к п.7.
Пример решения задачи 1
Исходные данные:
Прибыль от реализации одного изделия:
Нормы расхода энергии на одно изделие:
Нормы расхода финансовых средств на одно изделие:
Нормы расхода сырья на одно изделие:
Наличие на предприятии энергетических, финансовых и сырьевых ресурсов:
Минимальное количество изделий которое предприятие должно выпустить:
Решение.
Целевая функция имеет следующий вид:
.(1)
Система ограничений в соответствии с исходными данными запишется в виде:
(2)
Согласно алгоритму (п.1) решения задачи введем дополнительные переменные x 4, x 5, x 6 и x 7 и перейдем от ограничений-неравенств к равенствам:
(3)
Граничные условия имеют вид:
(4)
Для получения исходного решения удобно принять в качестве базисных переменные 
Остальные переменные 
- свободные. Запишем систему ограничений и целевую функцию в таблицу 1.
Таблица 1
| № строки | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | b |
| 5,5 | ||||||||
| -1 | -1 | -1 | -15 | |||||
| -Z=0 |
Исходное решение:
Свободные переменные: x 1= x 2= x 3=0;
Базисные переменные: x 4=50, x 5=100, x 6=150, x 7=-15;
Значение целевой функции: Z =0.
В полученном исходном решение переменная x 7 имеет отрицательное значение -15. При этом граничные условия (4) не выполняются. Полученное исходное решение является не допустимым.
Примем строку №4 в таблице 1, содержащую значение -15, в качестве разрешающей. Базисную переменную x 7 из строки №4 необходимо перевести в разряд свободных.
Так как в выбранной строке №4 все члены равны -1, то можем выбрать любой из этих коэффициентов. Выберем значение -1 для переменной x 3 и этот столбец примем в качестве разрешающего. Переведем свободную переменную x 3 в базис. Выполним пересчет всех коэффициентов таблицы 1.
Все коэффициенты, не принадлежащие разрешающей строке и разрешающему столбцу, пересчитаем по выражению:
(5)
где 
- коэффициент, лежащий на пересечении i- й строки и j- го столбца;
- новое пересчитанное значение коэффициента ;
- разрешающий коэффициент, который мы выбрали равным -1;
- коэффициент, лежащий на пересечении i- й строки и разрешающего столбца;
- коэффициент, лежащий на пересечении разрешающей строки и j- го столбца.
Затем все коэффициенты разрешающей строки делятся на разрешающий коэффициент . При этом разрешающий коэффициент становится равным =1.
Все коэффициенты разрешающего столбца, кроме разрешающего коэффициента, заменяются нулями.
Выполнив все эти действия получим таблицу 2 которая отвечает новому решению.
| № строки | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | b |
| 1 | -1 | -1 | ||||||
| 2 | 1,5 | |||||||
| 3 | -4 | -2 | ||||||
| 4 | -1 | |||||||
| 5 | -4 | -1 | -Z=-180 |
Таблица 2
В полученном новом решении имеем:
Свободные переменные: x 1= x 2=0, x 7=0;
Базисные переменные: x 3=15, x 4=5, x 5=40, x 6=30;
Значение целевой функции: Z =180.
Все переменные неотрицательные, следовательно граничные условия (4) выполняются и полученное решение считается допустимым.
Необходимо выполнить проверку полученного решения на оптимальность. Для этого просмотрим коэффициенты строки целевой функции (строка №5 таблицы 2). В этой строке имеем один положительный коэффициент целевой функции равный 12, следовательно мы можем увеличить целевую функцию. Примем столбец №7 таблицы 2 в качестве разрешающего и свободную переменную x 7 переведем в базис.
Вычислим положительные отношения свободных членов к коэффициентам разрешающего столбца: 5/3=1,67, 40/4=10, 30/8=3,75. Первую строку, отвечающую минимальному из этих отношений примем как разрешающую. Базисную переменную x 4, отвечающую разрешающей строке, переведем в разряд свободных. Разрешающий коэффициент выделен в таблице 2 зеленым цветом.
Выполним пересчет всех коэффициентов таблица 2 и получим таблицу 3, которая отвечает новому допустимому решению.
Таблица 3
| № строки | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | b |
| 1 | -0,33 | -0,33 | 0,33 | 1,67 | ||||
| 2 | 3,33 | 2,83 | -1,33 | 33,3 | ||||
| 3 | -1,33 | 0,67 | -2,67 | 16,67 | ||||
| 4 | 0,67 | 0,67 | 0,33 | 16,67 | ||||
| 5 | -4 | -Z=-200 |
В новом допустимом решении имеем:
Свободные переменные: x 1= x 2=0, x 4=0;
Базисные переменные: x 3=16,67, x 5=33,33, x 6=16,67, x 7=1,67;
Значение целевой функции: Z =200.
В строке целевой функции таблицы 3 имеем положительный коэффициент, равный 3. Поэтому полученное решение не является оптимальным. Принимаем второй столбец в качестве разрешающего и свободную переменную x 2 переводим в базис.
Для положительных коэффициентов разрешающего столбца вычисляем положительные отношения свободных членов к коэффициентам разрешающего столбца: 33,33/2,83=11,78, 16,67/0,67=25, 16,67/0,67=25. Вторую строку, которая отвечает минимальным из этих отношений примем в качестве разрешающей. Базисную переменную x 5 будем переводить в разряд свободных. Разрешающий коэффициент в таблице 3 выделен желтым цветом.
Выполним пересчет всех коэффициентов и получим таблицу 4.
| № строки | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | b |
| 1 | 0,06 | 0,17 | 0,12 | 5,59 | ||||
| 2 | 1,18 | -0,47 | 0,35 | 11,76 | ||||
| 3 | 2,12 | -2,36 | 8,82 | |||||
| 4 | -0,12 | 0,64 | -0,24 | 8,82 | ||||
| 5 | -3,53 | -2,59 | -1,06 | -Z=-235,29 |
В новом допустимом решении имеем:
Свободные переменные: x 1= x 4=0, x 5=0;
Базисные переменные: x 2=11,76, x 3=8,82, x 6=8,82, x 7=5,59;
Значение целевой функции: Z =235,29.
Полученное решение является оптимальным, так как строка целевой функции не содержит положительных значений. Максимальная прибыль Z=235,29 y.e.
Все ограничения и граничные условия задачи выполняются.
Так как количество изделий не может быть дробным числом, выполним округление до ближайшего целого.
Ответ: Максимальная прибыль предприятия Z=235,29 y.e., изделия первого вида выпускать не целесообразно, изделия второго вида необходимо выпустить в количестве 12 единиц, а третьего вида в количестве 9 единиц.