Глава 6. Решение задач линейного программирования в MathCAD

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

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

В системе MathCAD для поиска значений переменных , при которых некоторая функция принимает максимальное или минимальное значение, используются функции и . Эти функции возвращают массив неизвестных, при котором заданная функция принимает максимальное или минимальное значение соответственно.

Данные функции используются в составе блока Given, внутри которого могут задаваться различные ограничения в виде равенств и неравенств. Перед данным блоком решения необходимо задать начальные значения искомых переменных. Чем они ближе к верному решению, тем быстрее будет получен искомый результат.

6.1. Задача планирования производства

Предприятие выпускает n видов продукции (P₁, P₂, …, P_n) используя для производства m видов ресурсов (S₁, S₂, …, S_m). Известны данные о нормах расхода ресурсов на единицу продукции каждого вида и их запасах на предприятии, т.е.: – норма расхода ресурса S_i для производства единицы продукции P_j; – запас ресурса S_i на предприятии.

Цена единицы продукции P_j составляет .

Необходимо составить такой план производства продукции, при котором выручка от ее реализации была бы максимальной.

Обозначим через – объем продукции P_j, запланированный к производству – искомые величины. Тогда математическая модель данной задачи будет иметь следующий вид:

(6.1)

(6.2)

(6.3)

Полученная задача, является задачей линейного программирования, записанной в стандартной форме. Для удобства задачу (6.1)–(6.3) можно представить в компактной форме:

(6.4)

(6.5)

(6.6)

В итоге математическая модель задачи планирования производства может быть сформулирована следующим образом: составить такой план производства продукции X =(x₁, x₂, …, x_n), удовлетворяющий системе ограничений (6.4), условию (6.5), при котором целевая функция (6.6) принимает наибольшее значение.

Пример 6.1. Фирма выпускает изделия четырех типов. На изготовление изделий расходуются основные четыре группы ресурсов: материалы (S₁), полуфабрикаты (S₂), энергия (S₃), труд (S₄). Исходные данные приведены в нижеследующей таблице.

Таблица 6.1