практикум по математике часть 3

теперь уже на плоскости x1Ox2 в направлении вектора grad F . Пересечение этих прямых с проекцией многоугольника A1B1C1D1E1 , каковой является

многоугольник ABCDE, в точках A и C даст решение задачи. Подставив координаты x1, x2 этих точек в формулу целевой функции, определяют

min F и max F .

Сформулируем алгоритм геометрического метода решения задачи линейного программирования (рис.1.2).

1. Строим область допустимых решений для системы ограничений задачи:

a)Строим прямые линии, полученные из системы ограничений (1.5) путем замены неравенств равенствами;

b)Находим полуплоскости, определяемые системой ограничений

(1.5);

c)Строим многоугольник решений системы ограничений (1.5).

указывает на направление возрастания целевой функции). Вектор grad F –

свободный вектор, т.е. его можно построить в любой точке, в том числе и в начале координат.

3.Проводим линию уровня F0 = 0 перпендикулярно вектору grad F .

4.Перемещаем линию уровня параллельно самой себе в направлении вектора grad F .

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

5. Находим координаты указанных точек экстремума и вычисляем значение целевой функции в них.

Система ограничений (1.5)– область допустимых решений задачи

линейного программирования может быть представлена не только многоугольником решений. На рис.1.3. представлены возможные варианты

этой области: выпуклый многоугольник (а, б), неограниченная выпуклая

многоугольная область (в), единственная точка (г), прямая линия (д), отрезок

прямой (е), луч (ж), пустое множество (з).

10

Если область допустимых решений неограничена в направлении

противоположном вектору grad F , то min F = −∞.

Если область допустимых решений– пустое множество (рис.1.3, з), то

задача не имеет решения ввиду несовместности системы ограничений.

Пример 1. Найти такие значения неизвестных, которые доставляют

максимум функции

F = −x1 + x2 → max

при условиях

2x1 − x2 ≥ −2x1 − 2x2 ≤ 2x1 + x2 ≤ 5x1 ≥ 0, x2 ≥ 0

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

Решение.

1. Находим допустимую область.

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

Уравнения граничных прямых:

Строим прямые по найденным точкам в выбранной системе координат (рис.1.4). Масштабы на осях выбираем, исходя из удобства построения.

12

Построим нормальный вектор gradF , и перпендикулярно к нему через

точку (0;0) проведем прямую. Уравнение этой прямой :

− x1 + x2 = 0

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

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

Замечание. Для построения вектора gradF описанным выше способом

нужно, чтобы по осям координат Ox1 и Ox2 был выбран одинаковый масштаб. Если это условие не соблюдено, то нужно взять, одну из линий уровня целевой функции F ,например − x1 + x2 = 0 и построить ее по двум

выбранным точкам, например (0;0) и (2; 2). Далее следует провести линию уровня через эти точки и перпендикулярно к ней построить вектор gradF .

Линию уровня перемещаем параллельно самой себе в направлении вектора gradF до тех пор, пока позволяет область допустимых планов, т.е. до точки

А.

Найдем координаты точки А, заметив, что она лежит на пересечении прямых (l1) и (l3). Решим систему уравнений:

2x1 − x2 = −2x1 + x2 = 5

Координаты точки А (1;4) соответствуют оптимальному плану. Подставляя найденные значения x1 и x2 в целевую функцию, получим

максимальное значение целевой функции:

Fmax = −1 + 4 = 3.

Итак, Fmax =3 при x1 =1; x2 = 4 .

1.1.2. Симплекс-метод

Симплекс-метод (аналитический метод) – самый общий метод решения задач линейного программирования. Его еще называют «методом последовательного улучшения плана». При его использовании задача линейного программирования должна быть приведена к каноническому виду. Если условие (1.2) является системой неравенств со знаком ≤ (симметричная задача), то для приведения задачи к каноническому виду (знак ≤

14

преобразовать в знак =) в левых частях каждого неравенства необходимо добавить по дополнительной положительной переменной xn+1 ,..., xn+m.

Тогда задача (1.1) – (1.3) примет следующий вид: требуется найти такие значения переменных x1, x2 ,..., xn , которые доставляют максимум

(минимум) целевой функции

Сущность симплекс-метода заключается в следующем.

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

Симплекс-метод осуществляет целенаправленный перебор опорных планов так, что на каждом следующем опорном плане значение целевой функции F улучшается. Если оптимальный план существует, то он будет достигнут.

Алгоритм симплекс-метода.

1.Математическая модель задачи должна быть канонической (1.6) - (1.8). Если она неканоническая, то ее надо привести к каноническому виду.

2.Составить симплекс-таблицу и выписать начальный план.

Все строки первой таблицы, за исключением последней заполняются по данным системы ограничений (1.7) (это расширенная матрица системы ограничений (1.7)). При необходимости некоторые уравнения системы ограничений следует умножить на (–1) (чтобы все свободные члены уравнений были неотрицательными).

Последнюю строку, которую назовем индексной, заполняем коэффициентами целевой функции (1.6), представленной в виде уравнения

n

F − c1x1 − c2 x2 −... − cn xn = с0 или F − ∑c j x j = с0

j=1

Заполним первую симплекс-таблицу (табл.1.1).

15

Таблица 1.1

Допустимое (все члены решения положительные ) базисное ( свободные члены равны нулю) решение системы (1.7) является

начальным опорным планом: (0,0,0,…,0,b1,b2,b3,…,bm).

3.Проверить полученный план на оптимальность по индексной

строке.

Если все ci ≥ 0 ( кроме c0 ), то план оптимальный и F = c0 .

4.Если хотя бы одна ci ≤ 0, то либо устанавливают неразрешимость

задачи, либо переходят к новому опорному плану. Здесь возможны случаи: a) если хотя бы одна ci ≤ 0, но при соответствующей переменной x j

нет ни одного положительного коэффициента aij (i =1, 2, K, m ), то целевая

функция неограничена в области допустимых решений и решение прекращается;

b) если хотя бы одна оценка отрицательна, а при соответствующей

абсолютной величине из отрицательных чисел (− ci ), то есть max − ci и если

внем есть хотя бы один положительный элемент;

b)разрешающую строку принимают ту, которой соответствует минимальное отношение свободных членов bi к

положительным элементам разрешающего столбца.

c) Элемент, стоящий на пересечении разрешающей строки и столбца, называется разрешающим элементом.

6. Строим вторую симплекс-таблицу. Для этого:

a) Элементы разрешающей строки делим на разрешающий

элемент;

16

b) Остальные элементы находим по правилу «прямоугольника»: пусть разрешающим элементом является элемент apq ; тогда справедлива

формула

где apq , aij , aiq , apj - элементы предыдущего шага, aij′ - элемент нового шага, apq aij – главная диагональ.

Таким образом, получается новое опорное решение, которое проверяется на оптимальность.

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

1.

7. Записываем новый план и проверяем его на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаемся к пункту 5. Процесс решения задачи заканчиваем в случае получения оптимального плана, то есть выполнения пункта 3.

Замечания. 1. Если на каком либо шаге окажется, что хотя бы одна нулевая оценка свободной переменной c j = 0 , при всех остальных c j > 0 , то

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

Критерием альтернативного оптимума при решении задач симплексметодом является равенство нулю хотя бы одной оценки свободной переменной (сj = 0 ).

Если только одна оценка свободной переменной равна нулю, то решение

где 0 ≤ t ≤1, x1опт , x2опт - произвольные оптимальные решения.

Если S свободных переменных имеют нулевые оценки, то оптимальное решение определяется по формуле

i=1

s

где ∑ti =1, ti ≥ 0 .

i =1

17

разрешающей строки рассмотрим отношения и выберем минимальное среди них

min 2 , 5 = min{2,5}= 2 .

⎩1 1

Выбираем строку при x3 (минимальное отношение). Разрешающий элемент равен 1 (элемент, стоящий на пересечении строки при x3 и столбца

при x2 ).

Вводим в столбец базисных переменных x2 и выводим x3 . Составляем

симплекс-таблицу 2-го шага (табл. 1.3). Разрешающую строку делим на разрешающий элемент, остальные строки пересчитываем по правилу прямоугольника (1.9):

19