Программное обеспечение САПР

В качестве примера программного обеспечения САПР рассмотрим решение задач линейного и нелинейного программирования средствами программы Optimization Toolbox, входящей в программный комплекс Matlab.

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

Одной из наиболее известных задач линейного программирования является задача о пищевом рационе. Сущность задачи рассмотрим на примере.

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

Продукты	Элементы
	Белки	Углеводы	Жиры

Требуется составить пищевой рацион, обеспечивающий наличие заданных элементов (белки, углеводы, жиры), и обладающий минимальной стоимостью. Пусть , , , - количество продуктов , , , , входящих в рацион. Тогда стоимость рациона составит:

L = + + + = min.

Суммарное содержание элементов в рационе определяется неравенствами (ограничениями):

+ + + ;

+ + + ;

+ + + .

C учётом неотрицательности переменных x добавляются 4 неравенства (ограничения слева)

,

,

.

Задача линейного программирования: требуется найти значения переменных x, удовлетворяющие системе перечисленных ограничений, при которых функция цели L минимальна.

Стандартная задача, решаемая программой Optimization Toolbox, состоит в нахождении минимума целевой функции L при ограничениях типа (ограничения справа).

Пример 1. Пусть задана целевая функция L = max при наличии ограничений

3 - 7,

- 2 -1,

4 - 3,

5 + 2 14.

После приведения задачи к стандартному (для программы Optimization Toolbox) виду путём умножения функции цели и четвёртого ограничения на минус единицу, получим

L = min

3 - 7,

- 2 -1,

4 - 3,

-5 - 2 -14.

Для решения задачи используем функцию

[x, L] = linprog(c, A, b, [A1, b1, lx, rx]),

где

c – функция цели, представленная вектором коэффициентов;

A, b - система ограничений, заданная в матричном виде A*x ;

A1, b1 – параметры, которые используются, если система ограничений задана в виде

равенств A*x ;

lx, rx – параметры, обусловленные наличием ограничений слева или ограничений

справа ;

x – вектор решения, содержащий значения переменных, удовлетворяющие ограничениям и приводящие функцию цели к минимуму;

L – минимум функции цели;

Для рассматриваемого примера в рабочем окне программы Matlab выполняем действия,

приведенные ниже (поскольку в данной задаче ограничения-равенства и ограничения справа отсутствуют, их место указано пустыми массивами []).

Пример 2.

Фирмы “Лидер” и “Пионер” (далее называем их фирма 1 и фирма 2) производят стулья различных типов из общего запаса деталей. Удельная прибыль от продажи единицы продукции составляет 56$ для фирмы 1 и 40$ для фирмы 2. Для сборки стула нужны детали пяти типов: длинные винты, короткие винты, прочные сиденья, облегчённые сиденья, ножки. Запасы длинных и коротких винтов на неделю составляют 1280 и 1600 соответственно. Для производства 1 стула фирмой 1 требуется 8 длинных и 4 коротких винта, 1 прочное сиденье, 4 ножки; фирмой 2 - 4 длинных и 12 коротких винта, 1 облегчённое сиденье, 4 ножки. Запас прочных сидений на неделю составляет 140 штук, облегчённых сидений – 120 штук. Для каждого стула требуется 4 ножки. Общий запас ножек на неделю – 760 штук Требуется определить, сколько стульев в неделю должна выпускать каждая фирма для того, чтобы их суммарная прибыль была максимальной при условии, что общий объём производства обеих фирм должен быть не менее 100 единиц в неделю.

Представим исходные данные (расход каждого вида комплектующих на единицу продукции и запас каждого вида комплектующих на складе) в виде трёх таблиц:

Винты

Сиденья

Ножки

Обозначив через и количество стульев, изготовленных 1 и 2 фирмами, составим

математическое описание задачи

56 + 40 max;

8 + 4 1280 (длинные винты);

4 + 12 1600 (короткие винты);

+ 100 (объём производства);

4 + 4 760 (ножки);

140 (прочные сиденья);

120 (облегчённые сиденья);

0; 0;

После приведения математической модели к стандартному (для программы) виду, получаем систему

-56 - 40 min;

8 + 4 1280;

4 + 12 1600;

- - - 100;

4 + 4 760 (ножки);

140;

120;

0; 0;

В рабочем окне программы Matlab выполняем действия, приведенные ниже

Ответ программы:

фирма 1 должна производить 130 стульев в неделю; фирма 2 – 60 стульев в неделю.

Максимальная прибыль 9680$ в неделю.

В ответе для x получились целые числа, но дробные числа в ответе тоже были бы приемлемы, поскольку ответ содержит математическое ожидание (среднее арифметическое) недельной производительности обеих фирм.