-
Графический метод решения задачи линейного программирования
Графическим
методом
решается стандартная задача линейного
программирования:
,
,
.
Данный метод
основан на приведенной выше геометрической
интерпретации задачи ЛП. Нахождение
решения задачи ЛП графическим методом
имеет следующие этапы:
-
Строят
прямые (8), уравнения которых получаются
в результате замены в ограничениях
знаков неравенств на знаки точных
равенств. -
Находят полуплоскости,
определяемые каждым из ограничений
задачи. -
Находят многоугольник
решений как пересечение всех полуплоскостей -
Строят
начальную прямую (линию уровня целевой
функции), проходящую через начало
координат
. -
Строят
вектор
,
представляемый градиент целевой функции
(5). -
Движением
прямой
— const
параллельно
самой себе в направлении вектора
либо находят точки, в которой целевая
функция принимает наибольшее (наименьшее)
значение, либо устанавливают
неограниченность сверху (снизу) целевой
функции на множестве планов. -
Определяют
координаты точки максимума (минимума)
целевой функции и вычисляют ее значение
в этих точках.
.
,
— const
либо находят точки, в которой целевая
Пример.
Найти
наибольшее и наименьшее значения целевой
функции z
при заданных ограничениях:
-
Строят прямые,
уравнения которых получаются в результате
замены в ограничениях знаков неравенств
на знаки точных равенств:
-
Каждое
ограничение-неравенство определяет
координатную полуплоскость. В зависимости
от знака неравенств при помощи двух
стрелок укажем требуемые полуплоскости. -
В
результате пересечения всех полуплоскостей
находят многоугольник решений (на
рисунке обозначен треугольником ABC). -
Построим
начальную прямую (линию уровня целевой
функции), проходящую через начало
координат
. -
Движением
прямой
параллельно
самой себе в направлении вектора
находим два крайних положения. Первое
соответствует минимуму целевой функции
(точка А), второе — максимуму (точка С).
.
находим два крайних положения. Первое
Рис.6. Графическая
интерпретация задачи линейного
программирования
-
Определим
координаты точек максимума и минимума
целевой функции и вычислим их значения
в найденных точках.
Максимальное
значение целевой функции
.
Вообще,
с помощью графического метода может
быть решена задача ЛП, система ограничений
которой содержит n
неизвестных и m
линейно-независимых уравнений, если n
и
m
связаны соотношением
.
Действительно,
пусть поставлена каноническая задача
ЛП: найти наибольшее значение
(12)
при условиях
,
(13),
,
(14),
где
все уравнения (13) линейно независимы, и
выполняется соотношение
.
Используя
метод Жордана-Гаусса, производим m
исключений, в результате которых система
ограничений примет вид:
,
,
.
(15)
Учитывая
неравенства (14), эту систему уравнений
можно записать в виде системы неравенств
,
,
,
.
Исключая
из (12) при помощи уравнений (15), получим
,
т.е. задачу вида (5-7).
-
Симплекс — метод решения задач линейного программирования
Введение.
Предположим, что
поставлена стандартная задача ЛП:
,
,
,
(16)
,
.
Каждое
из условий типа неравенства определяет
полупространство, ограниченное
гиперплоскостью (плоскостью в k-мерном
пространстве). Пересечение соответствующих
полупространств образует выпуклый
многогранник (область допустимых решений
— ОДР), в котором необходимо найти максимум
(минимум) целевой функции. Внутри
многогранника условий в силу его
выпуклости линейная функция z
не может достигать максимума (минимума).
Её максимум (минимум), если он существует,
достигается обязательно в какой-нибудь
вершине многогранника или на одном из
его граней.
Теоретически
задача ЛП проста. Достаточно найти
конечное число вершин многогранника и
вычислить в них значения целевой функции.
Из всех этих значений выбрать то, которое
соответствует оптимальному решению.
Однако
простой перебор даже при использовании
самых современных ЭВМ практически
неосуществим из-за чрезвычайно большого
числа вершин. Поэтому возникла
необходимость применения методов
целенаправленного перебора, которые
приводят к решению задачи за приемлемое
время. Одним из таких методов является
симплекс-метод.
Симплексом
называется простейший выпуклый
многогранник. Решение задачи ЛП
симплекс-методом состоит в определении
одной из вершин многогранника условий
и последовательном переходе от одной
вершины к другой, причем каждый такой
переход приближает решение к оптимальному.
В этом заключается геометрический смысл
симплекс-метода.
Рассмотрим
каноническую задачу линейного
программирования:
,
,
, (17)
,
.
Здесь
систему ограничений представляет
система m
линейно независимых уравнений. Эта
система линейных уравнений имеет
бесконечное число решений. При этом
(n—m)
переменных могут принимать произвольные
значения (свободные переменные), а
остальные m
переменных выражаются через них (базисные
переменные).
Определение
7. Решение,
при котором все свободные переменные
равны нулю, называются базисным
решением.
Очевидно, что не
всякое базисное решение является
допустимым, т.е. принадлежит многограннику
условий, так как необходимо учесть
последние условия неотрицательности
всех переменных из (17).
Определение
8. Базисное
решение, удовлетворяющее условиям
неотрицательности всех переменных,
называется допустимым
базисным решением, или
опорным планом.
Определение
9. Опорный
план называется невырожденным,
если он содержит ровно m
положительных компонент, в противном
случае, он называется вырожденным.
На
каждой грани многогранника условий
какая-либо переменная тождественно
равна нулю. Например, из (16), (18) видно,
что гиперплоскость
,
которая, возможно, является одной из
сторон многогранника условий, соответствует
условию
.
Поэтому в каждой вершине многогранника
условий обращаются в нуль ровно столько
переменных, сколько свободных. Таким
образом, допустимое решение, соответствующее
какой-либо вершине многогранника
условий, необходимо искать среди
множества базисных решений.
Алгоритм
симплекс-метода.
Первоначально
задача ЛП записывается в канонической
форме (17), и находится произвольное
базисное решение. Если решение
недопустимое, то проверяется совместность
ограничений, и, в случае совместности,
из базиса вычеркивается определенная
переменная, а вместо неё вводится другая.
Тем самым, находится новое базисное
решение. Если же базисное решение
допустимое (т.е. найден опорный план,
соответствующий одной из вершин
многогранника условий), то решение
проверяется на оптимальность. В случае
неоптимальности допустимого базисного
решения, устанавливается ограниченность
целевой функции, и вновь производится
обмен между базисными и свободными
переменными, который геометрически
означает переход к другой вершине
многогранника.
В
результате многократного повторения
указанного процесса, либо будет получено
оптимальное решение, либо будет выявлена
противоречивость ограничений
(несуществование ОДР), либо будет видно,
что целевая функция неограничена.
Алгоритм
симплекс-метода представлен при помощи
блочных структур на рис.7.
При
решении задачи симплекс-методом удобно
пользоваться так называемыми
симплекс-таблицами. Приведем некоторые
пояснения к алгоритму нахождения
оптимального решения, основанного на
последовательных переходах от одной
симплекс-таблицы к другой.
Представление
исходных данных задачи в виде
симплекс-таблицы (первая симплекс-таблица).
Для получения симплекс-таблицы общую
или стандартную задачу ЛП необходимо
привести в канонический вид и разрешить
систему линейных уравнений (например,
методом Гаусса-Жордана) относительно
выделенных базисных переменных. Далее,
следует при помощи выражений для базисных
переменных выразить целевую функцию
через свободные переменные.
При
составлении первой симплекс-таблицы
на основе разрешенной системы линейных
уравнений, свободные члены записываются
без изменения знаков, а коэффициенты
при свободных переменных — с противоположными
знаками. Предположим для определенности,
дана стандартная задача ЛП в виде (16).
Введя дополнительные неотрицательные
переменные
,
получим соответствующую каноническую
задачу ЛП:
,
,
, (18)
,
.
Предполагая,
что
и равенство нулю некоторых
,
эту задачу можно записать в виде (17).
В
данном случае удобно в качестве базисных
переменных выбрать
,
относительно которых легко решить
систему уравнений. Поэтому из (18) следует
,
,
, (19)
,
,
где
,
,
.
Из
такой записи канонической задачи ЛП
составляют симплекс-таблицу (см. Таб.1).
В дальнейшем эта
таблица подвергается анализу, и в случае
необходимости проводится такое
преобразование, когда одна переменная
из свободных переходит в базисные, а
одна базисная – в свободные.
Таб.1.
Составление первой симплекс-таблицы
|
Базисные |
Свободные члены |
Свободные |
||||
|
|
… |
|
… |
|
||
|
|
|
|
… |
|
… |
|
|
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
… |
|
… |
|
|
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
… |
|
… |
|
|
Целевая |
|
|
… |
|
… |
|
Нахождение
базисного решения.
В базисном решении все свободные
переменные равны нулю, и поэтому базисные
переменные равны свободным членам (см.
(19) и Таб.1):
.
Проверка
допустимости базисного решения.
Признак
1. (Признак допустимости базисного
решения).
Решение будет допустимым, если в
симплекс-таблице все свободные члены
(кроме строки целевой функции)
неотрицательные.
Проверка
совместности ограничений.
Если базисное решение недопустимо, то
необходимое проверить совместность
ограничений, т.е. наличие ОДР. Геометрическая
интерпретация несовместности ограничений
показана на рис.5.
Признак
2. (Признак несовместности ограничений).
Ограничения несовместны, если в любой
строке (кроме строки целевой функции),
имеющей отрицательный свободный член,
нет ни одного отрицательного элемента.
Наличие отрицательного элемента дает
возможность произвести такой обмен
переменных, когда новая базисная
переменная возможно станет неотрицательной.
Если несовместность
по изложенному признаку не выявлена,
то необходимо произвести преобразование
симплекс-таблицы (обмен переменных),
цель которого нахождение нового базисного
решения.
Проверка
оптимальности решения.
Если базисное решение допустимое, то
решение проверяется на оптимальность
с помощью следующего признака.
Признак
3. (Признак оптимальности решения).
Целевая функция будет иметь максимальное
(минимальное)
значение, если в строке целевой
функции все элементы, кроме свободного
члена, положительные
(отрицательные).
Проверка
ограниченности целевой функции.
Если допустимое базисное решение
неоптимальное, то необходимо проверить
существование оптимального решения,
т.е. ограниченности целевой функции.
Геометрическая интерпретация
неограниченности целевой функции
показана на рис.4.
Признак
4. (Признак ограниченности целевой
функции).
Целевая функция ограничена сверху
(снизу), т.е. существует максимальное
(минимальное) значение целевой функции,
если на каждой итерации в каждом столбце,
не удовлетворяющем признаку оптимальности,
есть хотя бы один положительный элемент.
Если не выявлено
несуществование оптимального решения
по этому признаку, то итерацию необходимо
повторить, т.е. преобразованием
симплекс-таблицы перейти к новому
базисному решению.
Проверка
неединственности решения.
Признак
5. (Признак неединственности оптимального
решения).
Если в строке целевой функции оптимального
решения, кроме столбца свободных членов,
есть хотя бы один нулевой элемент, то
полученное оптимальное решение является
неединственным.
Это
означает, что есть другой набор значений
переменных, при котором целевая функция
будет иметь такое же оптимальное
значение.
Таким
образом, анализ симплекс-таблицы может
привести к необходимости её преобразования,
переходу к новому базисному решению.
Для этого необходимо найти разрешающий
элемент.
Нахождение
разрешающего элемента.
Разрешающий элемент указывает одну
свободную и одну базисную переменные,
которые следует обменять, чтобы получить
новое “улучшенное” базисное решение.
Шаг 1. Нахождение
разрешающего столбца.
-
базисное
решение недопустимое, ограничения
совместны.
В
строке, содержащей отрицательный
свободный член, выбирается отрицательный
элемент. Столбец, в котором находится
выбранный элемент, принимается в качестве
разрешающего.
-
базисное
решение допустимое, неоптимальное.
В
качестве разрешающего столбца принимается
любой столбец, неудовлетворяющий
признаку оптимальности.
Шаг
2. Нахождение разрешающей строки.
Определяются
положительные отношения свободных
членов к элементам разрешающего столбца
,
,
гдеl
– число строк, в которых
имеют одинаковый знак. В качестве
разрешающей, выбирается та строка, для
которой найденное значение минимальное,
т.е.
.
Разрешающие строка
и столбец в Таб.1 помечены стрелками,
разрешающий элемент выделен рамкой.
Замечание.
Если выбор разрешающего элемента
неоднозначный, то можно выбрать любой
из них. Это может несущественно повлиять
лишь на количество итераций, но не влияет
на оптимальное решение. Обеспечение
минимального количества итераций здесь
не рассматривается, однако, рекомендуется
выбрать наименьший, если элемент
отрицательный и наибольший, если
выбираемый элемент положительный.
Преобразование
симплекс-таблицы.
Как уже отмечалось, преобразование
симплекс-таблицы заключается в обмене
переменных. Предположим, что разрешающий
элемент является
,
который выделен рамкой в Таб.1. Тогда
базисную переменную
необходимо перевести всвободные,
а свободную переменную
— в базисные.Переход
от одной таблицы к другой выполняется
по следующему алгоритму.
Шаг
1. Ячейка
разрешающего элемента заполняется
значением
,
обратным значению разрешающего элемента.
Шаг
2. Ячейки
разрешающей строки заполняются
элементами, стоящими в этих ячейках,
деленными на разрешающий элемент, т.е.
,
,
,
.
(20)
Шаг
3. Ячейки
разрешающего столбца заполняются
элементами, стоящими в этих ячейках,
деленными на разрешающий элемент с
обратным знаком, т.е.
,
,
,
.
(21)
Шаг
4. Остальные
ячейки
,
,
заполняются значениями, стоящими в этих
ячейках, минус произведение элементов,
стоящих в соответствующем разрешающем
столбце и в соответствующей разрешающей
строке, деленное на разрешающий элемент,
т.е.
,
,
(22)
,
,
,
,
,
.
В
силу того, что на шаге 3 значения элементов
пересчитанного разрешающего столбца
уже определены, то вычисления по формулам
(22) можно сократить.
В
результате преобразования получим
новую симплекс-таблицу (Таб.2).
Таб.2.
Преобразование симплекс-таблицы
|
Базисные переменные |
Свободные члены |
Свободные |
||||
|
|
… |
|
… |
|
||
|
|
|
|
… |
|
… |
|
|
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
… |
|
… |
|
|
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
… |
|
… |
|
|
Целевая |
|
|
… |
|
… |
|
Пример.
Найти
наибольшее значение целевой функции z
при заданных ограничениях:
Исходную
стандартную задачу линейного
программирования (СЗЛП) приведем к
каноническому виду (КЗЛП). Для этого
введем дополнительные переменные,
учитывая знаки неравенств-ограничений.
Если ограничение-неравенство имеет
знак «≥»,
то
дополнительную переменную вводим со
знаком «-», в противном случае – со
знаком «+».
СЗЛП
КЗЛП
В
качестве базисных переменных удобно
выбрать
,
так как относительно этих переменных
легко решить систему линейных уравнений:
— базисные переменные;
— свободные переменные.
Составим
первую симплекс-таблицу: свободные
члены записываем без изменения знаков,
а коэффициенты при свободных переменных
– с противоположными знаками.
|
Базисные |
Свободные |
Свободные |
|
|
x1 |
x2 |
||
|
x3 |
-9 |
-3 |
1 |
|
x4 |
50 |
2 |
3 |
|
x5 |
-18 |
1 |
— |
|
Z |
0 |
-6 |
-1 |
4
Базисное
решение
— недопустимое, т.к. имеются отрицательные
элементы (
).
Данная симплекс-таблица соответствует
точке начала координат на рис.6. Ограничения
совместны, т.к. в строках с отрицательными
свободными членами имеются ещё
отрицательные элементы. Необходимо
найти разрешающий элемент и провести
преобразование симплекс-таблицы.
Найдём
разрешающий элемент. Выберем наименьший
отрицательный элемент в строках с
отрицательными свободными членами. Это
-4.
Столбец, в котором находится этот элемент
(
),
принимаем в качестве разрешающего
столбца (помечен стрелкой).
Для
нахождения разрешающей строки определяем
минимальное положительное отношение
свободных членов к элементам разрешающего
столбца. Так как
,
то в качестве разрешающей строки получаем
.
Элемент,
находящийся на пересечении разрешающих
столбца и строки, является разрешающим
элементом (выделен рамкой). Он указывает,
что базисную переменную
переводим в свободные, а свободную
переменную
— в базисные.
Преобразуем
симплекс-таблицу, используя правила
преобразования:
-
Ячейку
разрешающего элемента, равного «-4»,
заполняем значением, обратным значению
разрешающего элемента (-1/4=-0,25). -
Ячейки
разрешающей строки
заполняем элементами, стоящими в этих
ячейках, деленными на разрешающий
элемент «-4». Например, элемент, находящийся
на пересечении столбца свободных членов
и строки,
будет равен
. -
Ячейки
разрешающего столбца заполняем
элементами, стоящими в этих ячейках,
деленными на разрешающий элемент с
обратным знаком «4». В частности, элемент,
находящийся на пересечении столбца
и строки
,
будет равен
. -
Остальные
ячейки заполняем значениями, стоящими
в этих ячейках, минус произведение
элементов, стоящих в соответствующем
разрешающем столбце и в соответствующей
разрешающей строке, деленное на
разрешающий элемент «-4». Например,
элемент, находящийся на пересечении
столбца свободных членов и строки
,
будет равен
.
заполняем элементами, стоящими в этих
,
.
и строки
,
.
,
.
В
результате преобразования симплекс-таблицы
получим:
|
Базисные |
Свободные |
Свободные |
|
|
x1 |
x5 |
||
|
x3 |
|
|
|
|
x4 |
|
|
|
|
x2 |
|
|
|
|
Z |
|
|
|
Базисное
решение
— недопустимое, т.к. есть отрицательный
элемент (
).
Ограничения совместны, т.к. в строке с
отрицательным свободным членом имеется
ещё отрицательный элемент.
В
качестве разрешающего столбца выбираем
столбец
.
Вычисляя
,
получаем, что в качестве разрешающей
строки следует выбрать
.
Базисную переменную
переводим в свободные, а свободную
переменную
— в базисные.
В
результате преобразования симплекс-таблицы
получили следующую таблицу:
|
Базисные |
Свободные |
Свободные |
|
|
x3 |
x5 |
||
|
x1 |
|
|
|
|
x4 |
23 |
1 |
1 |
|
x2 |
|
|
|
|
Z |
|
|
|
Базисное
решение
— допустимое, т.к. все свободные члены
положительные. Решение оптимальное
(минимум целевой функции), поскольку в
строке целевой функции, кроме столбца
свободных членов, все элементы одного
знака (отрицательные). Оптимальное
решение единственное, т.к. в строке
целевой функции нет нулевых элементов.
Данная симплекс-таблица соответствует
точке А на рис.6.
Но поскольку
требуется найти максимальное значение
целевой функции, то итерации продолжаются.
В
качестве разрешающего столбца можно
выбрать любой столбец таблицы, т.к. они
оба не удовлетворяют признаку оптимальности
(максимуму). Выбираем столбец
.
Тогда разрешающей строкой будет строка
,
т.к.
.
В результате
преобразований получим следующую
симплекс-таблицу:
Таб.3.
Симплекс-таблица оптимального решения
|
Базисные |
Свободные |
Свободные |
|
|
x4 |
x5 |
||
|
x1 |
|
|
|
|
x3 |
23 |
1 |
1 |
|
x2 |
|
|
|
|
Z |
|
|
|
Базисное
решение
— допустимое, т.к. все свободные члены
положительные. Решение оптимальное
(максимум целевой функции), поскольку
в строке целевой функции все элементы
одного знака (положительные). Оптимальное
решение единственное, т.к. в строке
целевой функции нет нулевых элементов.
Данная симплекс-таблица соответствует
точке С на рис.6.
Таким
образом, наибольшее значение
целевая функция имеет при
.
Для решения задач линейного программирования разработано множество методов, но наиболее популярными из них являются графический, симплексный и двойственный методы, которые мы и рассмотрим далее в нашей исследовательской работе.
Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!
Возможно эта страница вам будет полезна:
Графический метод решения задач линейного программирования
Рассмотрим задачу линейного программирования в стандартной форме записи с двумя переменными
при условиях:
Необходимо найти вектор 
, удовлетворяющий данной математической модели.
При решении, прежде всего, необходимо найти область допустимых решений системы неравенств (3.2). Рассмотрим декартову систему координат 
. Заменив каждое из неравенств (3.2) равенством, строим соответствующую ему граничную прямую 
. На рисунке 1 видно, как эта прямая делит плоскость на две полуплоскости [3].
Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости (
) (например, начало координат) и подставить в неравенство числа . Если оно удовлетворится, то полуплоскость, в которой лежит данная точка — искомая. В противном случае нужная полуплоскость лежит по другую сторону прямой 
[26].
Для нахождения области допустимых решений строим граничные прямые полуплоскости, соответствующие всем неравенствам. Общая часть («пересечение») всех этих полуплоскостей будет решением системы неравенств данной задачи.
При нахождении области допустимых решений (ОДР) задачи линейного программирования может встретиться один из четырех случаев, рассмотренных в таблице 4:
Рассмотренные примеры позволяют сделать вывод о том, что область допустимых решений системы неравенств может быть пустой, одной точкой, выпуклым многоугольником или неограниченной выпуклой областью.
Согласно теореме, описанной в предыдущем параграфе, оптимальное решение ЗЛП находится в одной из угловых точек многоугольника допустимых решений. Поэтому решение задачи с ограниченной целевой функцией и не слишком большим числом угловых точек может быть найдено перебором этих угловых точек.
Рассмотрим целевую функцию
Уравнение
при фиксированном значении 
определяет прямую, а при изменении — семейство параллельных прямых с параметром . Вдоль каждой из этих прямых функция цели принимает одно и то же фиксированное значение, поэтому эти линии называют линиями уровня целевой функции [24].
Для решения задачи необходимо среди точек области допустимых решений найти такую точку (точки), в которой целевая функция принимает максимальное значение.
Для этого построим вектор-градиент 
, компонентами которого являются коэффициенты при неизвестных целевой функции, и линию уровня целевой функции, которая имеет уравнение 
и обладает тем свойством, что она перпендикулярна вектору 
.
Линию уровня в направлении вектора перемещаем до тех пор, пока она не сместится в область недопустимых значений, и все еще будет иметь одну общую точку с ОДР, координаты которой находим из пересечения соответствующих прямых [5].
Таким образом, можно определить алгоритм геометрического (графического) решения задач линейного программирования:
- Записать уравнения прямых, соответствующих ограничениям, и построить их на плоскости
. - Определить области, в которых выполняются ограничения задачи.
- Определить область допустимых решений задачи как область пересечения полуплоскостей, соответствующих ограничениям задачи.
- Определить направление возрастания (убывания) целевой функции
- Определить граничную точку или точки области допустимых решений, в которых целевая функция принимает максимальное (минимальное) значение.
- Определить координаты найденной точки, решая систему уравнений, состоящую из уравнений прямых, на пересечении которых находится эта точка, или выявляя уравнение граничной прямой области допустимых решений, с которой совпадает линия уровня целевой функции.
.
полуплоскостей, соответствующих ограничениям задачи.
Графический метод решения задачи линейного программирования состоит из двух этапов:
- Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.
- Поиск оптимального решения среди всех точек пространства допустимых решений.
Применение графического метода удобнее рассмотреть на конкретных примерах в двух постановках: для максимума и минимума целевой функции.
Примеры с решением
Пример решения задачи №1:
Задана стандартная математическая модель задачи с двумя неизвестными:
Нахождение решения этой модели на основе ее геометрической интерпретации включает следующие этапы.
- В плоскости строят прямые, уравнения которых получаются в результате замены в ограничениях (2.1) модели знаков неравенств на знаки точных равенств.
- Находят полуплоскости, определенные каждым неравенством системы.
- Находят выпуклый многоугольник решений всей системы (2.1).
- Строят нормальный вектор целевой функции , причем, начало вектора совмещают с началом координат и строят прямую .
- Передвигают эту прямую в направлении вектора , в результате либо находят вершину или отрезок, в которой целевая функция принимает наибольшее значение, либо устанавливают неограниченность сверху этой функции на множестве допустимых решений.
- Если функция ограничена, то определяют , вычисляют значение функции в этой точке .
строят прямые, уравнения которых получаются в результате замены в ограничениях (2.1) модели знаков неравенств на знаки точных равенств.
, причем, начало вектора совмещают с началом координат и строят прямую 
.
, в результате либо находят вершину или отрезок, в которой целевая функция принимает наибольшее значение, либо устанавливают неограниченность сверху этой функции на множестве допустимых решений.
, вычисляют значение функции в этой точке При геометрической интерпретации задач ЛП могут встретиться случаи, изображенные на рис. 2.1. — 2.4.
Рис. 2.1. Задача ЛП имеет единственное решение 
.
Рис. 2.2. Задача ЛП имеет бесчисленное множество решений, т.к. целевая функция достигает максимума на отрезке 
.
Рис. 2.3. Задача ЛП не имеет решения, т.к. функция неограниченна сверху.
Рис. 2.4. Задача ЛП не имеет решения, т.к. система (2.1) несовместна.
Пример решения задачи №2:
Для производства двух видов изделий 
и 
предприятие использует три вида сырья 
. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. 2.1.
Прибыль от реализации одного изделия каждого вида равна 
и 
, а общее количество сырья вида 
равно 
. Считая, что изделия и могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий будет максимальной.
Решение. Обозначим через 
и 
количество изделий первого и второго вида в плане предприятия. Поскольку производство продукции ограничено только сырьем каждого типа то получим условия:
Переменные и не могут быть отрицательными по смыслу задачи. Вычислим прибыль от реализации продукции и получим:
Итак, мы получили стандартную модель с двумя переменными.
Решим задачу линейного программирования геометрически, придерживаясь плана, приведенного ранее.
- Строим прямые :
:
Обратимся к неравенствам (2.3). Отмстим те полуплоскости, которые им удовлетворяют. Учтем на чертеже и неотрицательность переменных и , и получим многоугольник 
решений данной системы неравенств (см. рис. 2.5).
- Запишем окончательный ответ:
Наибольшая прибыль будет равна 1080 (у.е).
Пример решения задачи №3:
Минимизировать функцию
при ограничениях 
Допустимой областью, изображенной на рис. 1.2, является чегырехугольник 
. Два последних ограничения усиливают условия неотрицательности. Функция 
убывает в направлении вектора
Минимальное значение функции = — 68 и достигается в точке 
= (12,8). Заметим, что, как и в примере разд. 1.1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является точках = 2, = 8 с минимальным значением функции = — 68.
Иногда задача имеет более чем одно оптимальное решение.
Пример решения задачи №4:
Минимизировать функцию
при ограничениях
На рис. 1.3 чегырехугольник 
изображает допустимую область 
, 
, и, таким образом, вектор 
указывает направление убывания функции .
Любая точка на отрезке 
является оптимальным решением. В частности, в вершинах 
достигаются оптимальные решения, соответствующие одному и тому же минимальному значению функции =-12.
Любая точка на отрезке представляется формулой
где
Для каждой такой точки значение функции равно
Функция имеет единственное минимальное значение.
Иногда решение задачи не ограничено.
Пример решения задачи №5:
Максимизировать функцию
при ограничениях
Допустимая область, изображенная на рис. 1.4, не ограничена в направлении, в котором функция возрастает, т. е. в допустимой области не существует конечной точки, в которой функция достигала бы максимума. Решение, как и максимальное значение функции , не ограничено. Однако некоторые задачи с неограниченными допустимыми областями имеют конечные решения. Например, задача максимизации функции 
при ограничениях из примера 3 имеет конечное решение.
Разумеется, если бы задача состояла в минимизации функции 
, при тех же ограничениях, то минимум достигался бы в единственной точке 
в вершине допустимой области 
.
Иногда задача не имеет решения, поскольку допустимой области не существует.
Пример решения задачи №6:
Минимизировать функцию
при ограничениях
Ограничения задачи противоречивы, поэтому нет допустимых решений (рис. 1.5).
Уже из рассмотренных выше примеров можно вывести несколько характерных черт задач линейного программирования. Во-первых, допустимая область всегда является выпуклым многоугольником, даже в случае, когда она не ограничена. Во-вторых, оптимальное решение всегда достигается в вершинах допустимой области. В примере 2 и вершина 
, и вершина 
являются оптимальными точками.
Эти результаты могут быть обобщены. Сначала покажем, что задачи линейного программирования могут быть приведены к стандартной форме.
Пример решения задачи №7:
Найти максимум функции 
при ограничениях
На рис. 3 изображены: неограниченная многогранная область решений данной системы ограничений-неравенств, линия уровня 
, вектор 
. Функция 
может неограниченно возрастать при заданной системе ограничений, поэтому 
.
Пример решения задачи №8:
Найти максимум функции 
при ограничениях
Изображенная на рис. 4 область не содержит ни одной общей точки, которая удовлетворяла бы всем неравенствам системы ограничений, т.е. система ограничений противоречива и не может содержать ни одного решения, в том числе и оптимального.
Пример решения задачи №9:
Найти максимум функции при ограничениях
Всем неравенствам системы ограничений удовлетворяют точки треугольника 
, который и является областью решений (рис. 5). Максимальное значение 
. При построении треугольника не использовали прямые 
, хотя все точки этого треугольника удовлетворяют неравенствам 
. Таким образом, эти неравенства лишние в системе ограничений.
Пример решения задачи №10:
Найти минимум функции 
при ограничениях
Областью решений данной системы ограничений является треугольник (рис. 7).
На рис. 7 также изображены исходная линия уровня 
и вектор 
. Так как требуется найти минимум функции, то будем передвигать исходную линию уровня в сторону, противоположную 
. Минимум функции достигается в угловой точке 
, координаты которой служат решением системы уравнений
т.е.
Опорнои прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находится в одной из полуплоскостей.
Область допустимых решений любой задачи имеет не более двух опорных прямых, на одной из которых может находиться оптимальное решение.
На основании приведенных примеров и определения опорной прямой запишем этапы нахождения решения задачи линейного программирования с двумя переменными графическим методом:
- Изображаем область допустимых решений.
- Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений.
- Если область допустимых решений является непустым множеством, то изображаем нормальный вектор линий уровня и одну из линий уровня, имеющую общие точки с этой областью.
- Линию уровня перемещаем до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении.
- Если при перемещении линии уровня по области допустимых решений в направлении, соответствующем приближению к максимуму (минимуму) целевой функции, линия уровня уходит в бесконечность, то .
- Если задача линейного программирования имеет оптимальное решение, то для его нахождения решаем систему из уравнений прямых, ограничивающих область допустимых решений и имеющих общие точки с соответствующей опорой прямой. Если целевая функция достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая линейная комбинация этих точек.
- Вычисляем значение целевой функции на оптимальном решении.
линий уровня и одну из линий уровня, имеющую общие точки с этой областью.
.Графическим методом решаются задачи линейного программирования, записанные в каноническом виде и удовлетворяющие условию 
, где 
— число неизвестных системы ограничений; 
— ранг системы векторов условий. Если уравнения системы ограничений линейно независимы, то ранг равен числу уравнений системы 
.
Возможно эти страницы вам будут полезны:
- Решение задач по математическому программированиюПримеры решения задач по математическому программированиюЗаказать работу по математическому программированиюПомощь по математическому программированиюЗадачи математического программированияЗадача линейного программированияРешение задач по линейному программированиюМетоды решения задач линейного программированияГрафический метод решения задач линейного программированияЗаказать работу по линейному программированиюПомощь по линейному программированиюКонтрольная работа по линейному программированиюЛинейное программирование в ExcelКурсовая работа по линейному программированию
Ранее я описал, как принимать решения с учетом ограничивающих факторов. Цель таких решений – определить ассортимент продукции (производственный план), максимально увеличивающий прибыль компании. Решение заключалось в том, чтобы распределить ресурсы между продуктами согласно маржинальной прибыли, полученной на единицу ограниченных ресурсов, при соблюдении любых других ограничений, таких как максимальный или минимальный спрос на отдельные виды продукции. [1]
Если ограничивающий фактор один (например, дефицитный станок), решение может быть найдено с применением простых формул (см. ссылку в начале статьи). Если же ограничивающих факторов несколько, применяется метод линейного программирования.
Линейное программирование – это название, данное комбинации инструментов используемых в науке об управлении. Этот метод решает проблему распределения ограниченных ресурсов между конкурирующими видами деятельности с тем, чтобы максимизировать или минимизировать некоторые численные величины, такие как маржинальная прибыль или расходы. В бизнесе он может использоваться в таких областях как планирование производства для максимального увеличения прибыли, подбор комплектующих для минимизации затрат, выбор портфеля инвестиций для максимизации доходности, оптимизация перевозок товаров в целях сокращения расстояний, распределение персонала с целью максимально увеличить эффективность работы и составление графика работ в целях экономии времени.
Скачать заметку в формате Word, рисунки в формате Excel
Линейное программирование предусматривает построение математической модели рассматриваемой задачи. После чего решение может быть найдено графически (рассмотрено ниже), с использованием Excel (будет рассмотрено отдельно) или специализированных компьютерных программ. [2]
Пожалуй, построение математической модели – наиболее сложная часть линейного программирования, требующая перевода рассматриваемой задачи в систему переменных величин, уравнений и неравенств – процесс, в конечном итоге зависящий от навыков, опыта, способностей и интуиции составителя модели.
Рассмотрим пример построения математической модели линейного программирования
Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.
Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (рис. 1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.
Рис. 1. Использование и предоставление ресурсов
Николай хочет построить модель с тем, чтобы определить количество единиц продуктов А и В, которые он доложен производить в следующем месяце для максимизации маржинальной прибыли.
Линейная модель может быть построена в четыре этапа.
Этап 1. Определение переменных
Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:
Z = суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.
Существует ряд неизвестных искомых переменных (обозначим их х1, х2, х3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:
х1 = количество единиц продукта А, произведенных в следующем месяце.
х2 = количество единиц продукта В, произведенных в следующем месяце.
Очень важно четко определить все переменные величины; особое внимание уделите единицам измерения и периоду времени, к которому относятся переменные.
Этап. 2. Построение целевой функции
Целевая функция – это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х1, х2… в виде линейного уравнения.
В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х1 единиц продукта А, маржинальная прибыль составит 2500 * х1. Аналогично маржинальная прибыль от изготовления х2 единиц продукта В составит 3500 * х2. Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х1 единиц продукта А и х2 единиц продукта В, то есть, целевая переменная Z составит:
Z = 2500 * х1 + 3500 *х2
Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:
Максимизировать Z = 2500 * х1 + 3500 *х2
Этап. 3. Определение ограничений
Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».
В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х1 их2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х1, единиц, то будет потрачено З * х1, часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х2 продуктов, то потребуется 10 * х2 часов. Таким образом, общий объем машинного времени, необходимого для производства х1 единиц продукта А и х2 единиц продукта В, составляет 3 * х1 + 10 * х2. Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:
3 * х1 + 10 * х2 ≤ 330
Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:
х2 ≥ 12
Этап 4. Запись условий неотрицательности
Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х1 ≥ 0 и х2 ≥ 0. В нашем примере второе условия является избыточным, так как выше было определено, что х2 не может быть меньше 12.
Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:
Максимизировать: Z = 2500 * х1 + 3500 *х2
При условии, что: 3 * х1 + 10 * х2 ≤ 330
16 * х1 + 4 * х2 ≤ 400
6 * х1 + 6 * х2 ≤ 240
х2 ≥ 12
х1 ≥ 0
Рассмотрим графический метод решения задачи линейного программирования.
Этот метод подходит только для задач с двумя искомыми переменными. Модель, построенная выше, будет использована для демонстрации метода.
Оси на графике представляют собой две искомые переменные (рис. 2). Не имеет значения, какую переменную отложить вдоль, какой оси. Важно выбрать масштаб, который в конечном итоге позволит построить наглядную диаграмму. Поскольку обе переменные должны быть неотрицательными, рисуется только I-й квадрант.
Рис. 2. Оси графика линейного программирования
Рассмотрим, например, первое ограничение: 3 * х1 + 10 * х2 ≤ 330. Это неравенство описывает область, лежащую ниже прямой: 3 * х1 + 10 * х2 = 330. Эта прямая пересекает ось х1 при значении х2 = 0, то есть уравнение выглядит так: 3 * х1 + 10 * 0 = 330, а его решение: х1 = 330 / 3 = 110
Аналогично вычисляем точки пересечения с осями х1 и х2 для всех условий-ограничений:
| Область допустимых значений | Граница допустимых значений | Пересечение с осью х1 | Пересечение с осью х2 |
| 3 * х1 + 10 * х2 ≤ 330 | 3 * х1 + 10 * х2 = 330 | х1 = 110; х2 = 0 | х1 = 0; х2 = 33 |
| 16 * х1 + 4 * х2 ≤ 400 | 16 * х1 + 4 * х2 = 400 | х1 = 25; х2 = 0 | х1 = 0; х2 = 100 |
| 6 * х1 + 6 * х2 ≤ 240 | 6 * х1 + 6 * х2 = 240 | х1 = 40; х2 = 0 | х1 = 0; х2 = 40 |
| х2 ≥ 12 | х2 = 12 | не пересекает; идет параллельно оси х1 | х1 = 0; х2 = 12 |
Графически первое ограничение отражено на рис. 3.
Рис. 3. Построение области допустимых решений для первого ограничения
Любая точка в пределах выделенного треугольника или на его границах будет соответствовать этому ограничению. Такие точки называются допустимыми, а точки за пределами треугольника называются недопустимыми.
Аналогично отражаем на графике остальные ограничения (рис. 4). Значения х1 и х2 на или внутри заштрихованной области ABCDE будут соответствовать всем ограничениям модели. Такая область называется областью допустимых решений.
Рис. 4. Область допустимых решений для модели в целом
Теперь в области допустимых решений необходимо определить значения х1 и х2, которые максимизируют Z. Для этого в уравнении целевой функции:
Z = 2500 * х1 + 3500 *х2
разделим (или умножим) коэффициенты перед х1 и х2 на одно и тоже число, так чтобы получившиеся значения попали в диапазон, отражаемый на графике; в нашем случае такой диапазон – от 0 до 120; поэтому коэффициенты можно разделить на 100 (или 50):
Z = 25х1 + 35х2
затем присвоим Z значение равное произведению коэффициентов перед х1 и х2 (25 * 35 = 875):
875 = 25х1 + 35х2
и, наконец, найдем точки пересечения прямой с осями х1 и х2:
| Уравнение целевой функции | Пересечение с осью х1 | Пересечение с осью х2 |
| 875 = 25х1 + 35х2 | х1 = 35; х2 = 0 | х1 = 0; х2 = 25 |
Нанесем это целевое уравнение на график аналогично ограничениям (рис. 5):
Рис. 5. Нанесение целевой функции (черная пунктирная линия) на область допустимых решений
Значение Z постоянно на всем протяжении линии целевой функции. Чтобы найти значения х1 и х2, которые максимизируют Z, нужно параллельно переносить линию целевой функции к такой точке в границах области допустимых решений, которая расположена на максимальном удалении от исходной линии целевой функции вверх и вправо, то есть к точке С (рис. 6).
Рис. 6. Линия целевой функции достигла максимума в пределах области допустимых решений (в точке С)
Можно сделать вывод, что оптимальное решение будет находиться в одной из крайних точек области принятия решения. В какой именно, будет зависеть от угла наклона целевой функции и от того, какую задачу мы решаем: максимизации или минимизации. Таким образом, не обязательно чертить целевую функцию – все, что необходимо, это определить значения х1 и х2 в каждой из крайних точек путем считывания с диаграммы или путем решения соответствующей пары уравнений. Найденные значения х1 и х2 затем подставляются в целевую функцию для расчета соответствующей величины Z. Оптимальным решением является то, при котором получена максимальная величина Z при решении задачи максимизации, и минимальная – при решении задачи минимизации.
Определим, например значения х1 и х2 в точке С. Заметим, что точка С находится на пересечении линий: 3х1 + 10х2 = 330 и 6х1 + 6х2 = 240. Решение этой системы уравнений дает: х1 = 10, х2 = 30. Результаты расчета для всех вершин области допустимых решений приведены в таблице:
| Точка | Значение х1 | Значение х2 | Z = 2500х1 + 3500х2 |
| А | 22 | 12 | 97 000 |
| В | 20 | 20 | 120 000 |
| С | 10 | 30 | 130 000 |
| D | 0 | 33 | 115 500 |
| E | 0 | 12 | 42 000 |
Таким образом, Николай Кузнецом должен запланировать на следующий месяц производство 10 изделий А и 30 изделий В, что позволит ему получить маржинальную прибыль в размере 130 тыс. руб.
Кратко суть графического метода решения задач линейного программирования можно изложить следующим образом:
- Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.
- Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х1 = 0 и х2 = 0.
- Нанести линии ограничений модели на график.
- Определите на графике область (называемую допустимой областью принятия решения), которая соответствует всем ограничениям. Если такая область отсутствует, значит, модель не имеет решения.
- Определите значения искомых переменных в крайних точках области принятия решения, и в каждом случае рассчитайте соответствующее значение целевой переменной Z.
- Для задач максимизации решение – точка, в которой Z максимально, для задач минимизации, решение – точка, в которой Z минимально.
[1] Настоящая заметка написана по материалам CIMA.
[2] См., например, здесь.