Реферат: Линейное программирование постановка задач и графическое решение

х₁ 0, х₂ 0.

Если корм 1 не используется в рационе, то х₁ =0; в противном случае x₁ 0. Аналогично имеем х₂ 0. То есть должно выполняться условие неотрицательности переменных: х₁ 0, х₂ 0.

Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х₁ + 6х₂ (коп.)

Требуется найти такие х₁ и х₂ , при которых функция Z принимает минимальное. Таким образом, необходимо найти минимальное значение линейной функции Z = 4х₁ + 6х₂ при ограничениях

3х₁ + х₂ 9

х₁ + 2х₂ 8

х₁ + 6х₂ 12

х₁ 0, х₂ 0.

Построим многоугольник решений (рис. 2.4). Для этого в системе координат х₁ Ох₂ на плоскости изобразим граничные прямые

3х₁ + х₂ = 9 (L₁ )

х₁ + 2х₂ = 8 (L₂ )

х₁ + 6х₂ = 12 (L₃ )

х₁ = 0, х₂ = 0.

Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство (эти полуплоскости на рис. 2.4 показаны стрелками). В результате получим неограниченную многоугольную область с угловыми точками А, В, С, D.

Для построения прямой 4х₁ + 6х₂ = 0 строим радиус-вектор N = (4;6) и через точку O проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из риc. 2.4 следует, она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точе В. Если прямую перемещать дальше в направлении вектора N, то значения линейной функции на многограннике решений возрастут, значит, в точке В линейная функция Z принимает минимальное значение.

Точка В лежит на пересечении прямых L₁ и L₂ . Для определения ее координат решим систему уравнений

3x₁ + х₂ = 9

х₁ + 2х₂ = 8

Имеем: х₁ = 2; х₂ = 3. Подставляя значения х₁ и х₂ в линейную функцию, получаем Z_min = 4 2 + 6 3 = 26.

Таким образом, для того, чтобы обеспечить минимум затрат (26 коп. в день), необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2.

2.2. Обобщение графического метода решения задач линейного программирования.

Вообще, с помощью графического метода может быть ре-шена задача линейного программирования, система ограниче-ний которой содержит n неизвестных и m линейно независи-мых уравнений, если N и M связаны соотношением N – M =2.

Действительно, пусть поставлена задача линейного программирования.

Найти минимальное значение линейной функции Z= С₁ х₁ +С₂ х₂ +... +С_N x_N при ограничениях

a₁₁ x₁ + a₂₂ x₂ + ...+ a_1N Х_N = b₁

(2.3) a₂₁ x₁ + a₂₂ x₂ + ...+ a_2N Х_N = b₂

. . . . . . . . . . . . . . .

a_М1 x₁ + a_М2 x₂ + ...+ a_МN Х_N = b_М