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

Сервис для решения задач по линейному программированию

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

Метод Крамера
Метод Крамера использует определители для решения систем линейных уравнений.
Алгоритм калькулятора умеет использовать элементарные преобразования определителя.
Решение сопровождается большим количеством иллюстраций.
Пример №1. Решение системы линейных уравнений второго порядка методом Крамера
Пример №2. Решение системы линейных уравнений третьего порядка методом Крамера

Нахождение обратной матрицы
Обратную матрицу можно найти только для квадратной матрицы, но не каждая квадратная матрица имеет обратную.
Если матрица A -1 является обратной к исходной матрице A, то должно выполняться условие: A -1 * A = A * A -1 = E.
Калькулятор использует алгебраические дополнения для нахождения обратной матрицы.
Решение сопровождается большим количеством иллюстраций.
Пример №1. Нахождение обратной матрицы второго порядка
Пример №2. Нахождение обратной матрицы третьего порядка

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

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

Лучшее спасибо — порекомендовать эту страницу

Возникновение линейного программирования

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

Линейное программирование применяется в следующих типах задач:

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

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

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

Практический пример применения графического метода

Пусть введена линейная функция $Y=3X+4Z$ при этом переменные подчиняются следующим ограничениям: $$ \left\< \begin 0 \le X \le 6,\\ 0 \le Z \le 4. \end \right. $$ Найдем значения $X$ и $Z$, при которых $Y$ будет максимальным. Строим математическую модель: $$Y=3X+4Z \rightarrow \max,$$ $$ \left\< \begin 0 \le X \le 6,\\ 0 \le Z \le 4. \end \right. $$ Рисуем прямую линию $3X+4Z=0$ или $Z=-3/4 X$. Параллельным переносом в направлении градиента этой функции $n=(3,4)$ к правой верхней вершине полученного прямоугольника допустимых решений мы получим точку $(6,4)$. В этой точке функция $Y$ имеет максимальное значение, равное $Y_=34$. Другие более подробные примеры по разным темам собраны на странице: Задачи линейного программирования с решениями онлайн.

Полезная страница? Сохрани или расскажи друзьям

• Контрольные по линейному программированию на заказ
• Учебники и ссылки по линейному программированию

Решение задач линейного программирования

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

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

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

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

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

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

F(x) → min

F(x) → max

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

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

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

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

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

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

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

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

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

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

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

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

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

Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х₁ + 5Х₂ ≤ 10, то, очевидно, 0 ≤ Х₁ ≤ 10/2 = 5 и 0 ≤ Х₂ ≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его «обращенную» к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10 n последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10 n .)

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно — т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка — в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример со стр.208 книги [3].

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

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

В соответствии с симплекс-методом введем т.н. «свободные переменные» Х₄ , Х₅ , Х₆ , соответствующие недоиспользованным мощностям, т.е. перейдем к системе уравнений:

У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:

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

Выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х₁ .

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х₁:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

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

Умножим первую строку на 200, чтобы получить Х₁ с единичным коэффициентом:

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F, получим:

В результате система уравнений преобразуется к виду, в котором переменная Х₁ входит только в первое уравнение:

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее вершине в шестимерном пространстве:

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

Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент — при Х₂ (если бы положительных коэффициентов было несколько — мы взяли бы максимальный из них). На основе коэффициентов при Х₂ (а не при Х₁, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х₂ равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х₂ , предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х₂ стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

— 85/7 Х₃ — 19800/7 Х₄ — 1800/7 Х₅ = F — 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х₃ = Х₄ = Х₅ = 0. Из остальных уравнений следует, что при этом Х₁ = 120000/7 = 17143, Х₂ = 30000/7 = 4286, Х₆ = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.

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

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

В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать «прикрепление» потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 5.

Табл. 5. Исходные данные к транспортной задаче.