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

Задача о раскрое материалов. Пусть поступает в раскрой m различных материалов. Требуется изготовить из них k разных комплектующих изделий (комплектов) в количествах, пропорциональных величинам b₁, b₂, . , b_k (условия комплектности). Пусть каждую единицу j-го материала j=1, ., m можно раскроить n различными способами, так что при использовании i-го способа раскроя, i=1, ., n получим а_ij единиц k-го изделия. Нужно определить такой план раскроя материалов, обеспечивающий максимальное количество комплектов, если имеющийся запас j-го материала составляет а_j единиц.
Обозначим через x_ij количество единиц j-го материала, раскраиваемых i-м способом, а через x-общее количество изготавливаемых комплектов.
Математическая модель этой задачи имеет такой вид:

(3.8)

при условиях

(3.9)

(3.10)

Условие (3.9) означает ограничение на запас j-го материала, а (3.10) - условие комплектности.
Оптимальные балансовые модели. Рассмотрим n-отраслевую балансовую модель с постоянными технологическими коэффициентами, задаваемыми матрицей затрат A=||a_ij||, где a_ij затраты продуктов i-й отрасли на производство единицы продукции j-й отрасли. Производственные мощности i-й отрасли ограничивают ее валовой выпуск величиной d_i (i = 1, ...,n), и пусть цена конечного продукта i-й отрасли составляет c_i единиц.
Нужно определить оптимальный валовой выпуск продукции каждой отрасли, при котором будет достигнут максимальный суммарный выпуск конечного продукта в денежном выражении.
Обозначим вектор валовой продукции всех отраслей через x=[x1,.,xn], а вектор конечного продукта y=[y1,.,yn]. Тогда y_i - объем продукции i-й отрасли, идущего на накопление.
Между векторами x и y существует следующая связь:
x = Ax+y,
где Ax - продукт, расходуемый на потребление. Отсюда
y=x [E-А], x=[E-A]^-1y
Математическая модель этой задачи имеет вид
максимизировать c^Ty
при условиях

Кроме того, в этой задаче можно дополнительно использовать такие, например, ограничения на конечные продукты:
а) y1:y2:.:yn=b1:b2:.:bn-условие комплектности;
б) - условие ограниченности выпуска конечного продукта.