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

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.