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

1. Введение.

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

конечномерного  векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). Такие задачи имеют огромную область применения, не в последнюю очередь потому, что “любой процесс в первом приближении является линейным”.

Вместе  с задачей линейного программирования изучается тесно с ней связанная двойственная или сопряжённая задача. Использование теории двойственности позволяет удвоить полезные свойства задач математического программирования. Особенно важна эта теория для матричных игр. Вообще она является сердцевиной линейного программирования. Теория двойственности наиболее успешно применяется в задачах линейного программирования с экономическим содержанием. Распространён взгляд на экономику, как науку о “распределении ограниченных ресурсов с целью получения максимальной прибыли”. Можно выделить два подхода к её изучению. Один из них связан с максимизацией прибыли. Другой основан на минимизации издержек. Двум этим подходам соответствует пара двойственных задач линейного программирования. Иногда двойственность позволяет более просто решить исходную задачу линейного программирования.

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

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

     Определение 1. Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.

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

     Определение 2. Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.

     В общем виде математическая модель задачи линейного программирования (ЛП) записывается как 

при ограничениях: 
 

где — неизвестные; — заданные постоянные величины.

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

     Математическая  модель в более краткой записи имеет вид 

при ограничениях: 
 

     Определение 3. Допустимым решением (планом) задачи линейного программирования называется вектор , удовлетворяющий системе ограничений.

     Множество допустимых решений образует область  допустимых решений (ОДР).

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

     Базисное  допустимое решение является опорным решением, где r — ранг системы ограничений.

     Математическая  модель задачи ЛП может быть канонической и неканонической.

     Определение 5. Если все ограничения системы заданы уравнениями и переменные неотрицательные, то такая модель задачи называется канонической.

     Если  хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство  ввести балансовую переменную . Если знак неравенства ≤, то балансовая переменная вводится со знаком плюс, если знак неравенства ≥, то — минус. В целевую функцию балансовые переменные не вводятся.

     Чтобы составить математическую модель задачи ЛП, необходимо:

     — ввести обозначения переменных;

     — исходя из цели экономических исследований, составить целевую функцию;

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

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

     Наиболее  простым и наглядным методом  линейного программирования является графический метод. Он применяется для решения задач ЛП с двумя переменными, заданными в неканонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных.

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

     Для нахождения экстремального значения целевой  функции при графическом решении задач ЛП используют вектор на плоскости Х₁ОХ₂, который обозначим . Этот вектор показывает направление наискорейшего изменения целевой функции, он равен 

где и — единичные векторы по осям OX₁ и ОX₂ соответственно; таким образом,  _{. Координатами вектора} являются коэффициенты целевой функции .

Алгоритм  решения задач.

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

     2. Строим вектор .

     3. Проводим линию уровня L₀, которая перпендикулярна .

     4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум.

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

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

где 0 ≤  t ≤ 1, ₁ и ₂ — оптимальные решения в угловых точках ОДР.

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

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

3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ  ГРАФИЧЕСКИМ МЕТОДОМ.

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

 
 
 
 

     В задаче ЛП extr означает единый термин для экстремума, т.е. для нахождения максимума и минимума функции. Построим область X на плоскости. Она расположена в первой четверти и ограничена прямыми m и n. Для удобства построения запишем уравнения этих прямых в отрезках.

 

     Здесь пересечение прямых m и n с осью OX, а - пересечение с осью OY. Соответствующий чертёж представлен на рис.1. Здесь m представлена прямой АВ, а n представлена прямой ДВ.

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

     Построим  прямые уровня, которые касаются области X. Таких прямых две

 
 
 
 
 
 
 
 
 
 
 
 
 
 

рис.2.1.

     Прямая  касается области X в точке О(0,0), а прямая – в точке    В(6,8). Отметим, что координаты точки В являются решением системы уравнений

 
 

     Точки касания О(0, 0) и В(6, 8) определяют решение  задачи линейного программирования. Именно,

Пример  2.2. Выбор оптимального варианта выпуска изделий.

     Фирма выпускает 2 вида мороженого: сливочное  и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы даны в таблице.

       

     Изучение  рынка сбыта показало, что суточный спрос на сливочное мороженое  превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 р., шоколадного — 14 р.

     Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?

 

     Решение. Обозначим: x₁ — суточный объем выпуска сливочного мороженого, кг; x₂ — суточный объем выпуска шоколадного мороженого, кг.

     Составим  математическую модель задачи.

     Целевая функция будет иметь вид

 

при ограничениях:

 
 

OABDEF — область допустимых решений (рис. 2.2). Строим вектор (1, 1). Линия уровня L₀ задается уравнением

 
 
 
 
 
 
 
 
 
 
 
 
 

     рис.2.2.

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

 

     Решая систему, получим координаты точки  D (312,5; 300), в которой и будет оптимальное решение, т.е.

 

при этом

     L

     Таким образом, фирма должна выпускать  в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9 200 р.

 

     2.4. Примеры решения  по методу.

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

 
 
 
 
 
 

     Построим  область X на плоскости. Она расположена  в первой четверти, т.к. , и ограничена прямыми m, n, p, q. Для удобства построения приведём уравнения этих прямых в отрезках.

 
 

     Здесь пересечение прямых m, n, p, q с осью OX, а – пересечение с осью OY. Чертёж представлен на рис.2.3. Здесь m - прямая СF, n - прямая DE, p - прямая BG, а q - прямая AH. Каждая прямая определяет полуплоскость. Для всех прямых CF, DE, BG, AH это будут полуплоскости, содержащие начало отсчёта O. Тогда область допустимых значений в задаче линейного программирования представляется пятиугольником OALKE.

 
 
 
 
 
 
 
 
 
 
 
 
 
 

     рис.2.3.

     Построим  прямые уровня, которые касаются области X. Таких прямых две

 

     Прямая  касается области X в точке О(0, 0), а прямая - в точке    K(2, 2,4). Точка K - пересечением прямых m, n и её координаты находятся как решение системы уравнений

 
 

     Решение системы  значит K(2, 2,4). Точки касания K(2, 2,4) определяют решение задачи линейного программирования. То есть

4. ПОСТАНОВКА  И АЛГОРИТМ РЕШЕНИЯ  СИМПЛЕКСНОГО МЕТОДА.

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

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

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

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

     2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки Δ_j (индексная строка), заполняем по данным системы ограничений и целевой функции.

     Таблица 3.1.

       
 
 

     Индексная строка для переменных находится  по формуле

 

и по формуле

 

     Возможны  следующие случаи при решении  задачи на максимум:

     — если все оценки Δ_j ≥ 0, то найденное решение оптимальное;

     — если хотя бы одна оценка Δ_j ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как , т.е. целевая функция неограниченна в области допустимых решений;

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

     — если отрицательных оценок в индексной  строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

     Если  хотя бы одна оценка Δ_k < 0, то k-й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

     3. Заполняем симплексную таблицу 2-го шага:

     — переписываем ключевую строку, разделив ее на ключевой элемент;

     — заполняем базисные столбцы;

     — остальные коэффициенты таблицы  находим по правилу "прямоугольника". Правило "прямоугольника" заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m + 1)-го столбца h_1,m+1. Тогда элемент i-й строки (m + 2)-го столбца 2-го шага — обозначим его h’_i,m+2 — согласно правилу "прямоугольника" выражается формулой

 

где   — элементы 1-го шага. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

     Примечание. Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δ_j при всех j = .

 

5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ  СИМПЛЕКСНЫМ МЕТОДОМ.

Пример  1. Для задачи линейного программирования записать двойственную задачу и решить обе задачи симплексным методом

 
 
 
 
 

Запишем двойственную задачу

 
 
 
 
 

     Представим  прямую задачу линейного программирования в канонической форме

 
 
 
 
 

     Данные, приведённые в канонической задаче, заносим в симплекс таблицу.

     Таблица 3.2.

       
 

     Заполнение  таблицы стандартное, в столбце  “Значения” у оценочной функции ставим 0, т.к. в функции цели постоянное слагаемое 0. Выделяем базисные переменные. Это переменные, для которых столбцы образуют единичную матрицу. Базис образуют . Остальные переменные являются свободными.

     По  заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы. Они представлены в столбце “Значение”. Отметим, что значение функции цели берём с противоположным знаком. Итак,

     В оценочной строке имеются положительные  числа. Значит, решение можно улучшить. Выберем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них, например, первое. Соответствующий столбец называем ведущим. По ведущему столбу и столбцу “Значения” определяем оценку строки. Число из столбца “Значение” делим на соответствующее число из ведущего столбца. Получаем оценку строки. По условию задачи это положительное число. Объявляем ведущей строкой ту, оценка у которой наименьшая. В таблице 3.2 ведущая строка и столбец выделены цветом. На их пересечении находится ведущий элемент. В нашем случае это число 4.

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

     Таблица 3.3.

 

     Из  таблицы 3.3 находим базисные переменные (свободные переменные равны 0) и значение функции. Получаем Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования. Действительно, т.е. получили верное равенство.

     В оценочной строке имеется положительное  число, значит можно перейти к следующей итерации. В таблице 3.3 цветом выделены ведущий столбец и ведущая строка. Суть второй итерации состоит в том, чтобы свободную переменную преобразовать в базисную, а базисную переменную сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 3.4.

     Из  последней таблицы находим базисные переменные и значение функции цели. Получаем Этот результат можно проверить. Действительно, Итак, мы получили верное равенство.

     Таблица 3.4.

 

     В оценочной строке есть одно положительное число. Значит можно перейти к следующей итерации. В таблице 3.4 цветом выделены ведущий столбец и ведущая строка. Суть третьей итерации состоит в том, чтобы свободную переменную преобразовать в базисную, а базисную переменную сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 3.5.

     Таблица 3.5.