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

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .

Решение происходит в три этапа:

Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
Решение симплексным методом;

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными или зависимыми . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными или независимыми переменными .

Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом .
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной .

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Получаем новую матрицу:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Получаем новую матрицу:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Пример №2 . Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

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

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

Составной частью методов оптимизации является линейное программирование.

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

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

быть единственным для данной задачи;

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

линейно зависеть от входных параметров.

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

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

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

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

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

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

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

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

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

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

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

при условиях-ограничениях:

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

Основное содержание симплексного метода заключается в следующем:

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

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

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

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

Пример решения задачи симплексным методом

Пример 26.1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Δ k = C б X k — c k

C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

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

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод линейного программирования в экономическом анализе

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

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

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

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

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

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

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

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

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

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

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

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

Линейное программирование представляет собой один из наиболее значимых разделов математики, где осуществляется изучение теоретических и методических основ решения определенных задач. Данная математическая дисциплина широко используется в последние годы в разнообразных экономических и технических областях, где не последняя роль отведена математическому планированию и использованию автоматических систем вычисления. Этот раздел науки посвящен изучению линейных оптимизационных моделей. То есть линейное программирование посвящено числам. Впервые данный термин был предложен Т. Купмансом в 1951 году. Оптимальный план каждой линейной программы необходимо автоматически связывать с оптимальным уровнем цен, то есть с объективно обусловленными оценками.

Линейное программирование: методы

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

Если имеется математическая определенность и количественная ограниченность между изучаемыми факторами и переменными величинами;

Если имеется взаимозаменяемость факторов благодаря последовательности расчетов;

В случае если математическая логика совмещена с пониманием сущности явлений, которые изучаются.

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

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

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

Линейное программирование: задачи

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

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

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

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

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

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

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

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

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

История

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году .

Задачи

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида :

при условиях

, .

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

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

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

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

Примеры задач

Максимальное паросочетание

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

Введём переменные , которые соответствуют паре из -того юноши и -той девушки и удовлетворяют ограничениям:

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

Максимальный поток

Пусть имеется граф (с ориентированными рёбрами), в котором для каждого ребра указана его пропускная способность. И заданы две вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из истока в сток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока).

Возьмём в качестве переменных - количество жидкости, протекающих через -тое ребро. Тогда

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

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

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

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

Имеется некий однородный груз, который нужно перевести с складов на заводов. Для каждого склада известно, сколько в нём находится груза , а для каждого завода известна его потребность в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния от -го склада до -го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются - количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица размера . Первый игрок выбирает число от 1 до , второй - от 1 до . Затем они сверяют числа и первый игрок получает очков, а второй очков ( - число, выбранное первым игроком, - вторым). Нужно найти оптимальную стратегию первого игрока.

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

, , (),

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

Алгоритмы решения

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

Первый полиномиальный алгоритм , метод эллипсоидов , был предложен в 1979 году советским математиком Л. Хачияном , разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки , первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году . Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

См. также

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

Примечания

Литература

Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс», 2006. - С. 1296. - ISBN 5-8459-0857-4
Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
Карманов В. Г. Математическое программирование. - 3-е издание. - М .: Наука, 1986. - 288 с.
Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

- Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
Вершик А. М. «O Л. В. Канторовиче и линейном программировании »
Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе ».
Барсов А. С. «Что такое линейное программирование », Популярные лекции по математике , Гостехиздат, 1959.
М. Н. Вялый Линейные неравенства и комбинаторика . - МЦНМО , 2003.

Wikimedia Foundation . 2010 .

Зальтен, Феликс
Глагов, Мартина

Смотреть что такое "Линейное программирование" в других словарях:

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

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

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