Реферат: Использование линейного программирования для решения задач оптимизации

--PAGE_BREAK--I. Теоретический раздел 1.1 Понятие о линейном программировании. Формулировка задачи линейного программирования


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

Линейное программирование является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования.

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

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

решения линейных задач оптимизации.
Формулировка задачи линейного программирования
Нужно максимизировать
<img border=«0» width=«306» height=«46» src=«ref-1_846731760-2278.coolpic» alt=«f(x)= \sum_{j=1}^n c_j x_j=c_1x_1+c_2x_2+\dots+c_nx_n» v:shapes="_x0000_i1030">
при условиях
<img border=«0» width=«79» height=«37» src=«ref-1_846734038-895.coolpic» alt="\sum_{j=1}^n a_{ij}x_j \le b_i" v:shapes="_x0000_i1031">


при i= 1, 2, 3,… ., m..

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

Такую задачу называют «основной» или «стандартной» в линейном программировании.
1.2 Виды задач линейного программирования Поток и паросочетание
Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные xij — они соответствуют паре из i-того юноши и j-той девушки. Введем ограничения: xij≥ 0, xij≤ 1, <img border=«0» width=«204» height=«17» src=«ref-1_846734933-1254.coolpic» alt=«x_{1i}+x_{2i}+\dots+x_{ni}\le 1» v:shapes="_x0000_i1032">, <img border=«0» width=«210» height=«17» src=«ref-1_846736187-1250.coolpic» alt=«x_{i1}+x_{i2}+\dots+x_{im}\le 1» v:shapes="_x0000_i1033">, <img border=«0» width=«222» height=«20» src=«ref-1_846737437-1436.coolpic» alt=«f=x_{11}+x_{12}+\dots+x_{nm}» v:shapes="_x0000_i1034">. Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Вторая важная задача — максимальный поток. Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из стока в исток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Возьмем в качестве переменных xi — количество жидкости, протекающих через i-тое ребро. Тогда <img border=«0» width=«55» height=«17» src=«ref-1_846738873-572.coolpic» alt=«x_i\ge 0» v:shapes="_x0000_i1035">, <img border=«0» width=«49» height=«12» src=«ref-1_846739445-484.coolpic» alt=«x_i\le c_i» v:shapes="_x0000_i1036">, где ci — пропускная способность i-того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции f естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к 2 задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение <img border=«0» width=«86» height=«23» src=«ref-1_846739929-1356.coolpic» alt=«f(x)\ge m» v:shapes="_x0000_i1037">, где m — величина максимального потока, и решить задачу с новой функцией f(x) — стоимостью потока.

Все эти задачи могут быть решены быстрее, чем с помощью общих алгоритмов решения задач линейного программирования, за счет особой структуры уравнений и неравенств.
    продолжение
--PAGE_BREAK--Транспортная задача
Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нем находится груза ai, а для каждого завода известна его потребность bj в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния cij от i-го склада до j-го завода известны). Требуется составить наиболее дешевый план перевозки. Решающими переменными в данном случае являются xij — количества груза, перевезенного из i-го склада на j-й завод.

Ограничениями будут <img border=«0» width=«216» height=«17» src=«ref-1_846741285-1529.coolpic» alt=«x_{i1}+x_{i2}+\dots+x_{im}\le a_i» v:shapes="_x0000_i1038">и
<img border=«0» width=«216» height=«23» src=«ref-1_846742814-1570.coolpic» alt=«x_{1j}+x_{2j}+\dots+x_{nj}\ge b_j» v:shapes="_x0000_i1039">.
Целевая функция имеет вид: <img border=«0» width=«325» height=«23» src=«ref-1_846744384-1888.coolpic» alt=«f(x)=x_{11}c_{11}+x_{12}c_{12}+\dots+x_{nm}c_{nm}» v:shapes="_x0000_i1040">, которую надо минимизировать.
Игра с нулевой суммой
Есть матрица A размера <img border=«0» width=«52» height=«9» src=«ref-1_846746272-488.coolpic» alt=«n\times m» v:shapes="_x0000_i1041">. Первый игрок выбирает число от 1 до n, второй — от 1 до m. Затем они сверяют числа и первый игрок получает aij очков, а второй ( − aij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью pi. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: <img border=«0» width=«55» height=«20» src=«ref-1_846746760-635.coolpic» alt=«p_i\ge 0» v:shapes="_x0000_i1042">, <img border=«0» width=«55» height=«20» src=«ref-1_846747395-605.coolpic» alt=«p_i\le 1» v:shapes="_x0000_i1043">, <img border=«0» width=«147» height=«20» src=«ref-1_846748000-1075.coolpic» alt=«p_1+\dots+p_n=1» v:shapes="_x0000_i1044">, <img border=«0» width=«259» height=«17» src=«ref-1_846749075-1767.coolpic» alt=«a_{1i}p_1+a_{2i}p_2+\dots+a_{ni}p_n\ge c» v:shapes="_x0000_i1045">(<img border=«0» width=«101» height=«17» src=«ref-1_846750842-414.coolpic» alt=«i=1,\dots,m» v:shapes="_x0000_i1046">), в которой нужно максимизировать функцию <img border=«0» width=«164» height=«23» src=«ref-1_846751256-1512.coolpic» alt=«f(p_1,\dots,p_n,c)=c» v:shapes="_x0000_i1047">. c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.
1.3 Методы решения задач линейного программирования Симплекс-метод
Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже.

Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества <img border=«0» width=«17» height=«14» src=«ref-1_846752768-533.coolpic» alt="\( X \)" v:shapes="_x0000_i1048">, описанного с помощью системы неравенств
<img border=«0» width=«176» height=«29» src=«ref-1_846753301-759.coolpic» alt="\begin{displaymath}a^ix \leq b_i, i = 1,2,\ldots,m \end{displaymath}" v:shapes="_x0000_i1049">
крайними точками являются решения невырожденных подсистем вида:

<img width=«236» height=«30» src=«ref-1_846754060-1785.coolpic» hspace=«12» alt="\begin{displaymath}a^ix = b_i, i \in S \quad a^ix < b_i, i \notin S, \end{displaymath}" v:shapes="_x0000_s1026">

 (1)
где <img border=«0» width=«14» height=«14» src=«ref-1_846755845-537.coolpic» alt="\(S\)" v:shapes="_x0000_i1050">- некоторое подмножество индексов


<img border=«0» width=«121» height=«32» src=«ref-1_846756382-598.coolpic» alt="\(1,2,\ldots,\vert S \vert \geq n\)" v:shapes="_x0000_i1051">
и
<img border=«0» width=«156» height=«29» src=«ref-1_846756980-743.coolpic» alt="\begin{displaymath}\vert S \vert = \mbox{dim}\,x = n \leq m \end{displaymath}" v:shapes="_x0000_i1052">
и матрица, составленная из строк-векторов аi, неособенная.

Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют <img border=«0» width=«55» height=«18» src=«ref-1_846757723-1144.coolpic» alt="\(x' \in X\)" v:shapes="_x0000_i1053">и <img border=«0» width=«58» height=«9» src=«ref-1_846758867-613.coolpic» alt="\(x'' \in X\)" v:shapes="_x0000_i1054">такие, что для <img border=«0» width=«78» height=«9» src=«ref-1_846759480-637.coolpic» alt="\(0 < \lambda < 1\)" v:shapes="_x0000_i1055"> <img border=«0» width=«156» height=«17» src=«ref-1_846760117-1341.coolpic» alt="\begin{displaymath}x = \lambda x' + (1 — \lambda)x''. \end{displaymath}" v:shapes="_x0000_i1056">Поскольку для <img border=«0» width=«31» height=«12» src=«ref-1_846761458-560.coolpic» alt="\(i \in S\)" v:shapes="_x0000_i1057">



<img border=«0» width=«279» height=«19» src=«ref-1_846762018-1817.coolpic» alt="\begin{displaymath}a^ix' = a^ix'' = 0 = \lambda a^ix' + (1 — \lambda)a^ix'', \end{displaymath}" v:shapes="_x0000_i1058">
то, очевидно, <img border=«0» width=«109» height=«23» src=«ref-1_846763835-1415.coolpic» alt="\(a^ix' = a^ix'' = 0\)" v:shapes="_x0000_i1059">. В силу единственности решения (3) <img border=«0» width=«81» height=«20» src=«ref-1_846765250-1141.coolpic» alt="\(x' = x'' = x\)" v:shapes="_x0000_i1060">.

С другой стороны, если <img border=«0» width=«12» height=«14» src=«ref-1_846766391-310.coolpic» alt="\(x\)" v:shapes="_x0000_i1061">-- крайняя точка, то можно обозначить через <img border=«0» width=«14» height=«14» src=«ref-1_846755845-537.coolpic» alt="\(S\)" v:shapes="_x0000_i1062">множество равенств
<img border=«0» width=«124» height=«26» src=«ref-1_846767238-617.coolpic» alt="\begin{displaymath}i \in S \Leftrightarrow a^ix = 0.\end{displaymath}" v:shapes="_x0000_i1063">
Обозначим через <img border=«0» width=«26» height=«15» src=«ref-1_846767855-571.coolpic» alt="\(A_S\)" v:shapes="_x0000_i1064">матрицу, составленную из строк <img border=«0» width=«70» height=«24» src=«ref-1_846768426-1294.coolpic» alt="\(a^i, i \in S.\)" v:shapes="_x0000_i1065">Если предположить, что <img border=«0» width=«63» height=«21» src=«ref-1_846769720-1245.coolpic» alt="\(\mid S \mid < n\)" v:shapes="_x0000_i1066">, то существует нетривиальное нуль-пространство
<img border=«0» width=«107» height=«29» src=«ref-1_846770965-555.coolpic» alt="\begin{displaymath}\lbrace z:A_Sz = 0 \rbrace.\end{displaymath}" v:shapes="_x0000_i1067">2)
Выбирая <img border=«0» width=«12» height=«14» src=«ref-1_846771520-301.coolpic» alt="\(z\)" v:shapes="_x0000_i1068">достаточно малым по норме, можно добиться того, что для <img border=«0» width=«40» height=«26» src=«ref-1_846771821-621.coolpic» alt="\(x \in X\)" v:shapes="_x0000_i1069">вектор <img border=«0» width=«107» height=«9» src=«ref-1_846772442-1127.coolpic» alt="\(x' = x + z \in X\)" v:shapes="_x0000_i1070">или <img border=«0» width=«170» height=«26» src=«ref-1_846773569-1654.coolpic» alt="\begin{displaymath}a^ix' = a^ix = 0 + 0 = 0 \end{displaymath}" v:shapes="_x0000_i1071">

для <img border=«0» width=«60» height=«20» src=«ref-1_846775223-1306.coolpic» alt="\(i \in S\)" v:shapes="_x0000_i1072">и <img border=«0» width=«374» height=«29» src=«ref-1_846776529-1502.coolpic» alt="\begin{displaymath}a^ix' = a^ix + a^ix + a^iz \geq a^ix -\Vert a^i \Vert \Vert z \Vert \geq \delta/2 > 0\end{displaymath}" v:shapes="_x0000_i1073">

для достаточно малых <img border=«0» width=«23» height=«17» src=«ref-1_846778031-606.coolpic» alt="\(\Vert z\Vert\)" v:shapes="_x0000_i1074">. Аналогично можно показать, что при этом и <img border=«0» width=«72» height=«15» src=«ref-1_846778637-1136.coolpic» alt="\(x'' = x — z \in X\)" v:shapes="_x0000_i1075">. Так как <img border=«0» width=«173» height=«26» src=«ref-1_846779773-1581.coolpic» alt="\begin{displaymath}x = \frac{1}{2}(x + z) + \frac{1}{2}(x — z), \end{displaymath}" v:shapes="_x0000_i1076"> то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x= x1, x2,… ., xnна базисные <img border=«0» width=«55» height=«21» src=«ref-1_846781354-1179.coolpic» alt="\(x^B_i > 0\)" v:shapes="_x0000_i1077">и небазисные <img border=«0» width=«26» height=«23» src=«ref-1_846782533-624.coolpic» alt="\(x^N_j\)" v:shapes="_x0000_i1078">. Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x= (xB, xN).

Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде:
<img border=«0» width=«173» height=«23» src=«ref-1_846783157-1671.coolpic» alt="\begin{displaymath}Ax = A_Bx^B + A_Nx^B = b.\end{displaymath}" v:shapes="_x0000_i1079">(3)
Предположим, что матрица <img border=«0» width=«35» height=«18» src=«ref-1_846784828-1092.coolpic» alt="\(A_B\)" v:shapes="_x0000_i1080">имеет полный ранг, т.е. <img border=«0» width=«35» height=«18» src=«ref-1_846784828-1092.coolpic» alt="\(A_B\)" v:shapes="_x0000_i1081">  — невырожденная. Тогда из равенства (5) следует
<img border=«0» width=«109» height=«29» src=«ref-1_846787012-579.coolpic» alt="\begin{displaymath}x^B = (A_B)^{-1}b.\end{displaymath}" v:shapes="_x0000_i1082">4)
Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части:
<img border=«0» width=«150» height=«29» src=«ref-1_846787591-1421.coolpic» alt="\begin{displaymath}cx = c_Bx^B + c_Nx^N.\end{displaymath}" v:shapes="_x0000_i1083">
Подстановка (6) дает
<img border=«0» width=«268» height=«29» src=«ref-1_846789012-1115.coolpic» alt="\begin{displaymath}cx = (c_N + c_B(A_B)^{-1}A_N) = d^Nx^N.\end{displaymath}" v:shapes="_x0000_i1084">5)




Предположим, что мы находимся в некоторой начальной точке <img border=«0» width=«101» height=«15» src=«ref-1_846790127-1334.coolpic» alt="\(x^0 = (x^B_0,0)\)" v:shapes="_x0000_i1085">со значением целевой функции
<img border=«0» width=«135» height=«29» src=«ref-1_846791461-692.coolpic» alt="\begin{displaymath}cx^0 = c_B(A_B)^{-1}b.\end{displaymath}" v:shapes="_x0000_i1086">
Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора <img border=«0» width=«26» height=«17» src=«ref-1_846792153-590.coolpic» alt="\(x^N\)" v:shapes="_x0000_i1087">, которым соответствуют отрицательные значения координат вектора модифицированных стоимостей
<img border=«0» width=«190» height=«29» src=«ref-1_846792743-868.coolpic» alt="\begin{displaymath}d^N =c_N + c_B(A_B)^{-1}A^N, \end{displaymath}" v:shapes="_x0000_i1088">
сохраняя при этом неотрицательность базисных переменных <img border=«0» width=«26» height=«17» src=«ref-1_846793611-589.coolpic» alt="\(x^B\)" v:shapes="_x0000_i1089">.

Увеличение <img border=«0» width=«26» height=«17» src=«ref-1_846792153-590.coolpic» alt="\(x^N\)" v:shapes="_x0000_i1090">может быть проделано различным образом, и за время существования симплекс-метода были проделаны многочисленные эксперименты по поиску наиболее эффективных стратегий увеличения <img border=«0» width=«32» height=«17» src=«ref-1_846794790-604.coolpic» alt="\(x^N.\)" v:shapes="_x0000_i1091">

Здесь будет рассмотрена простейшая:

·                     среди компонент вектора <img border=«0» width=«132» height=«17» src=«ref-1_846795394-1528.coolpic» alt="\(d^N = (_i, i \in N)\)" v:shapes="_x0000_i1092">находится минимальная;

·                     соответствующая небазисная переменная <img border=«0» width=«35» height=«18» src=«ref-1_846796922-1067.coolpic» alt="\(x^N_i\)" v:shapes="_x0000_i1093">получает максимально возможное приращение, сохраняющее неотрицательность базисных переменных.

Поскольку при увеличении <img border=«0» width=«9» height=«14» src=«ref-1_846797989-295.coolpic» alt="\(i\)" v:shapes="_x0000_i1094">-й компоненты вектор <img border=«0» width=«26» height=«17» src=«ref-1_846792153-590.coolpic» alt="\(x^N\)" v:shapes="_x0000_i1095">приобретает вид:
<img border=«0» width=«72» height=«29» src=«ref-1_846798874-436.coolpic» alt="\begin{displaymath}x^N = \lambda e^i, \end{displaymath}" v:shapes="_x0000_i1096">
где <img border=«0» width=«17» height=«17» src=«ref-1_846799310-534.coolpic» alt="\(e^i\)" v:shapes="_x0000_i1097">это <img border=«0» width=«9» height=«14» src=«ref-1_846799844-295.coolpic» alt="\(i\)" v:shapes="_x0000_i1098">-й орт, а <img border=«0» width=«14» height=«14» src=«ref-1_846800139-317.coolpic» alt="\(\lambda \)" v:shapes="_x0000_i1099">-- степень увеличения этой переменной или шаг алгоритма, то модифицированный базисный вектор выражается следующим образом:


<img border=«0» width=«314» height=«29» src=«ref-1_846800456-1263.coolpic» alt="\begin{displaymath}x^B = (A_B)^{-1}b — \lambda(A_B)_{-1}A^Ne^i \equiv \beta — \lambda \alpha,\end{displaymath}" v:shapes="_x0000_i1100">
где <img border=«0» width=«14» height=«14» src=«ref-1_846801719-316.coolpic» alt="\(\alpha\)" v:shapes="_x0000_i1101">- <img border=«0» width=«9» height=«14» src=«ref-1_846802035-295.coolpic» alt="\(i\)" v:shapes="_x0000_i1102">-й столбец матрицы <img border=«0» width=«86» height=«29» src=«ref-1_846802330-1538.coolpic» alt="\((A_B){-1}A^N.\)" v:shapes="_x0000_i1103">Шаг <img border=«0» width=«14» height=«14» src=«ref-1_846803868-317.coolpic» alt="\(\lambda \)" v:shapes="_x0000_i1104">определяется при этом из условия:
<img border=«0» width=«89» height=«29» src=«ref-1_846804185-505.coolpic» alt="\begin{displaymath}\beta — \lambda \alpha \geq 0.\end{displaymath}" v:shapes="_x0000_i1105">
Максимально возможное значение <img border=«0» width=«14» height=«14» src=«ref-1_846803868-317.coolpic» alt="\(\lambda \)" v:shapes="_x0000_i1106">определится при этом как
<img border=«0» width=«89» height=«43» src=«ref-1_846805007-1462.coolpic» alt="\begin{displaymath}\lambda = \min_{\alpha_i > 0} \frac{\beta_i}{\alpha_i}.\end{displaymath}" v:shapes="_x0000_i1107">6)
Пусть <img border=«0» width=«12» height=«14» src=«ref-1_846806469-317.coolpic» alt="\(k\)" v:shapes="_x0000_i1108">-- номер <img border=«0» width=«9» height=«14» src=«ref-1_846806786-295.coolpic» alt="\(i\)" v:shapes="_x0000_i1109">, на которой достигается минимум (6). Очевидно, что при этом
<img border=«0» width=«150» height=«29» src=«ref-1_846807081-693.coolpic» alt="\begin{displaymath}x^B_k = \beta_k — \lambda \alpha_k = 0.\end{displaymath}" v:shapes="_x0000_i1110">
При этом говорят, что переменная <img border=«0» width=«23» height=«23» src=«ref-1_846807774-1046.coolpic» alt="\(x^B_k\)" v:shapes="_x0000_i1111">выводится из базиса (обращается в нуль), а переменная <img border=«0» width=«23» height=«35» src=«ref-1_846808820-1130.coolpic» alt="\(x^N_i\)" v:shapes="_x0000_i1112">вводится в базис. Целевая функция при этом уменьшается на величину
<img border=«0» width=«84» height=«29» src=«ref-1_846809950-1279.coolpic» alt="\begin{displaymath}\delta cx = \lambda d^N_i.\end{displaymath}" v:shapes="_x0000_i1113">
Важную роль в теории симплекс-метода играет условие невырожденности, в котором предполагается полный ранг ABи строгая положительность базисного решения β. При этом λ > 0 и δcx< 0, то есть целевая функция уменьшается при переходе к новому базису.

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

В силу выпуклости задачи любое другое оптимальное решение будет иметь также значение целевой функции, т.е. будет в этом смысле эквивалентно.
    продолжение
--PAGE_BREAK--Геометрический метод


<img border=«0» width=«385» height=«276» src=«ref-1_846811229-8283.coolpic» v:shapes="_x0000_i1114">
Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n= 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных nбольше числа уравнений mна 2, т. е. n– m= 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE(рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F= a, или
c1x1+c2x2 = а (1)
линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

Именно так и надо поступать при геометрическом решении задач линейного программирования. на многоугольнике решений следует найти точку, через которую проходит линия уровня функции Fс наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F– это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :
F=c1x1 + c2x2 = а1 (I)

F=c1x1 + c2x2= а2 (II)

F=c1x1 + c2x2= а3 (III)
Причём линия IIзаключена между линиями Iи III. Тогда а1 < а2 < а3 и а1 > а2 >а3.

В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.
<img width=«410» height=«314» src=«ref-1_846819512-1712.coolpic» v:shapes="_x0000_s1027 _x0000_s1028 _x0000_s1029 _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047">
Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c1x1 + c2x2, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).
II. Практический раздел 2.1 Решение транспортной задачи


Имеются два склада с сырьём. Ежедневно вывозится с первого склада 60 т сырья, со второго – 80 т. сырьё используется двумя заводами, причём первый завод получает – 50 т, а второй – 90 т. нужно организовать оптимальную (наиболее дешёвую) схему перевозок, если известно, что доставка 1 т сырья с первого склада на первый завод стоит 7 рублей, с первого склада на второй завод – 9 рублей, со второго склада на первый завод – 10 рублей, со второго склада на второй завод – 8 рублей.

Решение:

Обозначим через х1, х2 количество сырья, который нужно доставить с первой базы соответственно на первый, второй заводы, а через х3, хколичество сырья, который нужно доставить со второй базы соответственно на первый, второй заводы. Составим выражения, которые в соответствии с исходными данными должны удовлетворять следующим условиям:

<img width=«14» height=«142» src=«ref-1_846821224-210.coolpic» v:shapes="_x0000_s1048">


х1 +х2 = 60;

х3 + х4 = 80;(1)

х1 +х3 = 50;

х2 +х4 = 90.
Первое и второе уравнения описывают количество сырья, которое необходимо вывезти с первого и второго складов, а третье и четвёртое – сколько нужно завести сырья на первый и второй заводы. К данной системе уравнений нужно добавить систему неравенств:
хi ≥ 0, где i = 1,. ., 4, (2)


которая означает, что сырьё обратно с заводов на склады не вывозится. Тогда общая стоимость перевозок с учётом приведённых в таблице расценок выразится формулой :
f= 7х1 + 9х2 + 10х3 + 8х4. (3)
Таким образом, мы пришли к типичной задаче линейного программирования: найти оптимальные значения проектных параметров хi(i= 1,. ., 4), удовлетворяющим условиям (2), (3) и минимизирующим стоимость перевозок (3).

Из анализа системы уравнений (1) следует, что только первые два уравнения являются независимыми, а последние можно получить из них. Поэтому фактически имеем систему :
<img width=«14» height=«110» src=«ref-1_846821434-181.coolpic» v:shapes="_x0000_s1049">х1 +х2 = 60;

х3 + х4 = 80;(4)

х3 = 50 — х1;

х4 = 90 — х2.
Поскольку в соответствии с (2) все проектные параметры должны быть неотрицательны, то с учётом (4) получим следующую систему неравенств:
х1 ≥ 0, х2 ≥ 0, 50 — х1 ≥ 0, 90 — х2 ≥ 0.
Эти неравенства можно записать в более компактном виде :
0≤ х1 ≤ 50, 0≤ х2 ≤ 90. (5)
Данная система неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных параметров х1 и х2 нужно найти оптимальные, минимизирующие целевую функцию f
. Формула (3) для неё с учётом соотношений (4) принимает вид
f= 7х1 + 9х2 + 10(50 — х1)+ 8(90 — х2);

f= -3х1 + х2 + 1220.
Отсюда следует, что стоимость перевозок уменьшается с увеличением значений х1; поэтому нужно взять его наибольшее допустимое значение. В соответствии с (5) х1= 50, тогда получим, что х2 = 60 — х1 = 10. Тогда оптимальные значения остальных параметров можно найти по формулам (4):
х3 = 50 — х1 =50 – 50 = 0, х4 = 90 — х2 = 90 – 10 = 80.
В этом случае минимальная общая стоимость перевозок равна :
f= 7*50 + 9*10+ 10*0+ 8*80 = 350 + 90 + 0 + 640 = 1080.
То есть, минимальная общая стоимость перевозок f
= 1080.

Покажем на рисунке схему доставки сырья на заводы. (Числа указывают количество сырья в тоннах).
<img width=«354» height=«176» src=«ref-1_846821615-1901.coolpic» v:shapes="_x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061"> 
    продолжение
--PAGE_BREAK--