Линейное программирование

ЛЕКЦИЯ 1 ТЕМА 1. ОСНОВНЫЕ ПОНЯТИЯ И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Операция – мероприятие, направленное на достижение некоторой цели, допускающее несколько возможностей и их управление. Исследование операций – совокупность математических методов, позволяющих принять обоснованное решение для получения оптимального результата. Решение – выбор одной из нескольких возможностей. Оптимальное решение – решение, предпочтительное по отношению к другим по некоторому принципу. Исследование операций включает в себя пять основных разделов. 1. Программирование: – линейное; – нелинейное; – динамическое. 2. Теория игр. 3. Сетевое планирование и графическая оптимизация. 4. Теория массового обслуживания. 5. Системный анализ. ТЕМА 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 2.1. Задачи, приводящие к понятию линейное программирование 1. Задача об оптимальном использовании ресурсов Предположим, что предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (разных видов сырья, вспомогательных материалов, запасов машинного времени, людских ресурсов и т.д.). Эти ресурсы ограничены и составляют в планируемый период соответственно b1 , b2 ,, bm условных единиц. Известны также технологические коэффициенты a ij , которые показывают, сколько единиц i ресурса требуется для производства единицы j –того вида   изделия i  1, m; j  1, n . Пусть прибыль, получаемая предприятием при реализации единицы изделия j  того вида, равна с j ,  j  1,2,  , n  . В планируемый период все показатели a ij , с j и bi предполагаются постоянными. Требуется составить такой план выпуска продукции, при котором прибыль предприятия от реализации была бы наибольшей. Составим математическую модель задачи, т.е. выразим экономические требования в виде соответствующих математических зависимостей – уравнений, неравенств и т.д. n f  x    c j x j  max, j 1 n  aij x j  bi ,  i  1, m, j 1 x j  0,  j  1, n. Система линейных неравенств вместе с условием неотрицательности переменных представляют систему ограничений данной задачи по объѐму соответствующего ресурса, поскольку в ходе выполнения плана можно использовать либо весь запас этого ресурса, либо его часть. Требуется составить оптимальный план работы предприятия, т.е. найти такие неотрицательные значения x1 , x2 ,, xn , которые бы удовлетворяли системе ограничений, и при которых прибыль от реализации всей продукции была бы максимальной. Функция f  x  в данном случае выражает суммарную прибыль, поэтому эту функцию называют целевой. 2. Задачи о смесях (о диете) К группе задач о смесях относят задачи по отысканию наиболее дешевой смеси, которая должна иметь в своѐм составе n различных компонент в определѐнных количествах, а сами компоненты являются составными частями m исходных материалов. Обобщѐнная таблица задачи о смесях имеет следующий вид: Продукты Хлеб Полезные вещества Белки Жиры Углеводы … Молоко Мясо … Нормы a11 a12 a13 a 21 a 22 a 23 a 31 a 32 a 33 … … … … … … … b1 b2 b3 … Коэффициенты a ij показывают содержание полезного i –того вещества в единице j –того продукта. bi – минимальная норма потребления полезного вещества. x j  количество продукта j –того вида, потребляемого за некоторое время. с j  стоимость единицы данного продукта. Тогда математическая модель задачи имеет вид: n f  x    c j x j  min, j 1 n  aij x j  bi ,  i  1, m, j 1 x j  0,  j  1, n. 3. Транспортная задача Простейшей транспортной задачей является задача о перевозках некоторого однородного груза от поставщиков к потребителям с целью обеспечения минимальных затрат на перевозки. По условию задачи имеем: m – поставщиков, bi – мощность i поставщика в планируемый период; n – потребителей, a j – спрос j потребителя на этот же период; cij  стоимость поставки единицы груза от i поставщика к j потребителю; xij  количество продукции, которое планируется перевезти от i поставщика к j   потребителю i  1, m; j  1, n . Задачу можно формализовать в виде матрицы перевозок.  x11c11 x12 c12   c c  x21 21 x22 22       cm1 c xm 2 m 2   xm1 a1 a2  Математическая модель задачи: c x1n 1n  b1  c2 n x2 n  b2    c xmn m n  bn an m n f  x     cij xij  min, i 1 j 1 m n  bi   a j , i 1 j 1 n  xij  bi ,  i  1, m, j 1 m  xij  a j ,  j  1, n, i 1 xij  0. Класс рассмотренных экономических задач обычно называют оптимизационные задачи линейных моделей экономики. Раздел математики, рассматривающий решение задач подобного типа, называется линейное программирование. 2.2. Общая задача линейного программирования Рассмотрим математическую модель следующего вида: n f  x    c j x j  max min  j 1 (1) n  aij x j  bi ,  i  1, k , (2)  aij x j  bi ,  i  k  1, l , (3) j 1 n j 1 n  aij x j  bi ,  i  l  1, m , j 1 (4) x j  0,  j  1, r , (5) x j  0,  j  r  1, s , (6) x j  0,  j  s  1, n , (7) где a ij , c j , bi – заданные постоянные величины. Приведѐнная задача (1) – (7) называется общей задачей линейного программирования. Функция (1) называется целевой функцией. Элементы матрицы – строки С  с1 , c2 ,, cn   c j  коэффициенты целевой функции. Система (2) – (7) называется системой ограничений.  a11 a12  a1n     a21 a22  a2 n  A – матрица системы ограничений.       a a  a  m1 m2 mn   b1    b  B   2  – матрица-столбец свободных членов ограничений.     bm   x1    x  X   2  – матрица-столбец неизвестных.     xn  Всякое решение, удовлетворяющее системе ограничений, называется планом x  ~  ~1  ~  x2  задачи линейного программирования: X    .    ~  xn  ~ План X * называется оптимальным планом, если для X выполняется: ~ – для задачи на максимум f X *   f Х ; ~ – для задачи на минимум f X *   f Х . Решить задачу линейного программирования, значит найти оптимальный план задачи или доказать, что он не существует. 2.3. Основная задача линейного программирования Основной задачей следующего вида: линейного программирования называется задача n f  x    c j x j  max , (8) j 1 n  aij x j  bi ,  i  1, m , (9) x j  0,  j  1, n , (10) j 1 bi  0,  i  1, m . (11) Эту задачу можно записать в матричной форме f  X   CX  max, AX  B, X  0, B  0. Теорема. Всякая общая задача линейного программирования может быть сведена к основной задаче. Доказательство. Пусть общая задача линейного программирования сформулирована как задача поиска минимума функции (1) при ограничениях (2) – (7). Тогда для перехода к основной задаче необходимо выполнить следующие операции: 1) Перейти от задачи минимизации к эквивалентной задаче максимизации. т.е. нахождение эквивалентно min f x   max  f x  , f x   min ~ ~ исследованию  f x   max , неравенства f X *   f X и  f X *    f X эквивалентны; 2) Перейти от неравенств типа (2) к уравнениям типа (4). Для этого вводим дополнительные неотрицательные переменные: xn  i  0, i  1, l ,      n  aij x j  xn  i  bi ,  i  1, l ; j 1 3) Перейти от неравенств типа (3) к уравнениям типа (4). Это достигается также путем введения дополнительных неотрицательных переменных xn  i  0, i  l  1, k , n  aij x j  xn  i  bi ,  i  l  1, k ; j 1 4) Заменить неположительные переменные (6) на неотрицательные переменные типа (5). Это достигается заменой переменных x j  t j , t j   x j  0 ,  j  r  1, s ; 5) Перейти от произвольных переменных (7) к неотрицательным переменным типа (5). Заменим переменные типа (7) разностью двух неотрицательных переменных x j  t j  s j , t j  0, s j  0 ,  j  s  1, n ; 6) Перейти к положительным свободным членам в (9). Если существуют bi  0 , то обе части соответствующего ограничения достаточно умножить на  1 . Теорема доказана. В некоторых частных случаях, например, когда в задаче только две переменные, можно непосредственно решить общую задачу линейного программирования. Для этого используют графический метод решения.