Численные методы оптимизации. Рейзлин В.И. - 57 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

57
Требуется среди всех неотрицательных решений системы (7.8) найти та-
кое, которое сообщает форме
F
наименьшее значение (минимизирует
F
).
Естественно, что рассмотренные выше задачи не исчерпывают всех встре-
чающихся на практике типов задач линейного программирования. Тем не менее
они дают общее представление об их характере. Несмотря на внешнюю непохо-
жесть (в особенности по содержанию) задач 7.1 – 7.4, нельзя не заметить род-
ственности их математической формы. Более того, в следующем параграфе мы
покажем, что все эти различные примеры с помощью определенных приемов, в
конце концов, сводятся к одной и той же задаче. Она называется основной зада-
чей линейного программирования. К ее разбору мы и переходим.
7.2. Основная задача линейного программирования
Основная задача линейного программирования состоит в следующем. За-
дана система
11 1 1 1
21 1 2 2
11
,
,
...................................
nn
nn
m mn n m
a x a x b
a x a x b
a x a x b
(7.10)
m
линейных алгебраических уравнений с
n
неизвестными
1
,...,
n
xx
и линейная
форма относительно этих же неизвестных:
1 1 0
...
nn
F c x c x c
. (7.11)
Требуется среди всех неотрицательных решений системы (10) выбрать та-
кое, при котором форма F принимает наименьшее значение (минимизируется).
Определение: Система (7.10) называется системой ограничений данной за-
дачи.
Сами равенства (7.10) называются ограничениями-равенствами. Отметим,
что кроме ограничений-равенств в основу задач входят также ограничения-
неравенства
1
0,..., 0.
n
xx
Определение: Всякое неотрицательное решение
0 0 0
1
,..., 0; 1,...,
ni
x x x i n
системы (7.10) назовем допустимым. Допустимое
решение часто называют планом задачи линейного программирования.
Определение: Допустимое решение системы (7.10), минимизирующее
форму
F
, назовем оптимальным.
Рассмотрим следующие ограничения системы (7.10).
Задача имеет смысл лишь в том случае, когда система (7.10) совместна, то
есть когда (согласно теореме Кронекера-Капелли) ранги основной и расширен-
ной матриц системы совпадают. Этот общий ранг r не может превосходить чис-
ла
n
неизвестных. При
решение
00
1
,...,
n
xx
системы (7.10) единственно.
Если это решение допустимо, то оно является оптимальным, так как никаких

Страницы