Оптимальное распределение неоднородных ресурсов
Постановка задач
^ процессе производства постоянно возникают задачи определения оптимального плана производства продукции при наличии определенных ре-Ьурсов (сырья, полуфабрикатов, оборудования, финансов, рабочей силы 1 др.) или проблемы оптимизации распределения неоднородных ресурсов ^производстве. Рассмотрим несколько возможных постановок таких задач. 1 Постановка задачи А. Для изготовления п видов изделий И,, Иу ..., И^ Необходимы ресурсы m видов: трудовые, материальные, финансовые и др. Известно необходимое количество отдельного i-го ресурса для изготовления каждого j-го изделия. Назовем эту величину нормой расхода с^.. Пусть Определено количество каждого вида ресурса, которым предприятие располагает в данный момент, - а,. Известна прибыль Ц, получаемая предприятием от изготовления каждого j-го изделия. Требуется определить, какие Изделия и в каком количестве должно изготавливать предприятие, чтобы Обеспечить получение максимальной прибыли. Необходимая исходная ^информация представлена в табл. 3.11.
Таблица 3.11
Используемые ресурсы a, | Изгото&ли6аемые изделия | Наличие ресурсоб a; | |||
И, | И2 | Из | И« | ||
Трудобые | 3 | 5 | 2 | 7 | 15 |
Материальные | 4 | 5 | 3 | 5 | - 9 |
Финансобые | 5 | 6 | 4 | 8 | 30 |
Прибыль rij | 40 | 50 | 30 | 20 |
Постановка задачи В. Пусть в распоряжении завода железобетонных изделий (ЖБИ) имеется m видов сырья (песок, щебень, цемент) в объемах а. Требуется произвести продукцию п видов. Дана технологическая норма с потребления отдельного i-го вида сырья для изготовления единицы продукции каждого j-го вида. Известна прибыль П., получаемая от выпуска единицы продукции j-го вида. Требуется определить, какую продукцию и в каком количестве должен производить завод ЖБИ, чтобы получить максимальную прибыль. Исходные данные представлены в табл. 3.12.
Таблица 3.12
Используемые ресурсы а; | Изготаблибаемые изделия | Наличие ресурсоб a, | |||
И, | И; | Из | И4 | ||
Песок | 3 | 5 | 2 | 7 | 15 |
Щебень | 4 | 3 | 3 | 5 | 9 |
Цемент | 5 | 6 | 4 | 8 | 30 |
Прибыль hj | 40 | 50 | 30 | 20 |
Постановка задачи С. Пусть на предприятии после модернизации производства появился свободный ресурс времени. Предлагается организовать производство новых изделий нескольких наименований. Известно время, требуемое на изготовление отдельного изделия на каждом оборудовании, свободные резервы времени на каждой машине, а также прибыль, получаемая от выпуска каждого изделия. Требуется определить, какие изделия и в каком количестве целесообразно производить на предприятии, чтобы получить максимальную прибыль.
Выявление основных особенностей, взаимосвязей и количественных закономерностей
Количество изделий j-го наименования, которое может производить предприятие, обозначим через х.. Зная количество каждого вида i-го ресурса для изготовления отдельного j-го типа изделия - норму расхода с.
и количество каждого i-го ресурса а. (табл. 3.12), можно записать следующую систему неравенств: 3^ +5х2+2х3+7^^15
4r +^x +^x +SY <9 ^•^i ^~'л^ '~>л-} ~г~>л^ —у ,
^•о) L 5х1 + 6х2 + 4х3 + 8^ < 30
i Полученную систему можно представить в виде совокупности равенств, ^сли в каждое из неравенств ввести фиктивные изделия (дополнительные беременные) \у xg, х^ при изготовлении которых используют каждый оставшийся вид ресурса. Ь В этом случае система равенств примет такой вид:
р 3^1 +5х2 +2^з +7x^ +x^ =15
I 4x^+!x^+3x^+5x^+x^=9 ^ ^ (^•^) ^ 5х1 + 6х2 + 4х3 + 8x„ + x^ = 30
1 Это преобразование необходимо для упрощения вычислительной процедуры в дальнейшем. Прибыль, получаемая от фиктивных изделий, принимается равной нулю.
• Построение математической модели. Критерий оптимизации (суммарную величину прибыли) можно тогда представить так:
; 7
y=c^]+...c. x.+...+c^x^=^cx. (3.10)
y=l
Граничные условия будут записаны следующим образом:
/ ^>0(J=U,...,7) (3.11) Совокупность системы ограничений (3.9), целевой функции (3.10) и гра-,ничных условий (3.11) образует математическую модель для нашей задачи.
{Решение задачи традиционными методами
,Алгоритм решения. Для решения данной задачи разработано много способов. Рассмотрим один из наиболее распространенных - симплекс-метод. Для его использования необходимо определить начальный базис, то есть
' такое решение, которое удовлетворяет системе равенств (3.9). В некоторых задачах базис просматривается непосредственно, но во многих его необходимо найти.
В данной задаче базис определяется легко. Для этого требуется взять m неизвестных по числу уравнений в системе (3.9), желательно наиболее редко встречающиеся в ней. В нашей совокупности уравнений (m = 3) это Ху xg, х^ которые и выражаем через оставшиеся неизвестные х, Ху Ху х^.
Систему уравнений необходимо записать в таком виде: Xj = 15- (3^1 + 5x^ + 2х3 + 7:^ ) x^ = 9- (4х1 + Зх^ + З^з + 5x^ ) П 12)
^ =х1 +6х2 +4х3 +8х4)
Переменные, находящиеся в левой части системы уравнений, называются базисными (основными), а находящиеся справа - небазисными (неосновными). Для определения значений базисных переменных Ху xg, х, необходимо приравнять к нулю небазисные х, х„ Ху х^и подставить их в систему уравнений (3.12). Полученное таким образом решение называется базисным. В нашей задаче оно будет выглядеть следующим образом:
^^1) xg) ^-у ^-jf ^-y "g> ^-])
(0, 0, 0, 0, 15, 9, 30).
После определения начального базиса можно переходить непосредственно к использованию алгоритма симплекс-метода, который содержит следующие основные этапы:
1. Заполнение исходной симплекс-таблицы. В соответствии с полученной системой уравнений и критерием оптимизации заполняем исходную симплекс-таблицу (табл. 3.13).
Таблица 3.13
Базисные переменные | Сбободмые члена | Коэффициенты при бозиснах и небазисных переменнох | ||||||
^ | Qi | Xi | х? | хз | X4 | X5 | Хб | ^7 |
^ | 15 | 3 | Г5*~! | 2 | 7 | 1 | 0 | 0 |
Хб | 9 | 4 | з | 3 | 5 | 0 | 1 | 0 |
х? | 30 | 5 | 6 | 4 | 8 | 0 | 0 | 1 |
^ | 0 | 40 | 50 | 30 | 20 | 0 | 0 | 0 |
2. Проверка базисного решения на оптимальность. Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) - последняя строка табл. 3.13. Если все коэффициенты при небазисных переменных неположительны, то исходный базис является оптимальным; в противном случае переходят к следующему этапу. В нашей задаче решение не оптимально, так как все коэффициенты целевой функции при небазисных переменных положительны.
3. Проверка задачи на наличие решения. Если при какой-либо небазисной переменной, имеющей положительный коэффициент в целевой
функции, окажется, что столбец коэффициентов при этой же переменной в системе уравнений состоит из одних неположительных чисел, то максимальное значение целевой функции стремится к бесконечности, то есть задача решений не имеет. В нашей задаче решение имеется.
4. Выбор из небазисных переменных той, которая способна при введении ее в базис увеличить значение целевой функции. Наиболее простой и чаще всего используемый способ состоит в выборе той небазисной переменной, которой соответствует наибольший положительный коэффициент в целевой функции. В нашей задаче это переменная х (наибольший положительный коэффициент равен 50). Значит, х^ необходимо ввести в базис.
5. Определение базисной переменной, которая должна быть выведена из базиса. Для всех положительных коэффициентов при вводимой в базис переменной в системе уравнений определяется отношение свободного члена уравнения к коэффициенту при вводимой в базис переменной. Для нашей задачи это будут следующие отношения: 15/5 = 3; 9/3-3; 30/6 - 5.
Минимальное из полученных отношений указывает строку, базисную переменную, которая должна быть выведена из базиса. При наличии нескольких одинаковых отношений берется любое. В нашей задаче выведем из базиса переменную х,.
6. Представление новой базисной переменной через небазисные. Строится новая симплекс-таблица (табл. 3.14). Отмечается звездочкой строка и столбец в предыдущей симплекс-таблице (табл. 3.13), соответственно для выводимой из базиса и для вводимой в него переменной. Коэффициент, находящийся на пересечении строки и столбца, отмеченных звездочками, называется разрешающим и помечается звездочкой (табл. 3.13). Все коэффициенты строки, отмеченной звездочкой, делятся на разрешающий элемент, а результаты расчета заносятся в новую симплекс-таблицу. В нашей задаче на первой итерации разрешающий элемент равен 5 (табл. 3.13). Результаты деления каждого элемента строки, отмеченной звездочкой, на разрешающий коэффициент заносятся в строку 1 новой таблицы (табл. 3.14).
7. Представление остальных базисных переменных и целевой функции через новый набор небазисных переменных. Для этого коэффициенты в новой таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце при новой базисной переменной в новой таблице появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов
второй строки в новой табл. 3.14 умножаем коэффициенты при новой базисной переменной х^ (табл. 3.14) на число -3, складываем с соответствующими коэффициентами второй строки предыдущей симплекс-таблицы (табл. 3.13) и результаты расчета заносим во вторую строку новой таблицы (табл. 3.14).
Таблица 3.14
Базисные переменные | СЬободные члены | Коэффициенты при-базиснах и небазисных переменных | ||||||
х- | а; | Xl | X2 | ^ | X4 | "5 | Хб | *7 |
Х2 | 3 | 3/5 | 1 | 2/5 | 7/5 | 1/5 | 0 | 0 |
"б | 0 | 11/5 | 0 | 9/5 | 4/5 | -3/5 | 1 | 0 |
Х7 | 12 | 7/5 | 0 | 8/5 | -2/5 | -6/5 | 0 | 1 |
П, | -150 | 10 | 0 | 10 | -50 | -10 | 0 | 0 |
Аналогичные преобразования проводим и для других строк. После этого выполняем новую итерацию. Цикл расчета начинается с этапа 2 и проводится до тех пор, пока не будет найдено оптимальное решение. Поскольку в последней строке табл. 3.14 в целевой функции не все коэффициенты при небазисных переменных положительны, то решение не оптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица (табл. 3.15). В качестве вводимой в базис небазисной переменной берем х^ (можно х^) как имеющую наибольший положительный коэффициент. Отмечаем звездочкой столбец Ху В качестве выводимой из базиса переменной берем xg, так как для нее частное от деления свободного члена на соответствующий коэффициент минимально. Разрешающий множитель равен 9/5. Результаты расчета представлены в табл. 3.15.
Таблица 3.15
Базисные переменные | СЬободные члены | Коэффициенты при базисных и небазисных переменных | ||||||
^i | Oi | xi | ^2 | ^ | Х4 | X5 | Хб | X7 |
Х2 | 3 | 1/9 | 1 | 0 | 1/9 | 1/3 | -2/9 | 0 |
^ | 0 | 11/9 | 0 | 1 | 4/9 | -3/9 | 5/9 | 0 |
Я? | 12 | -5/9 | 0 | 0 | -10/9 | -2/3 | -8/9 | 1 |
^ | -150 | -20/9 | 0 | 0 | -490/9 | -20/3 | -50/9 | 0 |
Последняя строка таблицы не содержит положительных коэффициентов при небазисных переменных. Анализируя полученное решение, видим, что оно оптимально и выглядит так:
(^i, Ху Ху х^, xg, xg, х^) (О, 3, 0, 0, 0, 0, 12).
Из полученного решения видно, что предприятию наиболее выгодно L. изготовление только изделия И^ производство которого обеспечит ' ему максимальную прибыль в размере Ушах == 150. При этом матери-^ альные и трудовые ресурсы будут задействованы полностью, а финан-, совые - недоиспользованы на 12 единиц.
решение задачи с использованием системы Mathcad
введем сначала поясняющий текст в рабочем листе. Для этого разместим ^Урсор (визир - красный крестик) в месте ввода текста. Затем выберем ^щелчком мыши или с помощью клавиатуры) пункт Insert (Вставка) главного меню Mathcad. В появившемся падающем меню щелкнем по пункту lext Region (Текстовая область) или в месте расположения курсора наймем клавишу с двойной кавычкой (команда для ввода текста). В обоих ^лучаях появится шаблон, указывающий место и начало ввода текста, пос-Це чего можно приступить к этой операции. Текстовая область будет автоматически увеличиваться по мере ввода текста. По окончании этого действия выведем курсор за рамки текстовой области. , Далее введем критерий оптимизации - целевую функцию. Для этого разместим курсор (визир - красный крестик) в месте ввода математического выражения, затем, используя соответствующие клавиши, начнем ввод, в первую очередь - имени критерия оптимизации с аргументами ^скобках через запятые. Затем нажмем комбинацию Shift+: (двоеточие) ^ля ввода знака присваивания := (двоеточие и знак «равно»). На месте Правой метки помещаем все выражение критерия оптимизации. Аналогично вводятся начальные приближения. !Для решения задачи используем блок функций Given...Maximize. Для ^гого необходимо:
' Q ввести, если требуется, комментарии, ввод которых начинается
с нажатия клавиши с двойной кавычкой; Q ввести ключевое слово Given;
' Q ввести систему ограничений с использованием жирного знака равенства, нажав комбинацию клавиш Ctrl+=; Q ввести граничные значения (рис. 3.7);
Q ввести вектор-столбец искомых параметров, используя диалоговое окно Insert Matrix (Вставить матрицу) и комбинацию Ctrl+M (рис. 3.7). В диалоговом окне число строк (Rows) - элементоб вектора столбца - должно быть равно 7, а число столбцов (Columns) - 1; Q ввести знак присваивания, нажав комбинацию клавиш Shift+: (двоеточие);
Иис. 3./. Оптимизация распределения неоднородных ресурсов в среде Mathcad
а ввести функцию Minimize с искомыми параметрами, используя диалоговое окно Insert Function (Вставить функцию) и комбинацию Ctrl+E; а ввести вектор-столбец искомых параметров и знак «равно». На рис. 3.7 показан процесс оптимизации распределения неоднородных ресурсов с помощью Mathcad.
Оптимальное распределение неоднородных ресурсов зафиксировано в векторе (XI Х2 ХЗ...). Из полученного решения видно, что XI == О, Х2 == 3, Х4 = О, Х5 = 3.553 х 10-^ Х6 = О, Х7 = 12. Это означает, что изделия XI, ХЗ и Х4 предприятие изготавливать не должно. Ему нужно производить только второе изделие в количестве 3 единиц. Цифра в переменной Х2 определяет изделие, планируемое для изготовления. Оптимальное распределение ресурсов обеспечит получение максимальной прибыли Y, которая составит 150 единиц.
