Линейное программирование
8.1. Определения. Примеры задач линейного программирования
Линейное программирование − математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств. Линейное программирование стало развиваться в первую очередь в связи с решением задач экономики, с поиском способов оптимального распределения и использования ресурсов. Оно послужило основой широкого использования математических методов в этой сфере. Следует подчеркнуть, что в реальных экономических задачах число независимых переменных обычно бывает очень большим (тысячи, десятки тысяч). Поэтому практическая реализация алгоритмов их решения принципиально невозможна без современной вычислительной техники. Пример 8.1 . Для изготовления трех видов сплавов A , B и C используется медь, олово и цинк. Данные о сплавах приведены в табл. 8.1. В ней же указано общее количество метала каждого типа, а так же стоимость реализации одного кг сплава каждого типа.
| Процентное содержание и общая масса компонентов | Таблица 8.1. | |||||
| Компоненты сплава | Общая масса данной | |||||
| A | B | C | компоненты сплава, т. | |||
| Медь | 20 | 10 | 30 | 120 | ||
| Олово | 10 | 80 | 60 | 280 | ||
| Цинк | 70 | 10 | 10 | 240 | ||
| Стоимость 1кг. | 10 | 14 | 12 | − | ||
Требуется определить, какое количество сплавов каждого вида следует изготовить предприятию, чтобы стоимость продукции была максимальной. □ Предположим, что будет изготовлено x 1 кг сплава A , x 2 кг сплава B и x 3 кг сплава C . Тогда для производства такого количества сплавов потребуется затратить 20 x 1 + 10 x 2 + 30 x 3 кг меди.
Так как общая масса меди не может превышать 120 т, то должно выполняться неравенство 20 x 1 + 10 x 2 + 30 x 3 ≤ 120000 . Аналогичные рассуждения относительно возможности использования олова и цинка приведут к неравенствам 10 x 1 + 80 x 2 + 60 x 3 ≤ 280000, 70 x 1 + 10 x 2 + 10 x 3 ≤ 240000. При этом, так как масса сплавов не может быть отрицательной, то
| x 1 | ≥ 0, x 2 ≥ 0, x 3 ≥ 0. | (8.1) |
| Если будет изготовлено | x 1 кг сплава A , x 2 кг сплава B | и x 3 кг сплава C , то |
стоимость продукции составит F = 10 x 1 + 14 x 2 + 12 x 3 . Таким образом, приходим к следующей математической задаче. Дана система
| 20 x | + 40 x | 2 | + 50 x | 3 | ≤ 120000 | |
| 1 | ≤ 280000 | |||||
| 10 x 1 + 80 x 2 | + 60 x 3 | (8.2) | ||||
| + 10 x 2 | + 10 x 3 | ≤ 240000 | ||||
| 70 x 1 | ||||||
из четырех линейных неравенств (8.1) − (8.2) с тремя неизвестными и линейная функция относительно этих же переменных
| F = 10 x 1 + 14 x 2 + 12 x 3 . | (8.3) |
Требуется среди всех неотрицательных решений системы неравенств (8.2) найти такое, при котором функция (8.3) принимает максимальное значение. Так как функция (8.3) линейная, а система (8.2) содержит только линейные неравенства, то задача (8.1)−(8.3) является задачей линейного программирования. ■ Пример 8.2 . Продукцией молочного завода являются молоко, кефир и сметана. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы, работающие в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136 т молока. Основное оборудование может быть занято в течение 21,4 машино-часа, а автоматы по расфасовке сметаны − в течение 16,25 ч. Прибыль от реализации 1 т молока,
кефира и сметаны соответственно равна 30000, 26000 и 150000 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в пакеты. Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной. □ Предположим, что молочный завод будет ежедневно производить x 1 тонн молока, x 2 тонн кефира и x 3 тонн сметаны. Тогда для производства этой продукции необходимо 1010 x 1 + 1010 x 2 + 9450 x 3 кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство 1010 x 1 + 1010 x 2 + 9450 x 3 ≤ 136000. Аналогичные рассуждения, проведенные относительно возможного использования линий разлива цельномолочной продукции и автоматов по расфасовке сметаны, позволяют записать неравенства 0,18 x 1 + 0,19 x 2 ≤ 21,4 3,25 x 3 ≤ 16,25. Так как ежедневно должно вырабатываться не менее 100т молока, то x 1 ≥ 100. По своему экономическому смыслу переменные x 2 и x 3 могут принимать лишь
| неотрицательные значения | x 2 | ≥ 0, x 3 ≥ 0. | Общая прибыль от реализации x 1 тонн | |||
| молока, x 2 тонн кефира и | x 3 | тонн сметаны равна 30000 x 1 + 22000 x 2 + 150000 x 3 руб. | ||||
| Таким образом, приходим к следующей задаче. | ||||||
| Дана система | ||||||
| 1010 x 1 + 1010 x 2 | + 9450 x 3 | ≤ 136000 | ||||
| 0,18 x 1 | + | 0,19 x 2 | ≤ 21,4 | |||
| (8.4) | ||||||
| 3,25 x 3 | ≤ 16,25 | |||||
| x 1 ≥ 100, x 2 ≥ 0, | x 3 | ≥ 0. | ||||
из четырех линейных неравенств и линейная функция относительно переменных, x 1 , x 2 и x 3
| F = 30000 x 1 + 22000 x 2 + 150000 x 3 . | (8.5) |
Так как система (8.4) представляет собой систему линейных неравенств и функция (8.5) линейная, то эта задача является задачей линейного программирования. ■
8.2. Общая и каноническая задачи линейного программирования
Выше были рассмотрены примеры постановки задач линейного программирования. Во всех из них требовалось найти максимум линейной функции при условии, что ее переменные принимали неотрицательные значения и удовлетворяли некоторой системе линейных уравнений или неравенств либо системе, содержащей как линейные уравнения, так и неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования. Определение. Общей (основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции
| n | (8.6) |
| F = ∑ c j x j | |
| j = 1 | |
| при выполнении условий | (8.7) |
| n | |
| ∑ a ij x j ≤ b i ( i = 1. k ) | |
| j = 1 | (8.8) |
| n | |
| ∑ a ij x j = b i ( i = k + 1. m ) | |
| j = 1 | |
| x j ≥ 0 ( j = 1. l ; l ≤ n ) | (8.9) |
где a ij , b i и c j − заданные постоянные величины и k ≤ m . Определение . Функция (8.6) называется целевой функцией задачи (8.6) − (8.9), а условия (8.7) − (8.9) − ограничениями данной задачи. Определение. Канонической задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8.6) при выполнении условий (8.8) и (8.9), где k = 0 и l = n .
| Определение. | Вектор | X = ( x 1 , x 2 , … , x n ) T , | удовлетворяющий ограничениям |
| задачи (8.7) − (8.9), называется допустимым решением , или планом . | |||
| Определение . | План | X = ( x 1 , x 2 , … , x n ) T , | при котором целевая функция |
принимает свое максимальное (минимальное) значение, называется оптимальным . Чтобы перейти от одной формы записи задачи линейного программирования к другой, нужно в общем случае уметь, во-первых, сводить задачу минимизации функции к задаче максимизации; во-вторых, переходить от ограничений-
неравенств к ограничениям-равенствам; в-третьих, заменять переменные, которые не подчинены условиям неотрицательности. В том случае, когда требуется найти минимум функции F = с 1 x 1 + с 2 x 2 +…+ с n x n , можно перейти к нахождению максимума функции F 1 = − F = − с 1 x 1 − с 2 x 2 −…− с n x n , поскольку min F = max( − F ) . Нестрогое ограничение-неравенство общей задачи линейного программирования можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство a i 1 x 1 + a i 2 x 2 +…+ a in x n ≤ b i преобразуется в ограничение-равенство a i 1 x 1 + a i 2 x 2 +…+ a in x n + x n + 1 = b i , x n + 1 ≥ 0, а ограничение-неравенство a i 1 x 1 + a i 2 x 2 +…+ a in x n ≥ b i преобразуется в ограничение-равенство a i 1 x 1 + a i 2 x 2 +…+ a in x n − x n + 1 = b i , x n + 1 ≥ 0. Вводимые дополнительные переменные имеют вполне определенный смысл в рамках решения экономических задач. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, как это будет показано в дальнейших примерах, равно объему неиспользуемого соответствующего ресурса. Наконец, если переменная x k по условию задачи отрицательна, то ее следует заменить двумя неотрицательными переменными u k и v k , приняв x k = u k − v k . Пример 8.3. Записать в форме канонической задачи линейного программирования задачу нахождения максимума функции F = 3 x 1 − 2 x 2 − 5 x 4 + x 5 при условиях 2 x 1 + x 3 − x 4 + x 5 ≤ 2, x 1 − x 3 + 2 x 4 + x 5 ≤ 3,2 x 1 + x 3 − x 4 + 2 x 5 ≤ 6, x 1 + x 4 + 5 x 5 ≥ 8, x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0
3.3. Частные случаи использования графического метода
В рассмотренном в предыдущем вопросе примере множество решений задачи линейного программирования являлось замкнутым многогранником, система ограничений была совместимая и линейно независима, а оптимальное решение единственное. Однако на практике имеют место случаи, при которых эти условия не выполняются.
При применении графического метода решения задач линейного программирования возможны следующие частные случаи:
1 . Целевая функция достигает максимального (минимального) значения не в одной точке, а на некотором отрезке (например AB), который является границей многогранника области допустимых решений и расположен параллельно к линиям уровня целевой функции (рис. 3.3а).
2 . Задача не имеет оптимальных планов (рис. 3.2б – значение целевой функции равно бесконечности; рис. 3.2г – система ограничений задачи несовместима).
3. Задача имеет оптимальный план при неограниченной (незамкнутой) области допустимых решений (рис. 3.2в).
Рис. 3.3. Графическое представление некоторых частных случаев в задачах линейной оптимизации
3.4. Общий алгоритм графического метода
Составим алгоритм графического метода решения задач линейных оптимизационных задач:
Этап 1. Строим прямые линии, уравнения которых получаем заменой в ограничениях-неравенствах знаков неравенств на знаки равенств.
Этап 2. Определяем полуплоскости, соответствующие заданным ограничениям.
Этап 3. Находим многогранник области допустимых решений как область, где пересекаются все полу плоскости.
Примечание.Если такая область не существует, значит данная система ограничений несовместима и задача не имеет решений.
Этап 4. Строим вектор нормали , задающий направление роста значений целевой функции.
Этап 5. Строим линию уровня – прямую 
(т.е. 
, перпендикулярной (под прямым углом) к вектору 
и проходящей через начало координат.
Этап 6. Перемещаем линию уровня в направлении вектора для задачи максимизации целевой функции или в противоположном направлении для задачи минимизации. Последняя вершина многогранник области допустимых решений через которую пройдет линия уровня и будет точкой, в которой целевая функция достигает экстремального значения.
Примечание 1.В случае поиска максимума, если область допустимых решений не является замкнутым пространством точек в направлении вектора значение целевой функции будет равно бесконечности.
Примечание 2.В случае поиска минимума, если область допустимых решений не является замкнутым пространством точек в направлении противоположному вектору значение целевой функции будет равно минус бесконечности.
Этап 7. Определяем координаты вершины многогранника области допустимых решений, определенной на предыдущем этапе, путем решения системы уравнений, на пересечении которых она находится.
Этап 8. Вычисляем экстремальное значение целевой функции в оптимальной точке.
Глава 4. Симплексный метод ршения задач линейной оптимизации
4.1. Каноническая форма задачи линейного программирования
4.2. Пример использования симплекс-метода в общем случае
4.3. Частные случаи использования симплекс-метода