ЛЕКЦИЯ № 3

Пример. Составить математическое описание следующей задачи об оптимальном составе сплава и представить полученную задачу линейного программирования в каноническом виде.

Для приготовления b₀ кг сплава с заданными свойствами используют вещества А_j, j = 1`,n. В x кг вещества А<sub>j</sub> содержится а<sub>ij</sub>х кг химического элемента В<sub>i</sub>, i = 1`,m. Содержание элемента В_i в сплаве должно заключиться в пределах от b_i до b_i кг. Стоимость одного кг вещества А_j составляет С_j руб. Требуется определить такой состав для приготовления сплава, при котором общая стоимость израсходованных веществ минимальна.

Решение.

Обозначим х_j количество кг вещества А_j, используемое для приготовления сплава (очевидно х_j ³ 0, j = 1`,n). Тогда содержание элемента В_i в сплаве составит кг, а стоимость израсходованных веществ будет равна руб.

Поэтому с учетом ограничений на содержание элементов В_i в сплаве, для величин х_j получим следующие неравенства

Кроме того, количество сплава должно составлять b₀ кг, поэтому

Таким образом математическое описание задачи об оптимальном составе сплава принимает вид

(6)

(7)

(8)

(9)

Запишем эту задачу линейного программирования в каноническом виде.

Среди ограничений (7) – (9) на переменные х_j содержится 2m неравенств (7), (8). Для преобразования их в ограничения-равенства введём 2m дополнительных неотрицательных переменных х_n+i и х_n+m+i, i = 1,m.

Прибавив переменные х_n+i к левым частям соответствующих неравенств (7) и вычтя переменные х_n+m+i из левых частей неравенств (8), получим задачу линейного программирования в каноническом виде.