Приложение г задачи линейного программирования

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

В общем виде формулировка задачи сводится к следующему. Найти оптимум (максимум или минимум) целевой функции

F = c₁x₁ + c₂x₂+…+ c_nx_n (Г.1)

при выполнении ограничений:

a₁₁x₁ + a₁₂x₂+…+ a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂+…+ a_2nx_n = b₂

. . . . . . . . . . . . (Г.2)

a_m1x₁ + a_m2x₂+…+ a_mnx_n = b_m ,

где коэффициенты a_ij, b_i, c_j – заданные постоянные величины, а число уравнений m меньше числа переменных n. Значение X = (x₁, х₂, … , x_n), при котором функция F имеет оптимум, называется оптимальным решением.

В большинстве задач ограничения задаются не в виде системы уравнений, а в виде системы линейных неравенств, например вида

a₁₁x₁ + a₁₂x₂+…+ a_1nx_n  b₁

a₂₁x₁ + a₂₂x₂+…+ a_2nx_n  b₂

. . . . . . . . . . . . (Г.3)

a_m1x₁ + a_m2x₂+…+ a_mnx_n  b_{m .}

Однако любую систему ограничений можно привести к системе уравнений вида (Г.2). Для этого достаточно к левой части каждого неравенства добавить какое-то неотрицательное число x_n+1, x_n+2, x_n+m - добавочную переменную, чтобы неравенства обратились в уравнения. В результате вместо системы неравенств (Г.3) получим эквивалентную систему уравнений вида

a₁₁x₁ + a₁₂x₂+…+ a_1nx_n+ x_n+1 = b₁

a₂₁x₁ + a₂₂x₂+…+ a_2nx_n + x_n+2 = b₂

. . . . . . . . . . . . (Г.4)

a_m1x₁ + a_m2x₂+…+ a_mnx_n + x_n+m = b_{m ,}

т. е. систему ограничений, аналогичную системе (Г.2).

Таким образом, как бы ни были первоначально заданы огра­ничения задачи линейного программирования, их всегда можно привести к системе линейных уравнений, используя для этой цели добавочные переменные. Число добавочных переменных меньше m и равно m-t, где t – число ограничений в виде уравнений. Отсюда следует, что формулировка задачи (Г.1) - (Г.2) является формулировкой общей задачи линейного программирования. Ниже приведены примеры двух типовых задач линейного программирования.

Задача об оптимальном использовании ресурсов. Предприятие выпускает n различных изделий, и для их производства требуется m различных видов ресурсов (сырья, вспомогательных материалов, рабочего времени и т. д.). Эти ресурсы ограничены и составляют в планируемый период соответственно b₁, b₂, ..., b_m условных единиц. Известны также технологические коэффициенты а_ij, которые указывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-гo вида (i = 1, 2,..., m; j = 1, 2, …, n). Пусть прибыль, получаемая предприятием при реализации единицы изделия j-гo вида, равна c_j. Требуется составить такой план выпуска продукции x₁, х₂, … , x_n, чтобы на ее производство хватило имеющихся в распоряжении ресурсов и при реализации которого прибыль F = c₁x₁ + c₂x₂+…+ c_nx_n была бы наибольшей. Математически эта задача сводится к поиску максимума функции F при ограничениях (Г.3).

Задача о смесях. Свойства смеси обеспечиваются наличием m различных компонентов в количествах не ниже заданных b₁, b₂, ..., b_m, а сами компоненты являются составными частями n исходных материалов. Коэффициенты а_ij показывают удельный вес i-гo компонента (i =1,…, m) в единице j-гo материала (j =1,…, n). Необходимо отыскать наиболее дешевый набор x₁, х₂, … , x_n из n исходных материалов c ценой единицы j-гo материала с_j, обеспечивающий получение смеси. Задача сводится к отысканию минимума функции F = c₁x₁ + c₂x₂+…+ c_nx_n при ограничениях, аналогичных (Г.3), но со знаком «».

Методы решения задач линейного программирования основываются на ряде положений (теорем), суть которых может быть сведена к следующему: оптимальное решение задачи линейного программирования совпадает с одной из угловых точек выпуклого множества решений для системы ограничений задачи. Общепризнанным универсальным методом решения задач линейного программирования в настоящее время является симплексный метод Данцига, алгоритм которого имеется в программном пакете MATLAB [24].

Если система ограничений задачи линейного программирования задана в виде системы линейных неравенств с двумя переменными или в виде системы линейных уравнений, в которой число переменных на два превышает число уравнений, то такие задачи могут быть решены геометрически. Геометрический метод представляет определенный интерес для выработки наглядных представлений о задачах линейного программирования.

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

Например, требуется найти максимум F = 4x₁+ 3x₂

при ограничениях x₁ + 2x₂  16

2x₁ + 3x₂  28

3x₁ + 3x₂  30

x₁  x₂

x₁  0; x₂  0

На рисунке изображена область решений системы ограничений в виде многоугольника ОАВС. Он образован прямыми линиями, соответствующими неравенствам системы ограничений, каждое из которых определяет отмеченную штриховкой полуплоскость допустимых значений переменных x₁ и x₂. Отметим, что второе неравенство системы оказалось лишним, и соответствующая прямая 2х₁ + 3х₂ = 28 не участвовала в образовании четырехугольника ОАВС. Исходная линия уровня F = 4x₁ + 3x₂ = 0 показана прямой, проходящей через начало координат и точку (-3; 4).

Двигая исходную линию уровня в направлении стрелки, можно достигнуть максимума F, расположенного в точке С. Решив совместно уравнения для 3-й и 4-й прямых системы, получим координаты точки их пересечения С (x₁ = 5; x₂ = 5). Это оптимальное решение дает F_max = 35.