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

Оптимизация как раздел математики существует достаточно давно и обозначает выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточнённое решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

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

Таким образом целью данной курсовой работы является : освоить навыки использования линейного программирования для решения задач оптимизации. Для этого были поставлены следующие задачи :

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

2)Изучить методы решения задач линейного программирования.

3)Решить поставленные задачи, используя рассмотренные методы линейного программирования.

I. Теоретический раздел

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

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

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

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

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

решения линейных задач оптимизации.

Формулировка задачи линейного программирования

Нужно максимизировать

$f(x)= \sum_{j=1}^n c_j x_j=c_1x_1+c_2x_2+\dots+c_nx_n$

при условиях

$\sum_{j=1}^n a_{ij}x_j \le b_i$

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

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

Такую задачу называют "основной" или "стандартной" в линейном программировании.

1.2 Виды задач линейного программирования

Поток и паросочетание

Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные x_ij — они соответствуют паре из i-того юноши и j-той девушки. Введем ограничения: x _ij ≥ 0, x _ij≤ 1, $x_{1i}+x_{2i}+\dots+x_{ni}\le 1$ , $x_{i1}+x_{i2}+\dots+x_{im}\le 1$ , $f=x_{11}+x_{12}+\dots+x_{nm}$ . Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить.

Вторая важная задача — максимальный поток. Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из стока в исток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Возьмем в качестве переменных x_i — количество жидкости, протекающих через i-тое ребро. Тогда $x_i\ge 0$ , $x_i\le c_i$ , где c_i — пропускная способность i-того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции f естественно взять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к 2 задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение $f(x)\ge m$ , где m — величина максимального потока, и решить задачу с новой функцией f(x) — стоимостью потока.

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

Транспортная задача

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

Ограничениями будут $x_{i1}+x_{i2}+\dots+x_{im}\le a_i$ и

$x_{1j}+x_{2j}+\dots+x_{nj}\ge b_j$ .

Целевая функция имеет вид: $f(x)=x_{11}c_{11}+x_{12}c_{12}+\dots+x_{nm}c_{nm}$ , которую надо минимизировать.

Игра с нулевой суммой

Есть матрица A размера $n\times m$ . Первый игрок выбирает число от 1 до n, второй — от 1 до m. Затем они сверяют числа и первый игрок получает a_ij очков, а второй ( − a_ij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью p_i. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: $p_i\ge 0$ , $p_i\le 1$ , $p_1+\dots+p_n=1$ , $a_{1i}p_1+a_{2i}p_2+\dots+a_{ni}p_n\ge c$ ( $i=1,\dots,m$ ), в которой нужно максимизировать функцию $f(p_1,\dots,p_n,c)=c$ . c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае.

1.3 Методы решения задач линейного программирования

Симплекс-метод

Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже.

Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества $X$ , описанного с помощью системы неравенств

$\begin{displaymath}a^ix \leq b_i, i = 1,2,\ldots,m \end{displaymath}$

крайними точками являются решения невырожденных подсистем вида:

$\begin{displaymath}a^ix = b_i, i \in S \quad a^ix &lt; b_i, i \notin S, \end{displaymath}$

(1)

где $S$ - некоторое подмножество индексов

$1,2,\ldots,\vert S \vert \geq n$

$\begin{displaymath}\vert S \vert = \mbox{dim}\,x = n \leq m \end{displaymath}$

и матрица, составленная из строк-векторов аⁱ, неособенная.

Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют $x' \in X$ и $x'' \in X$ такие, что для $0 &lt; \lambda &lt; 1$ $\begin{displaymath}x = \lambda x' + (1 - \lambda)x''. \end{displaymath}$ Поскольку для

$\begin{displaymath}a^ix' = a^ix'' = 0 = \lambda a^ix' + (1 - \lambda)a^ix'', \end{displaymath}$

то, очевидно, $a^ix' = a^ix'' = 0$ . В силу единственности решения (3) $x' = x'' = x$ .

С другой стороны, если $x$ -- крайняя точка, то можно обозначить через $S$ множество равенств

$\begin{displaymath}i \in S \Leftrightarrow a^ix = 0.\end{displaymath}$

Обозначим через $A_S$ матрицу, составленную из строк $a^i, i \in S.$ Если предположить, что $\mid S \mid &lt; n$ , то существует нетривиальное нуль-пространство

$\begin{displaymath}\lbrace z:A_Sz = 0 \rbrace.\end{displaymath}$ 2)

Выбирая $z$ достаточно малым по норме, можно добиться того, что для $x \in X$ вектор $x' = x + z \in X$ или $\begin{displaymath}a^ix' = a^ix = 0 + 0 = 0 \end{displaymath}$

для $i \in S$ и $\begin{displaymath}a^ix' = a^ix + a^ix + a^iz \geq a^ix -\Vert a^i \Vert \Vert z \Vert \geq \delta/2 &gt; 0\end{displaymath}$

для достаточно малых $\Vert z\Vert$ . Аналогично можно показать, что при этом и $x'' = x - z \in X$ . Так как $\begin{displaymath}x = \frac{1}{2}(x + z) + \frac{1}{2}(x - z), \end{displaymath}$ то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x₁, x₂, . . ., x_n на базисные $x^B_i &gt; 0$ и небазисные $x^N_j$ . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (x^B, x^N ).

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

$\begin{displaymath}Ax = A_Bx^B + A_Nx^B = b.\end{displaymath}$ (3)

Предположим, что матрица $A_B$ имеет полный ранг, т.е. $A_B$ - невырожденная. Тогда из равенства (5) следует

$\begin{displaymath}x^B = (A_B)^{-1}b.\end{displaymath}$ 4)

Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части:

$\begin{displaymath}cx = c_Bx^B + c_Nx^N.\end{displaymath}$

Подстановка (6) дает

$\begin{displaymath}cx = (c_N + c_B(A_B)^{-1}A_N) = d^Nx^N.\end{displaymath}$ 5)

Предположим, что мы находимся в некоторой начальной точке $x^0 = (x^B_0,0)$ со значением целевой функции

$\begin{displaymath}cx^0 = c_B(A_B)^{-1}b.\end{displaymath}$

Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора $x^N$ , которым соответствуют отрицательные значения координат вектора модифицированных стоимостей

$\begin{displaymath}d^N =c_N + c_B(A_B)^{-1}A^N, \end{displaymath}$

сохраняя при этом неотрицательность базисных переменных $x^B$ .

Увеличение $x^N$ может быть проделано различным образом, и за время существования симплекс-метода были проделаны многочисленные эксперименты по поиску наиболее эффективных стратегий увеличения $x^N.$

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

· среди компонент вектора $d^N = (_i, i \in N)$ находится минимальная;

· соответствующая небазисная переменная $x^N_i$ получает максимально возможное приращение, сохраняющее неотрицательность базисных переменных.

Поскольку при увеличении $i$ -й компоненты вектор $x^N$ приобретает вид:

$\begin{displaymath}x^N = \lambda e^i, \end{displaymath}$

где $e^i$ это $i$ -й орт, а $\lambda$ -- степень увеличения этой переменной или шаг алгоритма, то модифицированный базисный вектор выражается следующим образом:

$\begin{displaymath}x^B = (A_B)^{-1}b - \lambda(A_B)_{-1}A^Ne^i \equiv \beta - \lambda \alpha,\end{displaymath}$

где $\alpha$ - $i$ -й столбец матрицы $(A_B){-1}A^N.$ Шаг $\lambda$ определяется при этом из условия:

$\begin{displaymath}\beta - \lambda \alpha \geq 0.\end{displaymath}$

Максимально возможное значение $\lambda$ определится при этом как

$\begin{displaymath}\lambda = \min_{\alpha_i &gt; 0} \frac{\beta_i}{\alpha_i}.\end{displaymath}$ 6)

Пусть $k$ -- номер $i$ , на которой достигается минимум (6). Очевидно, что при этом

$\begin{displaymath}x^B_k = \beta_k - \lambda \alpha_k = 0.\end{displaymath}$

При этом говорят, что переменная $x^B_k$ выводится из базиса (обращается в нуль), а переменная $x^N_i$ вводится в базис. Целевая функция при этом уменьшается на величину

$\begin{displaymath}\delta cx = \lambda d^N_i.\end{displaymath}$

Важную роль в теории симплекс-метода играет условие невырожденности, в котором предполагается полный ранг A_Bи строгая положительность базисного решения β. При этом λ > 0 и δcx < 0, то есть целевая функция уменьшается при переходе к новому базису.

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

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

Геометрический метод

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

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

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c₁x₁+c₂x₂= а (1)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

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

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

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

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

Пусть имеются три линии уровня :

F=c₁x₁+ c₂x₂= а₁(I)

F=c₁x₁+ c₂x₂ = а₂ (II)

F=c₁x₁+ c₂x₂ = а₃(III)

Причём линия II заключена между линиями I и III. Тогда а₁ < а₂< а_{3 и}а₁ > а₂>а_3.

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

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c₁x₁+ c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

II. Практический раздел

2.1 Решение транспортной задачи

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

Решение:

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