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

Автор: Пользователь скрыл имя, 10 Апреля 2012 в 14:16, лекция

Описание работы

1. Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП.
2. Геометрическое решение ЗЛП.
3. Основные теоремы линейного программирования.
4. Симплексный метод решения ЗЛП.
5. Двойственность в линейном программировании.

Скачать полностью (86.59 Кб) Сколько стоит заказать работу?

Работа содержит 1 файл

Экономико-математические методы1.docx

— 93.92 Кб (Скачать)

Экономико-математические
методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В общем виде модель записывается следующим образом:

· целевая функция:

= c₁x₁ + c₂x₂ + ... + c_nx_n → max(min);

(2.1)

· ограничения:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n {≤ = ≥} b₁,
a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n {≤ = ≥} b₂,

...

a_m1x₁ + a_m2x₂ + ... + a_mnx_n {≤ = ≥} b_m;

(2.2)

· требование неотрицательности:

x_j ≥ 0,

(2.3)

При этом a_ij, b_i, c_j ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.

Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

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

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b₁, b₂,..., b_m условных единиц.

Известны также технологические коэффициенты a_ij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна c_j.

В планируемом периоде значения величин a_ij, b_i и c_j остаются постоянными.

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

Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов.

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов

производственные участки	затраты времени на единицу продукции, н-час		доступный фонд времени, н-час
производственные участки	клюшки	наборы шахмат	доступный фонд времени, н-час
А	4	6	120
В	2	6	72
С	-	1	10
прибыль на единицу продукции, $	2	4

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

Обозначим: x₁ - количество выпускаемых ежедневно хоккейных клюшек, x₂ - количество выпускаемых ежедневно шахматных наборов.

Формулировка ЗЛП:

= 2x₁ + 4x₂ → max;

4x₁ + 6x₂ ≤ 120,
2x₁ + 6x₂ ≤ 72,
x₂ ≤ 10;

x₁ ≥ 0, x₂ ≥ 0.

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Повторимся, методы решения ЗЛП мы будем рассматривать чуть позднее, а сейчас - пример задачи другого типа.

2. Задача о смесях (планирование состава продукции).

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

На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

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

Представим условие задачи в таблице 2.2.

Таблица 2.2 - Исходные данные задачи о смесях

питательные вещества	содержание веществ в единице массы корма, ед.		требуемое количество в смеси, ед.
питательные вещества	корм I	корм II	требуемое количество в смеси, ед.
А	1	4	1
В	1	2	4
С	1	-	1
цена единицы массы корма, р	2	4

Cформулируем задачу линейного программирования.

Обозначим: x₁ - количество корма I в дневном рационе птицы, x₂ - количество корма II в дневном рационе птицы.

Формулировка ЗЛП:

= 3x₁ + 2x₂ → min;

x₁ + 4x₂ ≥ 1,
x₁ + 2x₂ ≥ 4,
x₁ ≥ 1;

x₁ ≥ 0, x₂ ≥ 0.

3. Транспортная задача.

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

Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (см. таблицу 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки x_ij (т.е. x_ij - количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).

Таблица 2.3 - Исходные данные транспортной задачи

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

Сформулируем ЗЛП:

= 7x₁₁ + 6x₁₂ + 4x₁₃ + 3x₂₁ + 8x₂₂ + 5x₂₃ + 2x₃₁ + 3x₃₂ + 7x₃₃ → min;

x₁₁ + x₁₂ + x₁₃ = 120,
x₂₁ + x₂₂ + x₂₃ = 100,
x₃₁ + x₃₂ + x₃₃ = 80,
x₁₁ + x₂₁ + x₃₁ = 90,
x₁₂ + x₂₂ + x₃₂ = 90,
x₁₃ + x₂₃ + x₃₃ = 120;

x_ij ≥ 0, (

, ).

2. Геометрическое решение ЗЛП

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

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

Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.

1. Сформулировать ЗЛП.

2. Построить на плоскости {х₁, х₂} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

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

5. Построить прямую c₁x₁ + c₂x₂ = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.

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

1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:

= 2x₁ + 4x₂ → max;

4x₁ +6x₂ ≤ 120,
2x₁ +6x₂ ≤ 72,
x₂ ≤ 10;

x₁ ≥ 0, x₂ ≥ 0.

2. Теперь построим прямые, соответствующие каждому из функциональных ограничений задачи (см. рисунок 2.1). Эти прямые обозначены на рисунке (1), (2) и (3).

Рисунок 2.1 - Геометрическое решение ЗЛП

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

4. Область допустимых решений включает в себя точки, для которых выполняются все ограничения задачи. В нашем случае область представляет собой пятиугольник (на рисунке обозначен ABCDO и окрашен синим цветом).

5. Прямая, соответствующая целевой функции, на рисунке представлена пунктирной линией.

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

7. Осталось вычислить координаты точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем: , . Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке .

Таким образом, для максимизации прибыли компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.

3. Основные теоремы линейного программирования

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

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

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

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

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

В частном случае, когда в систему ограничений входят только две переменные x₁ и x₂, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x₁, x₂ ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

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

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

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

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

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

4. Симплексный метод решения ЗЛП

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

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

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

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

Далее рассмотрим симплексный алгоритм, не углубляясь в его обоснование.

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

Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).

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

= c₁x₁ + c₂x₂ + ... + c_nx_n max;

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁,
a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂,

...

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m;

x_j ≥ 0,

Еще раз повторим формулировку задачи из нашего примера.

= 2x₁ + 4x₂ → max;

4x₁ +6x₂ ≤ 120,
2x₁ +6x₂ ≤ 72,
x₂ ≤ 10;

x₁ ≥ 0, x₂ ≥ 0.

Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений).

Для реализации шага в ограничения задачи вводятся дополнительные переменные. Ниже приведен порядок выполнения этой операции.

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n + y₁ = b₁,
a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n + y₂ = b₂,

...

a_m1x₁ + a_m2x₂ + ... + a_mnx_n + y_m = b_m.

Обозначим добавочные переменные несколько иначе, а именно: y₁ = x_n+1, y₂ = x_n+2, ..., y_m = x_n+m, где n - число переменных в исходной задаче, m - число уравнений.

Все дополнительные переменные также должны быть неотрицательными.

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

Выполним второй шаг для нашего примера.

4x₁ +6x₂ + x₃ = 120,
2x₁ +6x₂ + x₄ = 72,
x₂ + x₅ = 10.

Шаг 3. Построение исходной симплекс-таблицы (получение первоначального допустимого базисного решения).

При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные x_n+1, x_n+2, ..., x_n+m. Ниже приведены исходная симплексная таблица в общем виде (таблица 2.4) и в применении к рассматриваемой нами задаче (таблица 2.5).

Таблица 2.4 - Общий вид исходной симплекс-таблицы

базис	переменные							b_i
базис	x₁	x₂	...	x_n	x_n+1	...	x_n+m	b_i
x_n+1	a₁₁	a₁₂	...	a_1n	1	0	0	b₁
x_n+2	a₂₁	a₂₂	...	a_2n	0	...	0	b₂
...	...	...	...	...	...	...	...	...
x_n+m	a_m1	a_m2	...	a_mn	0	0	1	b_m
c_j	c₁	c₂	...	c_n	0	0	0	L

Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂, ..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении ( ). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 2.5 - Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах

базис	переменные					b_i
базис	x₁	x₂	x₃	x₄	x₅	b_i
x₃	4	6	1	0	0	120
x₄	2	6	0	1	0	72
x₅	0	1	0	0	1	10
c_j	2	4	0	0	0	0

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 120, x₄ = 72, x₅ = 10. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 4. Проверка условия: все c_j ≤ 0. Если НЕТ - осуществляется переход к шагу 5, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

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

В нашей задаче в качестве разрешающего выберем второй столбец (соответствующий переменной x₂), поскольку в последней строке для этого столбца содержится 4.

Информация о работе Линейное программирование