ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6761
Скачиваний: 51
676
Эти условия определяют наличие минимума необходимых питательных веществ. Диета,
для которой выполнены условия (7.78) - допустимая диета. Предположим, что из всех допустимых
диет должна быть выбрана самая дешевая. Пусть
π
i
-
цена 1 кг продукта
F
i
.
Полная стоимость дие-
ты, очевидно,
S =
π
1
η
1
+ π
2
η
2
+… + π
n
η
n
.
(7.79)
Таким образом, мы пришли к задаче: найти неотрицательное решение
η
1
, …, η
n
системы не-
равенств (7.78), минимизирующее выражение (7.79).
В примерах, приведенных выше. имеется нечто общее. Каждый из них требует нахождения
наиболее выгодного варианта в определенной экономической ситуации. С чисто математической
стороны в каждой задаче требуется найти значение нескольких неизвестных так, чтобы
1) все эти значения были неотрицательны;
2) удовлетворяли системе линейных уравнений или линейных неравенств;
3) при этих значениях некоторая линейная функция имела бы минимум (или максимум).
Таким образом,
линейное программирование -
это математическая дисциплина, изучающая методы
нахождения экстремального значения линейной функции нескольких переменных при условии,
что последние удовлетворяют конечному числу линейных уравнений и неравенств. Запишем это с
помощью формул: дана система линейных уравнений и неравенств.
Запишем это с помощью формул: дана система линейных уравнений и неравенств
(7.80)
и линейная функция
f = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
(7.81)
Требуется найти такое неотрицательное решение
x
1
≥ 0, x
2
≥ 0, …, x
n
≥ 0
системы (7.80), чтобы функция
f
принимала наименьшее (или наибольшее) значение.
Условия (7.80) называют ограничениями данной задачи, а функцию
f
- целевой функцией
(или линейной формой). В приведенных выше примерах ограничения имели вид не уравнений, а
неравенств. Заметим, что ограничения в виде неравенств всегда можно свести к системе в виде ра-
венств (способом введения добавочных неизвестных).
Так, для неравенства
a
i1
x
1
+ a
i2
x
2
+ … + a
in
x
n
≥ b
i
вводя добавочное неизвестное
x
n
+1
, получаем
x
n
+1
=
a
i1
x
1
+ a
i2
x
2
+ … + a
in
x
n
- b
i
Потребовав его неотрицательности наряду с остальными неизвестными, получим, что усло-
вие
x
n + 1
≥
0 превращает (7.84) в (7.83). Введя по отдельному дополнительному неизвестному для
каждого из неравенств, получим систему уравнений, равносильную исходной системе неравенств.
Пример.
Дана система неравенств
677
Сведем ее к системе уравнений. Получим
После оптимизации значениями дополнительных неизвестных следует пренебречь.
7.2. СИМПЛЕКС-МЕТОД
Для решения ряда задач линейного программирования существуют специальные методы.
Есть, однако, общий метод решения всех таких задач. Он носит название симплекс-метода и со-
стоит из алгоритма отыскания какого-нибудь произвольного допустимого решения и алгоритма
последовательного перехода от этого решения к новому допустимому решению, для которого
функция
f
изменяется в нужном направлении (для получения оптимального решения).
Пусть система ограничений состоит лишь из уравнений
и требуется отыскать минимум линейной функции (7.81). Для отыскания произвольного опорного
решения приведем (7.85) к виду, в котором некоторые
r
неизвестных выражены через остальные, а
свободные члены неотрицательны (как это сделать - обсудим позднее):
Неизвестные
x
1
,
x
2
, ...,
x
r
-
базисные неизвестные
, набор {
x
1
,
x
2
, ...,
x
r
} называется базисом, а
остальные неизвестные {
x
r+1
,
x
r+2
, ...,
x
n
} -
свободные
.
Подставляя (7.86) в (7.81), выразим функцию
f
через свободные неизвестные:
f
=
c
0
+
c'
r
+1
x
r
+1
+
c'х
r
+2
+…+
с'
n
x
n
.
Положим все свободные неизвестные равными нулю:
Полученное таким образом допустимое решение
отвечает базису
x
1
, х
2
, ..., x
r
,
т.е. является базисным решением. Допустим для определенности, что
мы ищем минимум
f
. Теперь нужно отданного базиса перейти к другому с таким расчетом, чтобы
значение линейной функции
f
при этом уменьшилось. Проследим идею симплекс-метода на при-
мере.
Пример
1. Дана система ограничений
x
1
–
3
x
2
+
5
x
3
– x
4
=
2
x
1
+ x
2
+ x
3
+ x
4
=
4
Требуется минимизировать линейную функцию
f
= х
2
– x
3
.
В качестве свободных перемен-
ных выберем
х
2
и
х
3
.
Тогда данная система ограничений преобразуется к виду
678
Таким образом, базисное решение (3, 0, 0, 1). Так как линейная функция уже записана в
свободных неизвестных, то ее значение для данного базисного решения
f
= 0.
Для уменьшения
этого значения можно уменьшить
x
2
или увеличить
x
3
. Но
x
2
в данном базисе равно нулю и потому
его уменьшать нельзя. Попробуем увеличить
x
3
.
Первое из уравнений имеет ограничение
x
3
= 1 (из
условия
x
1
≥ 0), второе - не дает ограничений. Далее, берем
x
3
= 1,
х
2
не меняем и получаем новое
допустимое решение (0, 0, 1, 3), для которого
f =
-1 - уменьшилось. Найдем базис, которому соот-
ветствует это решение (он состоит, очевидно, из переменных
x
3
, x
4
). От предыдущей системы ог-
раничений переходим к новой:
а форма в новых свободных переменных имеет вид
Теперь попробуем повторить предыдущую процедуру. Для уменьшения
f
надо уменьшить
либо
x
1
,
либо
x
2
, но это невозможно, так как в этом базисе
x
1
=
0,
x
2
= 0.
Таким образом, данное базисное решение является оптимальным, и min
f
= -1 при
x
1
= 0, x
2
=
0,
x
3
= 1,
x
4
= 3.
Приведем алгоритм симплекс-метода в общем виде. Обычно все вычисления по симплекс-
методу сводят в стандартные таблицы.
Запишем систему ограничений в виде
(7.90)
а функцию
f
(7.91)
Тогда очередной шаг симплекс-процесса будет состоять в переходе от старого базиса к но-
вому таким образом, чтобы значение линейной функции, по крайней мере, не увеличивалось.
Данные о коэффициентах уравнений и линейной функции занесем в табл. 7.12.
Таблица 7.12
Симплекс-таблица
Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл.
7.12.
1. Выяснить, имеются ли в последней строке таблицы положительные числа
(γ
0
не прини-
мается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (
b
1
,
b
2
,
....
b
r
,
0, ..., 0) является оптимальным; соответствующее значение целевой функции
f
=
γ
0
. Если в
последней строке имеются положительные числа, перейти к п.2.
679
2. Просмотреть столбец, соответствующий положительному числу из последней строки, и
выяснить, имеются ли в нем положительные числа. Если ни в одном из таких столбцов положи-
тельных чисел нет, то оптимального решения не существует. Если найден столбец, содержащий
хотя бы один положительный элемент (если таких столбцов несколько, взять любой из них), поме-
тить этот столбец и перейти к п. 3.
3. Разделить свободные члены на соответствующие положительные числа из выделенного
столбца и выбрать наименьшее частное. Отметить строку таблицы, соответствующую наимень-
шему частному. Выделить разрешающий элемент, стоящий на пересечении отмеченных строки и
столбца. Перейти к п. 4.
4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на
месте разрешающего элемента появится единица). Полученная таким образом новая строка пи-
шется на месте прежней в новой таблице. Перейти к п. 5.
5. Каждая следующая строка новой таблицы образуется сложением соответствующей стро-
ки исходной таблицы и строки, записанной в п. 4. которая предварительно умножается на такое
число, чтобы в клетках выделенного столбца при сложении появились нули. На этом процесс за-
полнения новой таблицы заканчивается, и происходит переход к п. 1.
Таким образом, используя алгоритм симплекс-метода применительно к симплекс-таблице,
мы можем найти оптимальное решение или показать, что его не существует. Результативность
симплекс-метода гарантируется следующей теоремой (приведем ее без доказательства):
если су-
ществует оптимальное решение задачи линейного программирования, то существует и базисное
оптимальное решение. Это решение может быть получено через конечное число шагов симплекс-
методом, причем начинать можно с любого исходного базиса.
Ранее мы предполагали, что если система ограничений задана в виде (7.85),
то
перед пер-
вым шагом она уже приведена к виду (7.86), где
b
i
≥
0 (
i
= 1, 2, ...,
r).
Последнее условие необхо-
димо для использования симплекс-метода. Рассмотрим вопрос об отыскании начального базиса.
Один из методов его получения - метод симплексного преобразования.
Прежде всего проверяем, есть ли среди свободных членов отрицательные. Если свободные
члены не являются числами неотрицательными, то добиться
их неотрицательности можно не-
сколькими способами:
1) умножить уравнения, содержащие отрицательные свободные члены, на-1;
2) найти среди уравнений, содержащих отрицательные свободные члены, уравнение с мак-
симальным по абсолютной величине отрицательным свободным членом и затем сложить это
уравнение со всеми остальными, содержащими отрицательные свободные члены, предварительно
умножив его на-1.
Затем, используя действия, аналогичные указанным в пп. 3 - 5 алгоритма симплекс-метода,
совершаем преобразования исходной таблицы до тех пор, пока не получим неотрицательное ба-
зисное решение.
Пример 2.
Найти исходное неотрицательное базисное решение системы ограничений
Так как условие неотрицательности свободных членов соблюдается, приступим к преобра-
зованиям исходной системы, записывая результаты в таблицу. Согласно алгоритму просматрива-
ем первый столбец. В этом столбце имеется единственный положительный элемент
a
31
. Делим на
8,654 все коэффициенты и свободный член третьей строки, после чего умножаем каждый коэф-
фициент на 8,704 и складываем с соответствующими коэффициентами второй строки. Первая
строка преобразований не требует, так как коэффициент при неизвестном
x
1
равен нулю. В ре-
зультате получаем
0,00000
0,00000
1,00000
-5,87100
0,68512
-0,77756
6,54300
17,46384
0,97677
-9,99600
8,57990
0,89808
7,61800
-3,19062
0,62769
0,86400
9,79929
1,11584
680
Продолжая просматривать второй столбец и совершая аналогичные преобразования, имеем
0,00000
0,00000
1,00000
0,00000
1,00000
0,00000
156,19554
25,49013
20,79687
63,52761
12,52318
10,63560
-19,72328
-4,65701
-2,99341
84,83688
14,30299
12,24727
И, наконец, на третьем шаге находим исходный базис. Его образуют неизвестные
x
1
,
x
2
,
x
3
.
Неизвестные
x
4
, х
5
являются свободными:
0,00000
0,00000
1,00000
0,00000
1,00000
0,00000
1,00000
0,00000
0,00000
0,40672
2,15588
2,17713
-0,12627
-1,43829
-0,36733
0,54315
0,45815
0,95155
При решении задачи линейного программирования целесообразно использование компью-
тера. В этом случае можно составить программу, решающую задачу. Учитывая,
что программиро-
вание довольно трудоемко, можно посоветовать воспользоваться для оформления результатов
расчетов табличным процессором. Кроме того, если получившаяся модель задачи слишком гро-
моздка, можно воспользоваться математическими пакетами, которые позволяют получить реше-
ние задачи линейного программирования. И, наконец, еще один возможный вариант применения
компьютеров - комбинирование всех вышеуказанных способов.
Контрольные вопросы и задания
1. Приведите примеры задач, приводящих к общей постановке задачи линейного програм-
мирования.
2. Сформулируйте задачу линейного программирования.
3. Сколько решений может иметь задача линейного программирования?
4. По каким причинам может отсутствовать решение задачи линейного программирования?
5. Каким образом неравенства из системы ограничений можно заменить уравнениями? Как
задачу отыскания максимума линейной формы свести к задаче отыскания минимума?
6. Необходимо ли учитывать при записи решения дополнительные неизвестные, вводимые
при переходе от неравенств к уравнениям?
7. Как найти начальный базис?
8. Сформулируйте алгоритм симплекс-метода.
9. Сформулируйте теорему о конечности алгоритма симплекс-метода.
10. Найдите максимум функции
z
= 4
x
1
+3
x
2
(
x
i
≥
0) при условии
11. Для откорма крупного рогатого скота используется два вида кормов
b
1
и
b
2
,
в которые
входят питательные вещества
а
1
,
a
2
,
a
3
и
а
4
.
Содержание количеств единиц питательных веществ в
одном килограмме каждого корма, стоимость одного килограмма корма и норма содержания пита-
тельных веществ в дневном рационе животного представлены в таблице. Составьте рацион при
условии минимальной стоимости.
Питательные вещества
Вид кормов
Норма содержания
питательного вещества
b
1
b
2
a
1
3
4
24
a
2
1
2
18