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

Размещено на http://www.allbest.ru/

Лекция 1. Линейное программирование

Общая постановка задачи

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

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

ь задача об оптимальном использовании ресурсов при производственном планировании;

ь задача о смесях (планирование состава продукции);

ь задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

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

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

ь математические модели большого числа экономических задач линейны относительно искомых переменных;

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

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

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

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

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

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

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

Z(x)=c1x1+c2x2 + . . . +cJxJ + . . . +cnxn > max(min)

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

где Xi -- неизвестные; a ij , bj , Ci -- заданные постоянные величины.

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

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

Z(x) = ?Ci Xi >max(min)

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

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

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

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

Базисное допустимое решение

Является опорным решением, где r-- ранг системы ограничений.

Виды математических моделей ЛП

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

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

Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической.

Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную хn+i .

Если знак неравенства < , то балансовая переменная вводится со знаком плюс, если знак неравенства >, то -- минус. В целевую функцию балансовые переменные не вводятся.

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

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

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

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

Графический метод решения ЗЛП

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

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

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

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

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

Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений, и наоборот..

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

Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений

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

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

Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор gradZ на плоскости x1Ox2.

Этот вектор показывает направление наискорейшего изменения целевой функции. Координатами вектора grandZ являются коэффициенты целевой функции Z(x).

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

Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму:

1. Строим координатные оси Х1ОХ2 и с учетом коэффициентов математической модели выбираем масштаб.

2. Находим область допустимых решений (ОДР) системы ограничений математической модели.

3. Строим прямую целевой функции и показываем направление наискорейшего ее изменения (нормаль - gradZ).

4. Линию целевой функции (линия уровня) перемещаем по направлению нормали для задач на максимум целевой функции и в противоположном направлении - для задач на минимум ЦФ.
Перемещение линии уровня через ОДР производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений. Эта точка будет точкой экстремума,и будет определять единственное решение задачи ЛП.
Если окажется, что линия уровня совпадает с одной из сторон ОДР , то задача ЛП будет иметь бесчисленное множество решений.
Если ОДР представляет неограниченную область, то целевая функция неограниченна.
Задача ЛП может быть неразрешима ,когда определяющие ее ограничения окажутся противоречивыми.

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

Задача производственного планирования

Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить а11 кг сырья первого типа, а21 кг сырья второго типа, а31 кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить а21 кг первого типа, а22 сырья второго типа, а32 сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно. Рыночная цена единицы Изделия 1 составляет c1 тыс руб., а единицы Изделия 2 -c2 тыс. руб.

Требуется:

· Построить математическую модель задачи.

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

a 11 = 2; a12 = 5; b1 = 432;

a 21 = 3; a 22 = 4; b2 = 424;

a 31 = 5; a 32 = 3; b3 = 582;

c1 = 34; c2 = 50.

Решение задачи

Построение модели

Через x1 и x2 обозначим количество выпускаемых изделий 1-го и 2-го типа.

Тогда ограничения на ресурсы:

линейный программирование задача алгоритм

2x1 + 5x2 ? 432

3x1 + 4x2 ? 424

5x1 + 3x2 ? 582

Кроме того, по смыслу задачи

x1 ? 0; x2 ? 0.

Целевая функция экономико-математической модели, выражающая получаемую от реализации выручку:

F = 34x1 + 50x2.

Получаем следующую экономико-математическую модель:

F = 34x1 + 50x2 > max;

2x1 + 5x2 ? 432

3x1 + 4x2 ? 424

5x1 + 3x2 ? 582

x1 ? 0; x2 ? 0.

Построение области допустимых решений. Решим полученную задачу линейного программирования графическим способом:

Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые:

2x1 + 5x2 ? 432 (1)

3x1 + 4x2 ? 424 (2)

5x1 + 3x2 ? 582 (3)

Найдем точки, через которые проходят прямые:

(1) (216, 0) (0, 86,4)

(2) (141.3, 0) (0, 106)

(3) (116.4, 0) (0, 194)

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

Для определения полуплоскости возьмём любую точку, например O(0,0), не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно, то

области решений соответствующего 1-го неравенства соответствует левая полуплоскость.

Возьмём любую точку, например O(0,0), не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно, то области решений соответствующего 2-го неравенства соответствует левая полуплоскость.

Возьмём любую точку, например O(0,0), не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно, то области решений соответствующего 2-го неравенства соответствует левая полуплоскость.

Областью допустимых решений является фигура ABCDE.

Нахождение решения задачи ЛП. Строим вектор лC, координаты которого пропорциональны коэффициентам целевой функции. Здесь л - коэффициент пропорциональности.

лC = 2(34,50) = (68,100).

Перпендикулярно к построенному вектору проводим линию уровня f = 0 .

Перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в крайней точке. Решением на максимум является точка , координаты которой находим как точку пересечения прямых (2) и (1).

2x1 + 5x2 ? 432

3x1 + 4x2 ? 424

x1 =56, x2 = 64.

max f = 34*56 + 50*64 = 5104.

Ответ

Таким образом необходимо выпускать 56 изделий 1-го вида и 64 изделия 2-го вида. При этом выручка от реализации изделий будет максимальна и составит 5104 ден.ед.

Размещено на Allbest.ru