Виды целевой функции в линейном программировании. Нетрадиционные методы
Большое число экономических задач сводится к линейным математическим моделям. Традиционно их называют моделями линейного программирования. Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана-решения в задачах с линейной структурой. Обычно его используют специалисты штабных подразделений для разрешения производственных трудностей. Типичными примерами применений модели линейного программирования являются следующие:
укрупненное планирование производства (составление графиков производства, минимизирующих общие издержки в связи с изменением ставки процента);
планирование ассортимента изделий (определение оптимальной структуры производства продуктов питания для человека);
маршрутизация производства изделий (определение оптимального технологического маршрута изготовления изделия);
регулирование запасов (определение оптимального сочетания продуктов на складе);
календарное планирование производства (составление календарных планов, минимизирующих издержки с учетом расходов на содержание запасов, оплату сверхурочной работы и заказов на стороне);
планирование распределения продукции и пр.
В самом общем виде линейное программирование сводится к оптимизационной задаче и записывается в следующем виде:
Чтобы
решить задачу оптимизации, достаточно
найти ее оптимальное решение, т.е. указать
такое,
чтоf
(X
0
)≥
f
(X
)
при любом
,
или для случая минимизации -f
(X
0
)≤
f
(X
)
при любом
.
Оптимизационная задача является неразрешенной, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешенной, если целевая функция f (X ) не ограничена сверху на допустимом множестве W .
Методы решения оптимизационных задач зависят как от вида целевой функции f (X ) , так и от строения допустимого множества W . Если целевая функция в задаче является функцией п переменных, то методы решения называются методами математического программирования.
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
|
| ||
При этом система линейных уравнений (2) и неравенств (3), (4), определяющая допустимое множество решений задачи W , называется системой ограничений задачи линейного программирования, а линейная функция f (X ) называется целевой функцией, или критерием оптимальности.
Если математическая модель задачи линейного программирования имеет вид:
|
| ||
|
| ||
|
| ||
|
|
то говорят, что задача представлена в канонической форме.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме, переводя максимизацию к минимизации, от ограничений неравенств к ограничениям равенств и заменяя переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1);
3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных, они преобразуются в равенства;
4) если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x k = x ’ k - x 1 , где 1 – свободный индекс, x ’ k ≥ 0, x 1 ≥ 0.
Обобщая сказанное можно сделать следующие выводы:
1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами.
2. Линейная функция может стремиться как к максимуму, так и к минимуму.
3. Переменные в модели всегда неотрицательны.
4. От любой задачи линейного программирования можно перейти к канонической (основной) задаче линейного программирования.
Каждой задаче линейного программирования можно противопоставить другую задачу линейного программирования, двойственную по отношению к исходной (прямой).
Рассмотрим задачу линейного программирования следующего вида:
|
……………………….. |
В задаче требуется максимизировать целевую функцию; все ограничения являются неравенствами со знаком ≤, все переменные х 1 , х 2 ,…,х п п управляющих переменных и m ограничений. Коэффициенты при переменных в целевой функции: c 1 , c 2 ,…, c n ; свободные члены: b 1 , b 2 ,…, b m .
Двойственная задача линейного программирования имеет вид:
|
……………………….. |
В двойственной задаче требуется найти минимум целевой функции, ограничения – неравенства со знаком ≥, управляющие переменные y 1 , y 2 ,…, y m неотрицательны. Задача содержит m управляющих переменных и n ограничений. Коэффициенты целевой функции задачи b 1 , b 2 ,…, b m являются свободными членами исходной задачи линейного программирования, а свободные члены двойственной задачи c 1 , c 2 ,…, c n – коэффициентами целевой функции исходной задачи линейного программирования. Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы – строками.
Задачи (9) –(10) и (11) – (12) образуют пару задач, называемую в линейном программировании двойственной парой.
Двойственная задача по отношению к исходной составляется по следующим правилам:
1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум.
2. Матрица А (13)
|
|
,составленная из коэффициентов при неизвестных в системе ограничений (10) исходной задачи (9) – (10) и аналогичная матрица в двойственной задаче (11) – (12) получаются друг из друга транспонированием.
3. Число переменных в двойственной задаче (11) – (12) равно числу ограничений в системе (10) исходной задачи, а число ограничений в системе (12) двойственной задачи – числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции (11) двойственной задачи являются свободные члены в системе (10) исходной задачи, а правыми частями в ограничениях системы (12) двойственной задачи - коэффициенты при неизвестных в целевой функции (9) исходной задачи.
5. Если переменная x j исходной задачи (9) –(10) может принимать только лишь неотрицательные значения, то j - е ограничение в системе (12) двойственной задачи является неравенством вида ≥. Если же переменная x j может принимать как положительные, так и отрицательные значения, то j - е ограничение в системе (12) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (10) исходной задачи и переменными двойственной задачи. Если i - е ограничение в системе (10) исходной задачи является неравенством, то i - я переменная двойственной задачи y i ≥ 0. Если же i - е ограничение есть уравнение, то переменная y i может принимать как положительные, так и отрицательные значения.
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования – симплекс-метода. Геометрический смысл этого метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум). Идеи метода были опубликованы российским ученым Л.В. Канторовичем в 1939 г.
Для применения симплекс-метода в ограничения задачи вводятся дополнительные переменные y 1 , y 2 ,…, y i и условие исходной задачи принимает вид:
|
……….………………….. |
Эту постановку можно представить в виде таблицы – первой таблицы симплекс-метода (табл. 1.1).
Таблица 1.1.
Первая симплекс-таблица
|
Свободные члены |
Свободные переменные |
||||
|
x 1 |
x 2 |
x n |
|||
|
y 1 |
b 1 |
a 11 |
a 12 |
a 1n |
|
|
y 2 |
b 2 |
a 21 |
a 22 |
a 2n |
|
|
y m |
b m |
a m1 |
a m2 |
a mn |
|
|
Индексная строка |
-c 1 |
-c 2 |
-c n |
||
Для составления симплекс-таблицы можно применить определенные правила.
1. Для первой таблицы:
а) в первый столбец записывают y m – базисные переменные, которые находятся в уравнениях слева;
б) свободные переменные a mn выносят в верхнюю строку таблицы;
в) в остальные столбцы записывают коэффициенты перед свободными переменными.
2. Для последующих таблиц:
а) выбирается наименьший отрицательный элемент в индексной строке при отыскании максимума, но наибольший положительный – при отыскании минимума, исключая вектор свободных членов;
б) этот элемент определяет ключевой вектор-столбец и он вводится в базис;
в) компоненты вектора свободных членов делятся на положительные элементы ключевого столбца;
г) из полученных отношений выбирается наименьшее;
д) вектор-строка, содержащая наименьшее положительное частное - ключевая и выводится из базиса;
е) на пересечении ключевых строк и столбца находится разрешающий элемент;
ж) преобразование матрицы:
Каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы,
Ключевой столбец в новой таблице – нули, за исключением разрешающего элемента,
Остальные элементы новой таблицы рассчитываются по схеме:
Новый элемент = Старый элемент –
- Элемент ключевой строки*Элемент ключевого столбца
Разрешающий элемент
Если нулевая строка (столбец) содержит нуль, то соответствующий столбец (строка0 в новой таблице не изменится.
3. Пункты «а» - «ж» повторяются до тех пор, пока в индексной строке не останется ни одного отрицательного элемента при отыскании максимума (но ни одного положительного при отыскании минимума).
Пример 1.1. Требуется принять решение об оптимальном плане производства трикотажа на месяц на ОАО «Свияж» с применением симплекс-методы.
Определим план выпуска моделей мужского трикотажа с целью получения максимальной прибыли при заданных ресурсах с помощью построения математической модели. Исходные данные представлены в таблице 1.2.
Таблица 1.2.
Исходные данные
|
Ресурсы (i ) |
Вид продукции (j ) |
Запас ресурса (b i ) |
|||
|
Брюки спортивные модель 7060 |
Свитер мужской модель 55-1 |
Джемпер мужской модель 38-0 |
Костюм спортивный модель |
||
|
удельный расход ресурса (a ij ) |
|||||
|
Трудовые | |||||
|
Материальные | |||||
|
Оборудование | |||||
|
x 1 |
x 2 |
x 3 |
x 4 | ||
Исходные данные по удельному расходу материальных, трудовых ресурсов проставлены в табл. 1.2 в соответствии с действующей в организации нормативной и технологической документацией. По строке «Материальные ресурсы» зафиксирована норма расхода наиболее дефицитного (лимитируемого0 вида материалов – пряжа шерстяная. Этот материал имеет самую высокую норму расхода и стоимость.
По строке «Оборудование» проставлена сводная трудоемкость изготовления единицы изделия в нормо-часах как суммарная по всем детале-операциям. Остальные виды ресурсов также взяты в натуральных единицах: трудовые ресурсы – в часах; материальные – в дм 2 .
Строка «Прибыль» отражает прибыль от реализации единицы изделия, взята в из плановой калькуляции на единицу изделия.
Через x 1 , x 2 , x 3 , x 4 обозначили количество выпускаемой продукции каждого вида ассортимента.
Согласно правилу построения стандартной задачи линейного программирования составим математическую модель:
|
|
В ограничениях задачи введем дополнительные переменные y 1 , y 2 , y 3 и перепишем условие задачи в виде уравнения:
|
|
Последнюю постановку можно представить в виде таблицы 1.3 – первой таблицы симплекс-метода, которой воспользуемся для решения задачи линейного программирования.
Таблица 1.3.
Первая симплекс-таблица
|
Свободные члены |
Свободные переменные |
||||
|
x 1 |
x 2 |
x 3 |
x 4 |
||
|
y 1 | |||||
|
y 2 | |||||
|
y 3 | |||||
|
Индексная строка | |||||
В первый столбец записаны y i – базисные переменные, которые находятся в уравнении слева, а свободные переменные x j вынесены в верхнюю строку таблицы. В остальных столбцах записаны коэффициенты перед свободными переменными. Индексная строка – результат вычитания из нуля коэффициентов перед свободными переменными.
Для построения следующей таблицы выбирается наименьший отрицательный элемент в индексной строке (это 222). Этот элемент определяет ключевой вектор-столбец и он вводится в базис. Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из полученных отношений выбирается наименьшее. Вектор-строка, содержащая наименьшее положительное частное, - ключевая и выводится из базиса (y 2 ). На пересечении ключевых строк и столбца находится разрешающий элемент (это 55,50).
Затем каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы. В итоге получена вторая симплекс-таблица (табл. 1.4).
Таблица 1.4.
Вторая симплекс-таблица
|
Свободные члены |
Свободные переменные |
||||
|
x 1 |
x 2 |
x 3 |
x 4 |
||
|
y 1 | |||||
|
y 2 | |||||
|
y 3 | |||||
|
Индексная строка | |||||
Так как в индексной строке появился отрицательный элемент, следует повторить все аналогичные этапы и построить третью симплекс-таблицу.
В итоге получена табл. 1.5.
Таблица 1.5.
Итоговая симплекс-таблица
|
Свободные члены |
Свободные переменные |
||||
|
x 1 |
x 2 |
x 3 |
x 4 |
||
|
y 1 | |||||
|
y 2 | |||||
|
y 3 | |||||
|
Индексная строка | |||||
На
основании таблицы 1.5 можно сделать
выводы: в столбце свободных членов все
элементы положительны (это значит, что
полученное решение является допустимым);
в индексной строке все элементы также
положительны (это значит, что полученное
решение – оптимально, т.е. максимизирует
целевую функцию); оптимальным планом
будут величины:
(значит,
они базисные);
(так
как они свободны); целевая функцияL
=
4 201 195.
Из таблицы 1.5 также следует, что базисная переменная y 3 =9716, а свободные переменные y 1 = y 2 = 0, т.е. в оптимальном плане резервы трудовых и материальных ресурсов равны нулю, так как они используются полностью. А резерв ресурсов оборудования y 2 = 9716, что свидетельствует о его излишках.
Таким образом, в результате применения метода линейного программирования принято решение о производстве джемперов мужских выбранной модели в количестве 3981 шт., свитеров мужских модели 55-1 в количестве 29 875 шт.
Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.
Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:
· задача об оптимальном использовании ресурсов при производственном планировании;
· задача о смесях (планирование состава продукции);
· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
· транспортные задачи (анализ размещения предприятия, перемещение грузов).
Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
· математические модели большого числа экономических задач линейны относительно искомых переменных;
· данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
· многие задачи линейного программирования, будучи решенными, нашли широкое применение;
· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
целевая функция:
F = c1x1 + c2x2 + ... + cnxn → max(min);
ограничения:
a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,
a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,
am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;
требование неотрицательности:
Задача состоит в нахождении оптимального значения функции при соблюдении ограничений.
Итак , Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).
Симплекс-метод является основным в линейном программировании . Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме . Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r , то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X 1 , X 2 , ..., X r . Тогда наша система уравнений может быть записана как
К такому виду можно привести любую совместную систему , например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.
Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными , их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением , если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X 1 , X 2 , ..., X r , то решение {b 1 , b 2 ,..., b r , 0, ..., 0} будет опорным при условии, что b 1 , b 2 ,..., b r ≥ 0 .
Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.
Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.
Имея систему ограничений , приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n) , находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.
Если первое же найденное базисное решение оказалось допустимым , то проверяют его на оптимальность . Если оно не оптимально , то, осуществляется переход к другому, обязательно допустимому базисному решению .
Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
Если первое найденное базисное решение окажется недопустимым , то с помощью симплексного метода осуществляется переход к другим базисным решениям , которые приближают нас к области допустимых решений, пока на каком-то шаге решения либо базисное решение окажется допустимым и к нему применяют алгоритм симплексного метода, либо мы убеждаемся в противоречивости системы ограничений.
Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.
При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.
Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Не останавливаясь подробнее на сути алгоритма, опишем его вычислительную сторону. Вычисления по симплекс-методу организуются в виде симплекс-таблиц , которые являются сокращенной записью задачи линейного программирования в канонической форме. Перед составлением симплекс-таблицы задача должна быть преобразована , система ограничений приведена к допустимому базисному виду , c помощью которого из целевой функции должны быть исключены базисные переменные. Вопрос об этих предварительных преобразованиях мы рассмотрим ниже. Сейчас же будем считать, что они уже выполнены и задача имеет вид.
Линейное программирование представляет собой методы решения определенного класса задач по нахождению крайних значений (шах или min). Они основаны на решении системы линейных уравнений, когда зависимость строго функциональна. В модели линейного программирования выделяются три составные части: целевая (максимизируемая или минимизируемая) функция, система ограничений и условие неотрицательности переменных. Математический аппарат линейного программирования используется при решении задач экономических, технических, военных и др.
В экономических задачах оптимального планирования решение целевой функции сводится к нахождению максимума, например, прибыли, объема производства, производительности труда или минимума текущих затрат, капиталовложений, времени выполнения работ и т.п.
В тоже время надо отметить, что не каждая задача оптимального планирования может быть сформулирована и разрешена в рамках линейного программирования. Для этого необходимо соблюсти четыре основных условия.
- 1. В задаче должен быть четко сформулирован и количественно определен критерий оптимальности, что не так легко сделать на практике. О работе предприятия чаще всего судят по ряду показателей: объему производства, ассортименту и качеству выпускаемой продукции, рентабельности производства и др. Выбор одного критерия может оказаться далеко не лучшим с точки зрения другого и наоборот.
- 2. Важной составной частью задачи линейного программирования являются ограничения, связанные с наличными ресурсами, потребностями или другими факторами. В реальной экономике не всегда можно учесть взаимодействие слишком большого количества факторов, поэтому составляется упрощенная модель, которая бы более близко отражала действительный характер.
- 3. Линейное программирование предполагает выбор вариантов и оно применимо только тогда, когда конкретные условия экономической задачи обусловливают эту свободу выбора.
- 4. Модель должна содержать только линейные уравнения или неравенства, т.е. все переменные задачи должны быть в первой степени. Реальные экономические зависимости не всегда носят линейный характер.
Учитывая соответствующие условия и приближая экономическую ситуацию для решения задач линейного программирования, необходимо также учитывать, что наложение на переменные величины слишком жестких ограничений может привести к противоречивости всей системы исходных условий задачи.
По характеру решаемых задач методы линейного программирования можно разбить на две группы.
- 1. Универсальные методы. С их помощью могут решаться любые задачи линейного программирования. Самым распространенным из них является симплексный метод , предложенный Дж. Данцигом, метод раз- решаюших множителей , разработанный академиком Л. В. Канторовичем в 1939 г., примерно за 10 лет до его появления за рубежом.
- 2. Специальные методы. Эти методы проще универсальных, но применимы не для всех задач. К ним относятся распределительный метод для решения транспортной задачи, метод разрешающих слагаемых А. Л. Лурье, метод дифференциальных рент А. Л. Брудно, венгерский метод.
К особой группе методов линейного программирования относятся приближенные методы , отличающие от остальных тем, что не гарантируют строго оптимального решения задачи, но они просты и хорошо приспособлены к ручным вычислениям. К ним относятся индексный метод , метод аппроксимации Фогеля и др.
Симплексный метод. Чтобы лучше понять идею симплексного метода, рассмотрим решение задачи оптимизации использования ресурсов с целью достижения максимальной прибыли.
Пример 2.21
Имеется вспомогательное производство, которое использует остающиеся от основного производства материалы. На данном производстве налажен выпуск дверей различного ассортимента: с использованием стекла (ассортимент ЛВС) и без него (ассортимент ДВ). Сбыт данной продукции обеспечен, т.е. продукция может производиться в любых соотношениях, но есть ограничение по количеству рабочих мест в цехе и ресурсам основных материалов. Задача состоит в том, чтобы запланировать цеху ежемесячный выпуск продукции, обеспечивающий наибольшую возможную сумму прибыли.
В задаче не ставится условия обязательного использования всего объема ресурсов. Необходимо, чтобы расход рабочего времени был не больше заданных пределов.
Рассмотрим программу 1, которая предполагает выпуск только дверей ассортимента ДВ, нс используя при этом стекло для их производства.
Если выпускать только ДВ, используя при этом все имеющиеся ресурсы, то их хватит для выпуска:
- - по рабочему времени: 520/9,2 = 56 (шт.);
- - древесине: 24/0,3 = 80 (шт.).
Следовательно, всех ресурсов достаточно для выпуска только 56 дверей.
Прибыль при данном выпуске составит 168 000 руб. (56 3000).
Программа 2 предполагает выпуск только дверей ассортимента ЛВС. В данном случае ресурсов хватит для выпуска:
- - но рабочему времени: 520/4 = 130 (шт.);
- - древесине: 24/0,6 = 40 (шт.);
- - стеклу: 40/2 = 20 (шт.).
Оптимально возможен выпуск только 20 дверей ЛВС, что ограничивается наличием стекла. При этом уйдет 12 м древесины, из оставшейся части возможен еще выпуск 40 шт. дверей ассортимента ДВ. На производство 20 шт. ДВС и 40 шт. ДВ будет потрачено 448 чел.-ч.
Прибыль составит 160 тыс. руб. (20 -2 + 40-3). Значит первая программа предпочтительней. Существуют и другие варианты.
Ограничения данной задачи таковы:
На графике проведем прямую L u
соответствующую первому неравенству:
Второму неравенству соответствует прямая Ь 2:
Третьему неравенству на графике соответствует прямая, параллельная оси абсцисс L 3:
Поскольку план выпуска должен строиться исходя из всех пяти ограничений задачи, то областью допустимых решений в данном случае будет закрашенный многоугольник.
Максимальное значение целевой функции, найденное в предыдущих расчетах, будет соответствовать точкам прямой:
Многоугольник ограничивает область допустимых решений задачи. Из массы решений нужно выбрать такое, где значение прибыли максимально. В нашем случае эго будет точка пересечения прямых L {
и 1 2 .
Далее решается система линейных уравнений:
Решая систему, получаем:
отсюда прибыль равна:
Если прямая, отвечающая целевой функции (в графическом методе) проходит через вершину многоугольника, то задача имеет единственный оптимальный вариант. Если совпадает со стороной многоугольника, то задача имеет множество решений.
Оптимальное решение должно проходить либо через вершину, либо через сторону многоугольника. Поэтому одна из вершин отвечает оптимальному решению, но неизвестно вначале какая.
Графический метод прост и нагляден, но применение его ограничено.
При трех переменных пришлось бы строить многогранник в многомерной системе координат. При четырех и более переменных графическое изображение невозможно. Но можно представить многомерное пространство абстрактно. Если условие задачи непротиворечиво, то область допустимых значений (ОДЗ) образует выпуклый многоугольник в и-мерном пространстве.
При этом оптимальное решение, если оно существует, обязательно достигается в некоторой вершине многогранника (возможно и более чем в одной).
Таким образом, чтобы найти решение задачи линейного программирования достаточно перебрать варианты, соответствующие вершинам многогранника. Они называются опорными планами. Однако в сложных задачах их может оказаться чрезмерно много и определение опорных планов потребует огромного объема вычислений.
Симплексный метод позволяет осуществить упорядоченный перебор вершин многогранника.
Последовательность расчетов по симплексному методу рассмотрим на примере.
Пример 2.23
Предприятие располагает тремя группами оборудования (I, II, III), па котором изготавливается четыре вида продукции (А, Б, В, Г). Все изделия имеют неограниченный сбыт и, следовательно, предприятие может планировать ассортиментную программу в пределах данной номенклатуры.
Имеются следующие ограничения:
- - наличие основного оборудования;
- - нормы времени на обработку каждого вида изделий на оборудовании каждой группы;
- - величина прибыли, полученная предприятием за единицу конкретного вида изделий.
Требуется получить максимальную прибыль.
Искомый выпуск: х { - изд. А; х 2 - изд. Б; х 3 - изд. В; х 4 - изд. Г.
Максимальная прибыль:
Ограничения:
Для решения задачи симплексным методом все неравенства превращаем в равенства. Для этого вводим в задачу три дополнительные неотрицательные переменные величины: х 5 , х 6 , х 7 и прибавляем их к левой части неравенства:
По своему экономическому смыслу дополнительные переменные есть ни что иное, как неиспользованное время работы конкретного оборудования. Для решения задач симплекс методом составляются специальные симплекс таблицы.
В самой верхней строке записаны коэффициенты целевой функции. Дополнительным переменным соответствуют нулевые коэффициенты. Неиспользованное оборудование не приносит прибыль. Те же нулевые показатели - в столбце С против каждой дополнительной переменной.
В заполнении строки Zj - Cj имеются свои особенности. Рассматривается Zj для каждого столбца. Она получается как сумма произведений величин столбца С на соответствующие коэффициенты столбца j. Поскольку в первоначальном варианте в столбце С находятся 0, то величина Zj для всех столбцов равна 0, а величина Zj - Cj = -Cj. Поэтому в начальном варианте здесь поставлены коэффициенты целевой функции с обратным знаком. Все основные переменные приравнены к 0 и не входят в базис нашей задачи. Дополнительные переменные равны предельным значениям в соответствии с исходными уравнениями. Это означает, что ничего не производится, ресурсы не используются и значение целевой функции равно 0 (прибыль отсутствует).
Решение задачи заключается в последовательном введении в план основных переменных, пока не будет получено оптимальное решение. При этом на каждом этапе расчета можно ввести лишь одну переменную. При этом другая переменная выводится из базы, так как при трех ограничениях в базисе не может быть больше трех переменных.
Поскольку задача решается на max прибыли, начинать надо с наиболее прибыльного изделия. В нашем случае это изд. Г. В базис вводится х 4 . Определим, каким может быть предусмотрен выпуск изд. Г. Это зависит от объема ресурсов и нормативов затрат. На оборудовании группы I можно обработать 3000 изд. (24 000/8), группа II в изготовлении Г не участвует, а группа III может быть использована на обработку 30 000 изд. Принимаем наименьшее из значений (3000 изд.), в таблице в колонку «базис» х 4 ставится на место х 5 (оборудование группы I равняется нулю, так как использовано полностью). Число 8 на пересечении х А и х 5 называется направляющим элементом или генеральным , ключевым , разрешающим.
Строка х 4 в новой таблице получается путем деления строки выводящей переменной х 5 предыдущей таблицы на направляющий элемент. В столбце С проставляется 0,8 - величина прибыли с единицы изд. Г. После этого пересчитывается столбец «план». На оборудовании группы II изд. Г не обрабатывается и в новом варианте фонд его времени остается без изменений (12 000 мин).
Фонд времени оборудования группы III уменьшится на 3000 мин (1 мин х х 3000 шт.), следовательно остаются неиспользованными 27 000 мин. Следующее число столбца «план» - 2400 руб. (0,8 3000) - прибыль при данном варианте. После столбца «план» пересчитываются все остальные столбцы симплексной таблицы, кроме строки вводимой переменной. При этом, следует иметь в виду, что в столбцах всех переменных, входящих в базис, на пересечении одноименных строк и столбцов всегда находится единица, а остальные элементы столбца равны нулю.
Поэтому сразу можно заполнить столбцы х 4 , х 6 и х 7 . Пересчет целесообразно производить по «правилу треугольника». Для того, чтобы рассчитать в новом варианте какой-либо коэффициент, нужно в симплексной таблице найти три числа: число, стоящее на месте этого коэффициента в предыдущем варианте;
- - число, стоящее в той же строке предыдущего варианта, но в столбце вводимой переменной;
- - число, находящееся в новом варианте в одном столбце с искомым коэффициентом, но в строке вновь введенной переменной (элементы этой строки ранее уже были рассчитаны).
Указанные три числа в таблице образуют прямоугольный треугольник. Для определения искомого коэффициента из числа, находящегося в вершине прямого угла необходимо вычесть произведение двух других углов.
Например, для столбца.гр
Производим вычисление:
для коэффициента по строке
для коэффициента строки х 7:
Показатель для строки Zj - Cj можно рассчитать двумя способами:
а) по формуле
б) по правилу «треугольника»:
Аналогично производим расчеты и для других столбцов нового варианта симплексной таблицы.
Теперь необходимо выяснить, является ли второй вариант оптимальным или он может быть улучшен. Для этого просматривается строка Zj - Cj. Если она содержит отрицательные числа, то вариант может быть улучшен.
На 0,3 руб. в расчете на каждую вводимую единицу изделий увеличится прибыль при введении в базис числах! (изд. А) и на 0,1 руб. при введении числах 3 (изд. В). Эти цифры могут показаться противоречащими исходным данным: согласно которым изд. А приносит 0,4 руб. прибыли, В - 0,5 руб. Но дело в том, что на данном этапе задачи введение в план этих изделий вытеснит известное количество ранее введенных изд. Г, чтобы для их производства высвободить оборудование группы I.
На следующем этане целесообразнее ввести х { (изд. А), гак как ему соответствует наибольшее по абсолютной величине отрицательное число. Аналогично предыдущему варианту установим сколько едении изд. А может быть включено в план с учетом того, что он уже содержит выпуск изд. Г. Для этого числа из столбца «план» делим на соответствующие (только положительные) коэффициенты из столбца вводимой переменной х { и из полученных частных выбираем наименьшее:
Отсюда следует, что в новый вариант расчета может быть введено не более 4000 изд. А, гак лимитирующим фактором является оборудование группы II. Следовательно, переменная х { заменит в базисе переменную х в.
На пересечении столбца х х и строки х 6 находим и подчеркиваем направляющий элемент - 3. Далее рассчитываем строку введенной переменной путем деления элементов строки х 6 предыдущего варианта на направляющий элемент. Затем рассчитываем столбец «план»:
Прибыль при новом варианте составит:
По описанному правилу заполняем следующие столбцы. Просматривая строку Zj - Cj видим, что в ней содержатся только нули и положительные элементы, что означает, что вариант 3 является оптимальным решением и не может быть улучшен. В него входят лишь два вида изделий из четырех. Переменная х 3 соответствует в последней строке 0. Это означает, что введение в план на последующем шаге х 3 не увеличит прибыль, но и не уменьшит ее и полученный результат также будет оптимальным. Разделив числа столбца «план» на коэффициенты столбца х 3 и выбрав из полученных минимальное, определяем, что данная переменная должна вводиться в базис на место переменной^. В результате последующих преобразований получаем новый оптимальный план, в котором предусматривается выпуск 2182 изд. А (х {) и 5455 изд. В (.г 3). Найдем еще несколько оптимальных вариантов решения нашей задачи. Вариант /: 50% из первой программы и 50% из второй программы:
Вариант II: 80% из первой программы и 20% из второй программы:
Эти варианты также обеспечивают прибыль в размере 3600 руб.
Наличие нескольких практически равных эффективных планов позволяет определить ряд промежуточных вариантов, что в экономических задачах дает дополнительные возможности для анализа и качественного отбора наиболее приемлемых из них.
При решении задач симплекс методом могут встретиться случаи «вырождения». При т ограничениях невырожденный план всегда содержит т положительных переменных, а остальные п - т переменных задачи в базис не входят и равняются нулю. Однако возможно равенство нулю и одной или нескольких переменных из входящих в базис, т.е. наличие одного или несколько нулей в столбце «план» симплексной таблицы. Такой план и называется вырожденным. При вырожденном плане наличие отрицательных чисел в строке Zj - Cj не означает, что следующий вариант обеспечит увеличение значения целевой функции. Оно может остаться неизмененным, причем на протяжении не только одного, но и нескольких последовательных шагов. Так происходит зацикливание , которое препятствует дальнейшим расчетам и может быть преодолено лишь с помощью специальных приемов.
В настоящее время при решении задач оптимизации широко применяются персональные компьютеры. При этом используется система электронных таблиц «Microsoft Excel ».
Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис».
Если в версии Excel , установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения».
Рассмотрим на примере использование данной надстройки, решив с ее помощью задачу производственного планирования.
Пример 2.24
Предприятие выпускает продукты А, В, С, D из трех типов ресурсов. Математическая модель имеет следующий вид: шах/(Х) = 7,5я* 1 +3х 2 + 6дг 3 + 12.г 4 (целевая функция - суммарная стоимость выпуска).
Ограничения по запасам ресурсов и неотрицательности переменных таковы:
Составим шаблон в редакторе Excel.
Теперь занесем в данную задачу числовую информацию.
В выделенные пустые ячейки (значения целевой функции и левых частей неравенств) необходимо занести формулы, отображающие связи и отношения между числами на рабочем столе.
Ячейки С 4 - F a называются в Excel изменяемыми (в нашей модели это неизвестные переменные). Поиск решения при их изменении будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).
Теперь необходимо ввести формулы. В нашей математической модели целевая функция представляет собой произведение вектора коэффициентов на вектор неизвестных. Действительно, выражение можно рассматривать
как произведение вектора (7, 5, 3, б, 12) на вектор (.г, х 2 , я-*, х А).
В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. Данную функцию необходимо вызвать в ячейку #5, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5: F5 ), и ячеек, в которые в результате решения будут помещены значения х и х 2 , х 3 , х 4 (ячейки СА : FA).
Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. Выражение 2х х + х 2 + 0Дг 3 + 4х л (для первого ограничения 2х, + х 2 + 0,5х 3 + 4 х 4 2400) будем рассматривать как произведение вектора коэффициентов (2,1,0,5,4) и вектора переменных (х и х 2 , х 3 , х 4).
В ячейке, отведенной для формулы левой части первого ограничения ((79), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9: /0 и адрес значений переменных С4: FA.
В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введенными формулами выглядит следующим образом.
К моменту вызова сервиса «Поиск решения» на рабочий стол с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.
В меню «Сервис» выбираем «Поиск решения». В появившемся окне задаем следующую информацию:
- а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции #5;
- б) «флажок» устанавливаем на вариант «максимальному значению», так как в данном случае целевая функция дохода подлежит максимизации;
- в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4: F4;
- г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения;
д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G
9, выбирается требуемый знак неравенства (в нашем случае,
е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».
Окно «Поиск решения» с занесенной информацией выглядит следующим образом.
Далее необходимо нажать кнопку «Параметры», установить «флажки» «Линейная модель» и «Неотрицательные значения», поскольку в данном случае задача относится к линейному программированию, а ограничение требует неотрицательности значений.
Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения.
Если в результате всех действий получено окно с сообщением «Решение найдено», то вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи.
Если же в результате решения задачи выдано окно с сообщением о невозможности нахождения решения, это означает, что при оформлении задачи была допущена ошибка (не заполнены формулы для ограничений, неправильно установлен «флажок», максимизации (минимизации) и т.д.).
В окне «Поиск решения» имеется кнопка «Параметры».
Установим флажок «Показывать результаты итераций», нажмем «ОК».
Затем нажмем кнопку «Выполнить».
Ms Excel выдаст следующее окно.
На рабочем листе будут показаны результаты первой итерации.
После этого нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты второй итерации.
Снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации.
При следующем нажатии кнопки «Продолжить», программа выдает окно «Результаты поиска решения», где необходимо сохранить найденное решение и выбрать тип отчета.
В данном разделе рассмотрен общий формат решения задач оптимизации в Excel. В зависимости от экономических моделей, выполняют его соответствующие модификации.
Отчеты выглядят следующим образом.
1. Отчет по результатам.
2. Отчет по устойчивости.
3. Отчет по пределам.
Теперь рассмотрим пример, в котором математическая модель имеет тот же вид, но ограничения имеют разные знаки.
Пример 2.25
Л. Допустим, математическая модель такова:
Она имеет следующие ограничения:
Отчет по устойчивости.
Б. Теперь предположим, что математическая модель имеет другие ограничения:
В данном случае имеем следующие результаты по отчетам.
Отчет по устойчивости.
- Воспользуемся для решения этой же задачи одним из методов линейного программирования - графическим. Пример 2.22 Введем обозначения: х{ - искомое количество дверей ДВ, х2 - искомое количество дверей ДВС.
15. Аналитические методы. Методы линейного программирования.
15.1. Аналитические методы
На протяжении всей своей эволюции человек, совершая те или иные деяния, стремился вести себя таким образом, чтобы результат, достигаемый как следствие некоторого поступка, оказался в определенном смысле наилучшим. Двигаясь из одного пункта в другой, он стремился найти кратчайший среди возможных путь. Строя жилище, он искал такую его геометрию, которая при наименьшем расходе топлива, обеспечивала приемлемо комфортные условия существования. Занимаясь строительством кораблей, он пытался придать им такую форму, при которой вода оказывала бы наименьшее сопротивление. Можно легко продолжить перечень подобных примеров.
Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?
Ответ на первый вопрос получается как результат глубокого изучения проблемы, которую предстоит решить. Выявляется тот параметр, который определяет степень совершенства решения возникшей проблемы. Этот параметр обычно называют целевой функцией иликритерием качества . Далее устанавливается совокупность величин, которые определяют целевую функцию. Наконец, формулируются все ограничения, которые должны учитываться при решении задачи. После этого строится математическая модель, заключающаяся в установлении аналитической зависимости целевой функции от всех аргументов и аналитической формулировки сопутствующих задаче ограничений. Далее приступают к поиску ответа на второй вопрос.
Итак, пусть в
результате формализации прикладной
задачи установлено, что целевая функция
,
где множество Х – обобщение ограничений,
его называют множеством допустимых
решений. Существо проблемы оптимизации
заключается в поиске на множестве Х –
множестве допустимых решений такого
решения
,
при котором целевая функцияf
достигает наименьшего или наибольшего
значения.
Составной частью методов оптимизации является линейное программирование.
15.2. Основные понятия линейного программирования
Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.
Линейное программирование - это раздел математики, ориентированный на нахождение экстремума (максимума или минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры. Необходимым условием задач линейного программирования является обязательное наличие ограничений на ресурсы (сырье, материалы, финансы, спрос произведенной продукции и т.д.). Другим важным условием решения задачи является выбор критерия останова алгоритма, т. е. целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий останова алгоритма (или критерий оптимальности) должен удовлетворять следующим требованиям:
быть единственным для данной задачи;
измеряться в единицах количества;
линейно зависеть от входных параметров.
Исходя из вышесказанного, можно сформулировать задачу линейного программирования в общем виде:
найти экстремум целевой функции
при ограничениях в виде равенств:
(2.2)
при ограничениях в виде неравенств:
(2.3)
и условиях неотрицательности входных параметров:
В краткой форме задача линейного программирования может быть записана так:
(2.5)
при условии
где
- входные переменные;
Числа положительные, отрицательные и равные нулю.
В матричной форме эта задача может быть записана так:
Задачи линейного программирования можно решить аналитически и графически.
15.3. Каноническая задача линейного программирования
,
i=1,…,m,
,
j=1,…,n.
Основные вычислительные методы решения задач линейного программирования разработаны именно для канонической задачи.
15.4. Общая задача линейного программирования
Необходимо максимизировать (минимизировать) линейную функцию от n переменных.
при ограничениях
,
i
=1,…,
k
,
,
i
=1+
k
,…,
m
,
,
…,
Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .
Пример.
Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.
Таблица 1. Нормы расходов сырья
на производство
Экономико-математическая формулировка задачи имеет вид
Найти такие значения переменных Х=(х1, х2, х3) , чтобы
целевая функция
при условиях-ограничениях:
Решение происходит в три этапа:
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .Проиллюстрируем этот факт графически:
| F(x) → min
|
F(x) → max
 |
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент
– коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка
– строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец
– столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными
или зависимыми
. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными
или независимыми переменными
.
Базисное решение
называется допустимым базисным решением
, если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой
допустимого множества S задачи линейного программирования и называется иногда опорным планом
.
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным
(вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной
.
Пример №1
. Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП
.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(0 3):-2 | 3-(-2 3):-2 | -1-(5 3):-2 | 1-(0 3):-2 | 0-(-1 3):-2 | 10-(3 3):-2 |
| 0: -2 | -2: -2 | 5: -2 | 0: -2 | -1: -2 | 3: -2 |
| 1-(0 0):-2 | 0-(-2 0):-2 | 2-(5 0):-2 | 0-(0 0):-2 | 0-(-1 0):-2 | 9-(3 0):-2 |
Получаем новую матрицу:
| 4 | 0 | 6 1 / 2 | 1 | -1 1 / 2 | 14 1 / 2 |
| 0 | 1 | -2 1 / 2 | 0 | 1 / 2 | -1 1 / 2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 6 1 / 2):2 | 0-(0 6 1 / 2):2 | 6 1 / 2 -(2 6 1 / 2):2 | 1-(0 6 1 / 2):2 | -1 1 / 2 -(0 6 1 / 2):2 | 14 1 / 2 -(9 6 1 / 2):2 |
| 0-(1 -2 1 / 2):2 | 1-(0 -2 1 / 2):2 | -2 1 / 2 -(2 -2 1 / 2):2 | 0-(0 -2 1 / 2):2 | 1 / 2 -(0 -2 1 / 2):2 | -1 1 / 2 -(9 -2 1 / 2):2 |
| 1: 2 | 0: 2 | 2: 2 | 0: 2 | 0: 2 | 9: 2 |
Получаем новую матрицу:
| 3 / 4 | 0 | 0 | 1 | -1 1 / 2 | -14 3 / 4 |
| 1 1 / 4 | 1 | 0 | 0 | 1 / 2 | 9 3 / 4 |
| 1 / 2 | 0 | 1 | 0 | 0 | 4 1 / 2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или
Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max
Пример №2
. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0