Глава 6. Решение задач линейного программирования в MathCAD
Линейное программирование является одним из разделов математического программирования – дисциплины, занимающейся изучением экстремальных задач и разработкой методов их решения.
В общем виде постановка экстремальной задачи математического программирования состоит в определении максимального или минимального значения целевой функции при условиях-ограничениях , где f и gi – заданные функции, а bi – заданные постоянные величины. При этом условия-ограничения определяют множество допустимых решений (проектных параметров) .
В системе MathCAD для поиска значений переменных , при которых некоторая функция принимает максимальное или минимальное значение, используются функции и . Эти функции возвращают массив неизвестных, при котором заданная функция принимает максимальное или минимальное значение соответственно.
Данные функции используются в составе блока Given, внутри которого могут задаваться различные ограничения в виде равенств и неравенств. Перед данным блоком решения необходимо задать начальные значения искомых переменных. Чем они ближе к верному решению, тем быстрее будет получен искомый результат.
6.1. Задача планирования производства
Предприятие выпускает n видов продукции (P1, P2, …, Pn) используя для производства m видов ресурсов (S1, S2, …, Sm). Известны данные о нормах расхода ресурсов на единицу продукции каждого вида и их запасах на предприятии, т.е.: – норма расхода ресурса Si для производства единицы продукции Pj; – запас ресурса Si на предприятии.
Цена единицы продукции Pj составляет .
Необходимо составить такой план производства продукции, при котором выручка от ее реализации была бы максимальной.
Обозначим через – объем продукции Pj, запланированный к производству – искомые величины. Тогда математическая модель данной задачи будет иметь следующий вид:
(6.1)
(6.1)
(6.2)
(6.3)
Полученная задача, является задачей линейного программирования, записанной в стандартной форме. Для удобства задачу (6.1)–(6.3) можно представить в компактной форме:
(6.4)
(6.5)
(6.6)
В итоге математическая модель задачи планирования производства может быть сформулирована следующим образом: составить такой план производства продукции X=(x1, x2, …, xn), удовлетворяющий системе ограничений (6.4), условию (6.5), при котором целевая функция (6.6) принимает наибольшее значение.
Пример 6.1. Фирма выпускает изделия четырех типов. На изготовление изделий расходуются основные четыре группы ресурсов: материалы (S1), полуфабрикаты (S2), энергия (S3), труд (S4). Исходные данные приведены в нижеследующей таблице.
Таблица 6.1