Материал: Методические указания для организации выполнения курсовой работы по курсу Высшая математика. Пантелеев И.Н

2

1. Общая задача линейного программирования

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

найти вектор X = (x1 , x2 ,..., xn ) , максимизирующий (минимизирующий) функцию

j=1

иудовлетворяющий условиям

x j ³ 0, j = 1, n

Линейная функция f (X ) называется целевой функцией задачи. Условия (2) называются ограничениями задачи.

Любое решение системы ограничений ЗЛП называется допустимым планом. Допустимый план, максимизирующий или минимизирующий целевую функцию назы-

вается оптимальным.

План, у которого отличным от нуля компонентам соответствует система линейно независимых векторов, называется опорным планом.

Теорема. Множество планов задачи линейного программирования является выпуклым множеством.

Теорема. Оптимальный план задачи линейного программирования находится в крайней точке выпуклого множества планов. Если оптимальный план находится в двух крайних точках выпуклого множества планов, то он находится также и в любой точке, являющейся выпуклой комбинацией этих крайних точек.

Формы ЗЛП

Форма задачи линейного программирования, у которой ограничения заданы в виде неравенств, называется стандартной, а форма задачи, у которой ограничения заданы в виде уравнений – канонической. Если же система ограничений содержит и уравнения и неравенства, то такая форма называется смешанной.

3

2. Графический метод решения задачи линейного программирования

Если задача содержит только две переменные, а система ограничений задана в виде неравенств, то её можно решить графическим методом.

Графический метод решения ЗЛП состоит из следующих этапов.

1.Строится область допустимых решений (ОДР) ЗЛП.

2.Строится вектор-градиент целевой функции(вектор, координатами которого явля-

ются частные производные функции) с приложением в начале координат – Ñ = (C1 , C2 ) .

3. Линия уровня C1x1+C2x2 = а (а – постоянная величина) - прямая, перпендикулярная

вектору–градиенту Ñ – передвигается в направлении этого вектора в случае максимизации f(x1,x2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x1,x2).

4. Для нахождения ее координат достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x1,x2), найденное в полученной точке, является максимальным.

При минимизации f(x1,x2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то целевая функция f(x1,x2) не ограничена на максимум (в задаче максимизации) или минимум (в задаче минимизации).

Если линия уровня параллельна какой-либо прямой из ограничений задачи, то оптимальное значение целевой функции будет достигаться в любой точке этой прямой.

Пример. Найти максимальное значение функции f=2x1 + 3x2 при условиях

Построим область допустимых значений:

1) первое ограничение x1 + 3x2 £18; прямая x1 + 3x2 = 18 пересекает оси координат в точках (0; 6) (18; 0); неравенству соответствует полуплоскость, содержащая данную прямую и лежащая ниже неё (контрольная точка (0; 0), 0 + 3*0 < 18 принадлежит полуплоскости);

2) второе ограничение 2x1 + x2 £ 16: прямая 2x1 + x2 = 16 пересекает оси координат в точках (0; 16) (8; 0); неравенству соответствует полуплоскость, содержащая данную прямую

илежащая ниже неё (контрольная точка (0; 0), 2*0 + 0 <16 принадлежит полуплоскости);

3)неравенству x2 £ 5 соответствует полуплоскость, содержащая прямую x2 = 5 и лежащая ниже неё.

4)x1 ³ 0 - правее ОX2;

5)x2 ³ 0 - выше ОX1.

Вектор-градиент имеет координаты Ñ = (2;3) .

Построим линии уровня 2x1 + 3 x2 = а. При а = 0 получим прямую 2x1 + 3x2 = 0, проходящую через начало координат, перпендикулярно вектору-градиенту. Так как задача на максимум, то передвигаем линию уровня в направлении градиента. Предельной точкой (последней из области допустимых решений, с которой соприкасается линия уровня) является точка С. Значит, в ней достигается максимум функции f (рис. 1).

Найдём её координаты. Для этого решим систему, составленную из уравнений прямых пересекающихся в точке С (I и II):

ìx1 + 3x2 = 18, ìx1 = 6,

íî2x1 + x2 = 16; íîx2 = 4;

Таким образом, получим x1 = 6, x2 = 4, fmax = 2*6 + 3*4 = 24.

4

Рис. 1.

3. Нахождение решения задачи линейного программирования

Для решения ЗЛП существует универсальный метод– метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: сим- плекс-метода с естественным базисом и симплекс-метода с искусственным базисом(М- метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения -ис ходной ЗЛП к каноническому виду.

Для применения симплекс-метода с естественным базисом ЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план.

Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные записать в таблицу:

В первом столбце таблицы"Базис" записывают базисные векторы данного опорного плана. Во втором столбце - коэффициенты целевой функции (с1, с2,…, сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу). В третьем столбце Р0 - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы второго столбца таблицы со столбцом Р0, и суммируя эти произведения, мы получаем значение целевой функции(F0=с1*b1 + с2*b2+…+

сm*bm).

Первая строка симплексной таблицы содержит коэффициенты целевой функции нашей задачи и остается неизменной на протяжении всего решения (с1, с2,…, сm).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи. При этом следует заметить, что коэффициенты при базисных пере-

5