- •Задача 1
- •Задача 3
- •Задача 4
- •Задача 5
- •Задача 6
- •Задача 7
- •Задача 8
- •Задача 9
- •Задача 10
- •Задача 11
- •Задача 12
- •Задача 13
- •Задача 14
- •Задача 15
- •Задача 16
- •Решение: (проверить)
- •Задача 17
- •Задача 18
- •Задача 19
- •Задача 20
- •Задача 21
- •Задача 22
- •Задача 23
- •Задача 24
- •Задача 25 (ошибка в условии)
- •Задача 28
- •Метод потенциалов
- •Задача 30
- •Задача 32
- •Задача 33
- •Решение
- •Задача 34
- •Решение
- •Решение
Задача 17
При производстве двух видов продукции и используются три вида сырья , , . Известны запасы каждого вида сырья: 40, 15 и 28. Для изготовления единицы продукции вида необходимо 3 ед. сырья , 2 ед. сырья вида и 4 ед. сырья вида . Производство единицы продукции вида требует затрат 5 ед. сырья вида , 1 ед. сырья вида и 1 ед. сырья вида . При реализации одной единицы продукции вида предприятие получает прибыль в 2 ден.ед, а при реализации одной единицы продукции вида прибыль составит 4 ден.ед. Требуется составить план выпуска продукции, при котором предприятие получит наибольшую прибыль.
РЕШЕНИЕ:
1) Составим математическую модель исходной задачи.
Представим исходные данные в виде таблицы:
Вид сырья |
Нормы расхода сырья на единицу продукции |
Запасы сырья |
|
П1 |
П2 |
||
S1 |
3 |
5 |
40 |
S2 |
2 |
1 |
15 |
S3 |
4 |
1 |
28 |
Прибыль при реализации одной единицы продукции, ден.ед. |
2 |
4 |
|
Объектом моделирования является процесс получения максимальной прибыли от реализации выпускаемой продукции, а целью – оптимизация структуры и объема производства.
Задача относится к классу оптимизационных задач. Математическая модель для задач такого класса состоит в построении целевой функции, для которой надо найти экстремум, при ограничениях.
Для решения поставленной задачи введем обозначения:
х1 – объем производства продукции вида П1;
х2 – объем производства продукции вида П2.
Общую прибыль от реализации продукции можно определить по формуле:
(ден.ед.)
Функция F называется целевой, ее следует максимизировать. Поэтому получаем:
На целевую функцию накладываются следующие ограничения:
а) объем производства продукции не может быть отрицательным:
x1 0, x2 0.
б) ограничение по запасам сырья вида S1:
;
в) ограничение по запасам сырья вида S2:
;
г) ограничение по запасам сырья вида S3:
.
Математическая модель задачи: составить оптимальный план производства продукции (х1, х2), обеспечивающий максимальную прибыль при реализации продукции:
при ограничениях:
Математическая модель исходной задачи составлена.
2) Решим исходную задачу симплексным методом.
Приведем задачу к канонической форме.
Чтобы перейти от общей формы записи ЗЛП к канонической, нужно ограничения-неравенства исходной ЗЛП преобразовать в ограничения-равенства добавлением к их левой части дополнительной неотрицательной переменной со знаком «+» в случае неравенства вида «» и со знаком «-» - в случае неравенства вида «».
В первое ограничение системы добавим переменную со знаком «+», во второе ограничение системы добавим переменную со знаком «+» и в третье ограничение системы добавим переменную со знаком «+». В результате получаем следующую систему ограничений:
Следовательно, исходная задача может быть записана в канонической форме так: найти максимум функции
при ограничениях:
В полученной системе уравнений системы ограничений имеются три базисные переменные. Решим систему уравнений относительно базисных переменных x3, x4 и x5. Запишем базисное решение в стандартной форме:
или
.
Составим симплекс-таблицу:
Базис |
Свободный член |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
40 |
3 |
5 |
1 |
0 |
0 |
x4 |
15 |
2 |
1 |
0 |
1 |
0 |
x5 |
28 |
4 |
1 |
0 |
0 |
1 |
F(X0) |
0 |
-2 |
-4 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация 1. Текущий опорный план не является оптимальным, так как в индексной строке находятся отрицательные коэффициенты.
В индексной строке F(х) выбираем максимальный отрицательный элемент. В качестве генерального столбца будет выступать x2. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:
.
Таким образом, строка х3 является генеральной. Разрешающий элемент равен РЭ = 5 и находится на пересечении генерального столбца и генеральной строки.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана, включая элементы индексной строки, определяем по правилу прямоугольника.
Элементы разрешающей строки делим на разрешающий элемент и записываем в соответствующей по номеру строке новой таблицы:
, при i = r.
Все остальные элементы новой таблицы рассчитываем по формулам:
, при i ≠ r
где - элемент новой симплекс-таблицы, aij, - элемент предыдущей симплекс-таблицы, ark - разрешающий элемент , aik - элемент разрешающего столбца, arj - элемент разрешающей строки.
Представим расчет каждого элемента в виде таблицы:
Свободный член |
x1 |
x2 |
40 / 5 |
3 / 5 |
5 / 5 |
15-(40 * 1)/5 |
2-(3 * 1)/5 |
1-(5 * 1)/5 |
28-(40 * 1)/5 |
4-(3 * 1)/5 |
1-(5 * 1)/5 |
0-(40 * (-4))/5 |
-2-(3 * (-4))/5 |
-4-(5 * (-4))/5 |
x3 |
x4 |
x5 |
1 / 5 |
0 / 5 |
0 / 5 |
0-(1 * 1)/5 |
1-(0 * 1)/5 |
0-(0 * 1)/5 |
0-(1 * 1)/5 |
0-(0 * 1)/5 |
1-(0 * 1)/5 |
0-(1 * (-4))/5 |
0-(0 * (-4))/5 |
0-(0 * (-4))/5 |
После перерасчета получаем новую таблицу:
Базис |
Свободный член |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
8 |
0,6 |
1 |
0,2 |
0 |
0 |
x4 |
7 |
1,4 |
0 |
-0,2 |
1 |
0 |
x5 |
20 |
3,4 |
0 |
-0,2 |
0 |
1 |
F(X1) |
32 |
0,4 |
0 |
0,8 |
0 |
0 |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальное решение задачи.
Таким образом, получаем:
;
.
Ответ. ; . Для получения максимальной прибыли от реализации выпускаемой продукции на предприятии необходимо производить 8 единиц продукции вида П2, а продукцию вида П1 производить не требуется. При использовании данного плана выпуска продукции предприятие получит наибольшую прибыль, которая составит 32 ден.ед.
РЕШЕНИЕ ГРАФИЧЕСКИМ СПОСОБОМ: