1 Теория решения задачи

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

найти значения переменных x₁,...,x_n, доставляющие максимум (минимум) заданной функцииz=f(x₁,...,x_n) при условияхg_i(x₁,...,x_n)=b_i(i=1...m).

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

Множество точек X=(x₁,...,x_n), удовлетворяющих системе ограниченийg_i(X)=b_i(i=1...m), есть область определенияUпоставленной выше задачи.

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

В основу классификации таких задач положены особенности функций zиg_i, встречающихся в конкретных исследованиях. Различают два основных класса задач – задачи линейного и нелинейного программирования. К первым относятся те, в которых и целевая функцияz, и все функцииg_i(i=1...m) линейны относительно переменныхx_j(j=1...n), ко вторым – те, в которых присутствуют различного рода нелинейности.

2 Построение математической модели

При имеющемся количествеNбрёвен известной длины (L) необходимо составить план распила так, чтобы получить брусья заданных размеров 3,5: 4,5; 5 м. при условии условии максимального числа брусьев в заданном ассортименте.

Пусть единица i-го бревна содержитai1 единиц брусьев по 3,5;ai2 – 4,5;ai3 – 5.

Обозначим ci,I= 1,..,N, в качестве длиныi-го бревна;b1,b2,b3 – заданное количество соответственно брусьев по 3,5: 4,5; 5 метров (ассортимент).

Запишем условия задачи в виде математических формул.

1. Выберем переменные задачи:x1,x2,…,xn– количество брёвен, пригодных для распила.

2. Составим ограничения задачи: Ограничения по условиям задачи должны обеспечить распил брёвен в заданном ассортиментеb1,b2,b3 соответственно.

Так как I– е бревно возможно распилить наai1 количество брусьев по 3,5 метра, тоxi - е единицI– го бревна возможно возможно распилить наai1xi количество брусьев по 3,5 метра.

Значит, общее количество брусьев по 3,5 метров из общего числа брёвен будет равно сумме:

a11x1 + a21x2+… +an1xn≥b1;

Записывая аналогичные условия для брусьев размерами 4,5 и 5 метров, получим, включая предыдущее, три условия:

a11x1 + a21x2+… +an1xn ≥ b1;

a12x1 + a22x2+… +an2xn ≥ b2; (1)

a13x1 + a23x2+… +an3xn ≥ b3;

Нельзя забывать очевидно вытекающие из условий задачи ограничения:

X1≥0,X2≥0, …,Xn≥0. (2)

Эти ограничения означают, что отрицательное количество брёвен Xi не имеет содержательного смысла.

3. Составим целевую функцию. Так как общая длинна брёвенL=C1X1+C2X2+,…,+CnXn,необходимо минимизировать линейную функциюL.

Итак, математическая модель рассмотренной задачи о оптимизации использования брёвен имеет следующий вид:

Минимизировать L=C1X1+C2X2+,…,+CnXn,

При условиях:

a11x1 + a21x2+… +an1xn ≥ b1;

a12x1 + a22x2+… +an2xn ≥ b2; (3)

a13x1 + a23x2+… +an3xn ≥ b3;

X1≥0, X2≥0, …, Xn ≥0.

Или в матричном виде:

cx→min,(4)

Ax≥b,x≥ 0.