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

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

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. Исходные данные к транспортной задаче.

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

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции 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

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

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

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

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

Ваша ссылка очень поможет сайту. Заранее спасибо.

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

Задача линейного программирования: основные определения

Линейное программирование – метод решения задач оптимизации.

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

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

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

Или в сокращённом виде с сигмой:

Можно встретить обозначение целевой функции и через C, и через F.

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

Или в сокращённом виде:

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

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

Задачей линейного программирования в стандартной, или, как говорят иначе, нормальной форме, называется задача, в которой требуется найти максимум целевой функции при ограничениях, заданных системой неравенств одного смысла, то есть с одинаковым знаком, и этот знак — «меньше или равно», причём действует также условие неотрицательности переменных. Если в задаче линейного программирования, заданной в стандартной форме, требуется найти минимум целевой функции, то система ограничений состоит из системы неравенств со знаком «больше или равно».

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

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

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

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

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

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

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

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

Примеры формулировки задачи линейного программирования

Разберём несколько типов экономических задач и запишем их в виде математических соотношений. Или, говоря иначе, построим математическую модель предметной области.

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

Целевая функция. Её нужно максимизировать или минимизировать. Для того, чтобы функцию максимизировать, переменные, являющиеся её слагаемыми, должны принимать как можно большие значения в соответствии с условиями задачи. При минимизации — наоборот, меньшие. Обычно целевая функция выражает доходы или расходы.

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

Ограничения. Очень просто. Например, в каждом уравнении (неравенстве) заданы ограничения перечисленных выше или других запасов, используемых для производства определённого вида продукции.

Пример 1. Схема задачи использования сырья.

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

Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья — соответственно , , , единицы.

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

Решение. Для удобства сначала все данные запишем в виде таблицы:

Виды сырья	Запасы сырья	Виды продукции
		Доход от реализации одной единицы продукции

Тогда на основании таблицы запишутся неравенства (ограничения):

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

Из остальных строк таблицы составим ещё 3 неравенства системы.

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

Пример 2. Схема задачи о смесях.

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

Требуется найти наиболее дешёвый набор из доступных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в свойм составе n различных компонент в определённых количествах, а сами компоненты являются составными частями m исходных материалов. Для упрощения примем, что n=3 и m=4. Пусть стоимость одной единицы материала соответственно составляет , , , . В свою очередь необходимое количество каждой из компонент в смеси составляет соответственно , , .

Решение. Строим таблицу:

Виды материалов	Цена единицы материала	Количество компонент в материале
		K 1	K 2	K 3
1
2
3
4
Необходимое количество компонент

Коэффициенты a ij показывают количество j-й компоненты в единице i-го материала K 1 . Требуется получить смесь с заданными свойствами при наименьших затратах на приобретение материалов.

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

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

Пример 3. Схема задачи о питании.

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

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

Решение. Строим таблицу:

Питательные вещества	Норма	Продукты
		Ж
Б
У
В
Стоимость питательных веществ

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

Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта — буквой , количество продукта — буквой .

Получим систему неравенств (ограничений):

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

Пример 4. Схема задачи об использовании мощностей оборудования.

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

Предприятию требуется за время T выпустить N 1 единиц продукции П 1 и N 2 единиц продукции П 2 . Каждый из этих двух видов продукции может производиться тремя машинами A, B, C . Составить оптимальный план работы машин, то есть найти время загрузки машин A, B, C , с тем расчётом, чтобы стоимость изготовления всей продукции предприятием оказалась минимальной.

Мощность машин задана следующей таблицей:

Машины	П 1	П 2
A
B
C

В этой таблице — количество единиц продукции, производимое за единицу времени.

Цена одной единицы рабочего времени на изготовление одной единицы продукции на каждой машине задана следующей таблицей:

Машины	П 1	П 2
A
B
C

В этой таблице, например, число означает цену одной единицы рабочего времени машины B , затрачиваемой на изготовление одной единицы продукции П 1 .

Запишем задачу в виде математических соотношений. Неизвестным является время загрузки машин по производству продукции. Обозначим через время загрузки машины A по изготовлению продукции П 1 , через — время загрузки машины A по изготовлению продукции П 2 . Аналогично — время загрузки машины B по изготовлению продукции П 1 , — время загрузки машины B по изготовлению продукции П 2 , — время загрузки машины C по изготовлению продукции П 1 , время загрузки машины C по изготовлению продукции П 2 .

Машины A, B, C работают одновременно, значит если обозначим время одновременной работы всех трёх машин буквой T , то получим систему неравенств:

Машина A изготовлением продукции П 1 занята единицы времени на единицы продукции. Машина B изготовлением П 1 занята единицы времени по единицы продукции.

Аналогично машина C изготовлением П 1 занята единицы времени, по единицы продукции и т.д. Всего нужно N 1 единиц продукции П 1 и N 2 единицы П 2 .

То есть получаем ещё одну систему:

Тогда общая стоимость всей продукции запишется в виде равенства:

Окончательно получаем систему ограничений, состоящую из соотношений:

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

Пример 5. Транспортная задача (схема).

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

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

Составить такой план перевозок, чтобы общая стоимость всех перевозок была минимальной.

Решение. Считаем, что запас всего груза на обоих пунктах отправления равен потребности в этом грузе на всех трёх пунктах назначения, т. е.

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

Пункт отправления	Пункт назначения			Запас груза
	Потребность в грузе

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

Тогда система ограничений запишется в виде уравнений:

Цель задачи — найти неотрицательное решение системы уравнений, при котором функция цели была минимальной.

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

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

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

Пример 6. Записать систему неравенств

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

Решение. Прибавляя к левым частям неравенств по одной дополнительной переменной, получим систему уравнений:

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

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

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

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

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

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

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

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

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

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

Справедливость этого утверждения вытекает из теорем 2 и 4.

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

Продолжение темы «Линейное программирование»

• Графический метод решения задач линейного программирования
• Пример задачи линейного программирования: задача использования ресурсов, её графическое решение
• Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм
• Симплекс-метод: случай, когда максимум целевой функции — бесконечность
• Симплекс-метод: случай, когда система не имеет ни одного решения
• Симплекс-метод: случай, когда оптимальное решение — не единственное
• Двойственная задача линейного программирования
• Решение задачи целочисленного программирования: методы и примеры
• Решение транспортной задачи распределительным методом на примерах