Элементы дискретного математического анализа

Разбить на страницы

Показывать лекцию целиком

Элементы дискретного математического анализа

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

Рассмотрим численное решение уравнений.

Пусть дано уравнение f(x)=0, где функция f(x) непрерывна на отрезке [a;b] и дифференцируема на интервале (a;b). Предполагается, что корень уравнения существует и принадлежит данному отрезку.

Численным методом решения уравнений называют метод нахождения численных значений корней уравнения с заданной точностью.

Он состоит из двух частей:

отделение корней - нахождение интервалов, где локализованы корни, то есть в каждом таком интервале имеется ровно один корень;

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

Рассмотрим графический метод отделения корней. Отделение корней уравнения f(x)=0 графическим методом начинают с построения графика функции y=f(x). Абсциссы точек пересечения графика функции с осью абсцисс и есть корни уравнения. Иногда построить график функции y=f(x) достаточно сложно. Тогда уравнение f(x)=0 преобразовывают к виду f₁(x)=f₂(x) так, чтобы графики функций f₁(x) и f₂(x) было легче построить. Абсциссы точек пересечения этих графиков и есть корни уравнения.

При графическом отделении корней уравнения результат зависит от точности построения графиков. Поэтому используем аналитический численный метод отделения корней, основанный на следующем факте: если функция f(x) непрерывна на отрезке [a;b], принимает на концах этого отрезка значения противоположных знаков, а производная f'(x) на интервале (a;b) сохраняет постоянный знак, то внутри отрезка существует единственный корень уравнения f(x)=0. Этот критерий успешно применяется для уравнений f(x)=0, для которых знак производной определяется несложно.

Пример. Рассмотрим уравнение x³-3x-0,4=0 и отрезок [-2;-1]. Функция f(x)=x³-3x-0,4 непрерывна на данном отрезке. На концах отрезка функция принимает значения противоположных знаков: f(-2)= -2,4 и f(-1)=1,6. Очевидно, что для всех $$x\in (-2;-1)$$ производная f'(x)>0, так как f'(x)=3x²-3=3(x-1)(x+1). Следовательно, на интервале (-2;-1) находится корень уравнения и он единственный. Аналогично можно убедиться в том, что внутри отрезков [-1;0], [1;2] находится также по одному корню.

После отделения корней необходимо определить корни с их заданной точностью. Пусть неизвестный корень x=c уравнения f(x)=0 отделен, то есть дан отрезок [a;b], которому принадлежит только этот корень: $$c\in [a;b]$$. В качестве приближенного значения корня можно взять любую точку $$x\in [a;b]$$. Очевидно, что погрешность |c-x|<b-a. Отсюда следует, что для уточнения корня с заданной точностью h нужно сужать отрезок [a;b], пока его длина не станет меньше h.

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

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

Если корень с уравнения f(x)=0 отделен на отрезке [a;b], в качестве точки x₀, которую назовем нулевым приближением корня, выберем середину отрезка: x₀=(b+a)/2. Корень будет принадлежать тому из отрезков [a;x₀] и [x₀;b], на концах которого функция принимает значения противоположных знаков. Пусть, например, это [a;x₀] то есть $$f(a)f(x_0)<0$$, тогда корень находится на этом промежутке, и мы далее делим пополам этот промежуток (промежуток $$[x_0;b]$$, как не содержащий корень, выпал из дальнейшего рассмотрения). Сужают отрезок до тех пор, пока не получают отрезок длины, не превосходящий h.

Пример. Уточнить методом бисекции с точностью не менее h=0,01 корень уравнения f(x)=x³-3x-0,4 на [-2;-1]. Вычислим значения функции f(x) на концах отрезка [-2;-1] и выберем, в результате оценки их знаков, новую точку x={-1,5}. Таблица значений функции в серединах и на концах отрезков приведена ниже.

N	[a;b]	x	F(x)	F(a)	F(x)	F(b)
0	[-2;-1]	-1,5	0,725	-	+	+
1	[-2;-1,5]	-1,7	-0,213	-	-	+
2	[-1,7;-1,5]	-1,6	0,304	-	+	+
3	[-1,7;-1,6]	-1,65	0,058	-	+	+
4	[-1,7;-1,65]	-1,68	-0,102	-	-	+
5	[-1,68;-1,65]	-1,66	0,006	-	+	+
6	[-1,68;-1,66]	-1,67	-0,147	-	-	+
7	[-1,67;-1,66]	-1,665	-0,021	-	-	+

Мы получили отрезок [-1,67;-1,66], длина которого равна 0,01, и этот отрезок содержит корень уравнения. Числа -1,67 и -1,66 есть приближенные значения корня с погрешностью не более h=0,01. Примем за приближенное значение корня: x={-1,665} (проделали еще одно деление пополам).

Метод деления отрезка пополам удобен тогда, когда легко вычислить значения функции на концах отрезков и точность вычисления их не будет меньше требуемой точности корня. При уточнении приближенного значения корня уравнения f(x)=0 методом деления отрезка пополам всегда имеет место сходимость метода, то есть последовательность приближенных значений корня x₀,x₁,x₂,...,x_n, ... (полусумм) будет сходиться к корню x=c.

Есть много других методов отделения и уточнения корней. Отметим среди них еще один - метод итерации. Заменим уравнение f(x)=0 равносильным уравнением x=g(x). Выберем на отрезке [a;b], содержащем только один корень x=c, приближенное значение корня. Обозначим его через x₀ и назовем нулевым приближением. Каждое следующее приближение корня x_n+1 при заданной точности h будем вычислять по формуле: x_n+1=g(x_n), n=1, 2, .... Процесс приближений к корню продолжается до тех пор, пока мы не достигнем точности корня. Критерием достижения точности может быть отклонение двух последовательных приближений не более, чем на h: |x_n+1-x_n|<h.

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

Пусть на отрезке [a;b] известны значения функции f(x) в точках x₀<x₁<x₂<...<x_n, которые называются узлами интерполяции . Требуется построить функцию F(x), совпадающую в узлах интерполяции со значениями заданной функции f(x), то есть F(x₀)=f(x₀), F(x₁)=f(x₁), ..., F(x_n)=f(x_n). Способ построения функции F(x), принимающей в узлах интерполяции те же значения, что и функция f(x), называется методом интерполяции или интерполирования, а функция F(x) - интерполирующей функцией, интерполянтой.

Геометрически интерполяция состоит в нахождении по точкам M_i(x_i;y_i), i=1, 2,..., n на графике y=f(x), некоторой плавной кривой y=F(x), проходящей через эти точки и мало отклоняющейся от графика y=f(x) в других точках.

Таких функций может быть много - задача интерполяции не имеет единственного решения. Обычно стараются выбрать наиболее простую по форме и наиболее точную интерполянту, например, многочлен вида F(x)=a_nxⁿ+a_n-1x^n-1+a_n-2x^n-2+...+a₀. Покажем на примере, как находить интерполянту.

Пример. Пусть дана дискретная функция

x	y
0	1
1	-2
2	3

Подберем для этой функции интерполянту - многочлен 2-го порядка: F(x)=ax²+bx+c. Подставив значения в трех точках x=0, x=1, x=2 поочередно в функцию F(x), получаем систему из уравнений вида: F(0)=c=1, F(1)=a+b+c=-2, F(2)=4a+2b+c=3. Решая, мы найдем неизвестные коэффициенты интерполянты: a=4, b=-7, c=1, то есть найдем интерполянту F(x)=4x²-7x+1.

Рассмотрим задачу аппроксимации: задана табличная функция

`x_i`	`x₁`	`x₂`	`x₃`	`..`.	`x_n`
`y_i`	`y₁`	`y₂`	`y₃`	`..`.	`y_n`

Найти функцию z=f(x), легко вычисляемую и легко записываемую, которая приближенно заменяет (аппроксимирует) данную табличную функцию, причем в отличие от задачи интерполяции мы уже не требуем тут непосредственного совпадения с заданной табличной функцией в заданных точках. Достаточно лишь малого отклонения от них в этих точках, как и в любых других точках области задания функции.

Найденная при этом функция y=f(x) называется эмпирической функцией (или формулой), или аппроксимирующей функцией, математической моделью.

Мы рассмотрим нахождение эмпирической функции в виде многочлена P_n(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x+a₀.

Исследуемая величина y может зависеть также и от нескольких независимых факторов - x₁, x₂,..., x_n: y=y(x₁, x₂,..., x_n). Будем предполагать, что между x и y есть однозначное соответствие, которое и будем искать.

Пусть формула содержит неизвестные параметры функциональной зависимости, т.е. y=f(x, a₀, a₁,..., a_m). Конкретные числовые значения этих параметров, соответствующие данному набору y₁, y₂,..., y_n, выбирают из условия наилучшего, в каком-то смысле, согласования теоретических y(x_i) и экспериментальных y_i данных (i=1, 2,..., n). Наиболее широко применяемый критерий близости - критерий метода наименьших квадратов. Рассмотрим его на примере наиболее часто выбираемой в качестве эмпирической функции - многочлена y=P_m(x)=a₀+a₁x+...+ a_mx^m. Необходимо найти неизвестные параметры a_i, i=1, 2,...,n. Если бы измерения были точны, то для определения m+1 неизвестных a₀, a₁,..., a_m достаточно было бы сделать m+1 измерение - в точках x₁, x₂,..., x_m+1, затем подставить в формулу и получить систему m+1 линейных алгебраических уравнений вида: $$y_i=a_0+a_1x_i+a_2x_i+...+a_{mxi} ,\quad i=1, 2,..., m+1$$, которую можно решить, например, методом Гаусса. На практике же значения $$y_i$$, i=1,...,n искажены (допускаемыми приборами и методикой измерения), то есть на самом деле $$y(x_i)=y_i+\delta _i$$, i=1,2,..., n, где $$\delta _i$$ - ошибки измерений. Из этих равенств получаем$$\left. \begin{matrix} f(x_1, a_0, a_1, \dotsc, a_m) - y_1 =\delta _1 \hfill\null\\ \hdotsfor{1} \\ f(x_n, a_0, a_1, \dotsc, a_m) - y_n =\delta _n \hfill\null \end{matrix} \right \}.$$ Предполагаем, что $$n\ge m+1$$. Величины $$\delta _i$$ называются невязками . Числа a₀, a₁,..., a_m определяют из условия минимума суммы квадратов невязок:$$\min_A \sum^n_{i=1} \{ f(x_i,a_0,a_1, \dotsc, a_m) -y_i\}^2,$$ где A - множество всех допустимых значений параметров a₀, a₁,..., a_m.

Сумму можно рассматривать как функцию от m+1 параметра (параметров):$$\Phi(a_0,a_1, \dotsc, a_m) = \sum^n_{i=1} \{f(x_i, a_0,a_1, \dotsc, a_m) -y_i\}^2.$$

Из условия минимума этой суммы получаем систему так называемых нормальных уравнений (или нормальную систему уравнений):$$\frac{\partial\Phi}{\partial a_0} =0, \quad \frac{\partial\Phi}{\partial a_1} =0, \quad \dotsc, \quad \frac{\partial\Phi}{\partial a_m} =0.$$

В случае полинома получаем функционал вида$$\Phi = \sum^n_{i=1} \{a_0 + a_{1x1} + a_2x_i^2 + \dotsc + a_mx_i^m - y_i\}^2$$ и систему уравнений (нормальную систему):$$\left. \begin{matrix} \pd {\Phi}{a_0} = 2\sum^n_{i=1} (a_0 +a_1x_1 + \dotsc + a_mx_i^m) =0, \hfill\null\\ \pd {\Phi}{a_1} = 2\sum^n_{i=1} (a_0 +a_1x_1 + \dotsc + a_mx_i^m)x_i =0, \hfill\null\\ \hdotsfor{1} \\ \pd {\Phi}{a_m} = 2\sum^n_{i=1} (a_0 +a_1x_1 + \dotsc + a_mx_i^m)x_i^m =0. \hfill\null\\ \end{matrix} \right \}$$ Эту систему алгебраических линейных уравнений можно решить, например, методом Гаусса и найти неизвестные параметры a₀, a₁,..., a_m эмпирической формулы - многочлена.

Пример. Рассмотрим функцию, заданную нижеследующей таблицей.

x	1	1,5	1,7	1,8	2	3
y	200	300	400	500	800	1100

Будем искать линейную зависимость y=a₀x+a₁. Этот вид зависимости мы выбрали только по критерию наибольшей простоты, хотя по изменениям значений функции видно, что такая зависимость хорошо "работает" только при x=1,5 ; 1,7 ; 1,8 и совсем "плоха" для последних двух значений. Находим нормальную систему:$$\begin{cases} 22,38a_0 +11a_1 = 7130, \\ 11a_0 + 6a_1 = 3300. \end{cases}$$ Решим эту систему и находим: y=442,8x-261,8.

Рассмотрим теперь новый класс задач - численное вычисление определенных интегралов или численное интегрирование.

Пусть f(x) - непрерывная (а поэтому и интегрируемая) на отрезке [a;b] функция. Если F(x) есть первообразная для f(x) на интервале, содержащем отрезок [a;b], то задача интегрирования через элементарные функции для большинства функций разрешима. Если первообразная функция не выражается через элементарные функции ("интеграл не берется в квадратурах"), то нужно использовать численное интегрирование.

Задача численного интегрирования состоит в нахождении интеграла на отрезке [a;b] заменой подынтегральной функции f(x) на этом отрезке [a;b] другой, интерполирующей или аппроксимирующей функцией g(x) (например, многочленом).

Пусть функция f(x) считается заданной в n+1 равноотстоящих точках: a=x₀, x₁, x₂,..., x_n-1, x_n=b. Соответствующие значения равны: f(x_i)=y_i, i=0,1, 2,... n, h=x_i-x_i-1. Формула носит название формулы трапеции, так как при f(x)>0 приближенное значение интеграла слева получается в виде суммы площадей n трапеций:$$\int_{a}^{b} f(x)\,dx=h\Bigl(\frac{y_0+y_n}{2}+y_1+y_2+\dotsc+y_{n-1}\Bigr).$$

Пример. Вычислить интеграл от 0 до 1 от функции вида y=x²+sin (x/4). Используем точки x_i=0,i, i=0, 1,..., 10. Найдем значения функции (таблица).

`i`	`x_i`	`x_i/4`	`x₂+sin(x_i/4)`
0	0,00	0,000	0,00000
1	0,10	0,025	0,01044
2	0,20	0,050	0,04873
3	0,30	0,075	0,09131
4	0,40	0,100	0,16175
5	0,50	0,125	0,26218
6	0,60	0,150	0,36262
7	0,70	0,175	0,49305
8	0,80	0,200	0,64349
9	0,90	0,225	0.81393
10	1,00	0,250	1.00436

По формуле трапеций получаем$$\int_{0}^{1} \Bigl(x^2+\sin \frac {x}{4} \Bigr)\,dx \approx 0{,}1 \Bigl(\frac {1{,}004}{2} + 0{,}010+0{,}0049 + \dotsc + 0{,}814 \Bigr) = 0{,}3386.$$

Так как точное значение интеграла также можно вычислить приближенно:$$\int_{0}^{1} \Bigl(x^2+\sin \frac {x}{4} \Bigr)\,dx = \Bigl(\frac {x^3}{3}-4\cos \frac {x}{4} \Bigr) \Bigr|^1_0 = 0{,}333,$$ то относительная погрешность вычисления интеграла не больше 1,5%.

Рассмотрим следующую задачу - численное дифференцирование или численное вычисление производной. Можно вычислить производную любой функции, если она задана аналитически. Для функции, заданной сложным образом или таблично, используют какую-либо интерполяционную функцию. После ее нахождения, дифференцируют найденную функцию (интерполяционная функция представляет собой, как правило, многочлен, поэтому ее дифференцирование не вызывает трудностей).

Решим теперь задачу нахождения наибольшего (наименьшего) значения функции f(x) на заданном отрезке [a;b]. Это задача одномерной оптимизации. Один из простых и эффективных методов поиска минимума такой функции - метод золотого сечения. Он состоит в построении последовательности отрезков [a_i;b_i] ; i=0, 1, 2,..., стягивающихся к одной точке минимума функции f(x). Вначале выбираются две точки $$x_1$$, $$x_2$$ из [a₀;b₀] и вычисляются f(x₁), f(x₂). Минимум достигается в одном из отрезков, прилегающих к x₁ (считаем для определенности f(x₁)<f(x₂) ), поэтому отбрасываем [x₂;b₀]. На втором шаге выбираем a₁=a ; b₁=x₂ и т.д. Процесс продолжается до тех пор, пока длина очередного отрезка [a_n;b_n] не станет меньше заданного малого числа e - точности нахождения минимума. Точки x_i размещаются на отрезке [a_i;b_i] так, чтобы выполнялось правило золотого сечения: $$c_1=0,618c$$ ; $$c_2=0,38c$$, где c - длина оставляемого интервала [a_i;b_i].

Если оптимизируемая функция - дважды непрерывно дифференцируема, то отыскание минимума функции f(x) производится с помощью стационарной точки, то есть точки x^* удовлетворяющей уравнению f'(x^*)=0 при помощи метода Ньютона. Если x_k - точка, полученная на k -ом этапе, то функция f'(x) аппроксимируется своим уравнением касательной z=f'(x_k)+(x-x_k) f''(x_k), а точка x_k+1 выбирается как пересечение этой прямой с осью Ox (рис. 13.1):$$x_{k+1} = x_k - \frac {f'(x_k)}{f''(x_k)}.$$

(рис 13.1) Схема оптимизации Ньютона

Пример. Вычислительные эксперименты методом Ньютона для функции f(x)=sin x+0,25 на отрезке [0; 3,14] при e=0,0005. Строим таблицу:

`N`	`k`	`x₀`	`x^*`	`x_k`	`f(x*)`
1	12	0	1,2501	1,2509	1,5707
2	9	0,1	1,2500	1,2508	1,5706
3	8	0,4	1,2501	1,2509	1,5708
4	6	1	1,2500	1,2507	1,5707

Точность равна |1,2497-1,2508|=0,0011.

Рассмотрим задачу численного решения обыкновенного дифференциального уравнения, а именно, задачи Коши для уравнения первого порядка: y'(x)=f(x,y), y(x₀)=y₀ на отрезке [a;b] . Идея всех приближенных методов решения этой задачи состоит в том, что отрезок [a;b] разбивается на части точками x_i, i=0, 1, ..., n, x₀=a, x_n=b и производная на каждом из таких отрезков заменяется (аппроксимируется) его дискретным приближением с какой-то точностью. Наиболее простая схема аппроксимации уравнения - схема Эйлера: $$y_{i+1}=y_i+hf(x_i,y_i), \quad i=0{,}1,2,\dotsc, n$$.

Пример. Решить задачу Коши: y'=2(x²+y), y(0)=1, 0<x<1. Разобьем отрезок [0;1] на 10 равных частей, то есть h=0,1. Вычисления по схеме Эйлера дают приближенное решение (приведено в таблице).

`i`	`x_i`	Приближенное решение	Точное решение
0	0,00	1,00	1,00
1	0,10	1,20	1,22
2	0,20	1,44	1,50
3	0,30	1,74	1,84
4	0,40	2,10	2,28
5	0,50	2,56	2,83
6	0,60	3,12	3,52
7	0,70	3,81	4,39
8	0,80	4,67	5,49
9	0,90	5,74	6,86
10	0,10	7,05	8,58

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

Теорема. Множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n -мерном пространстве.

Пример. Построим множество решений системы линейных неравенств:$$\begin{cases} x_1+x_2-3\le 0,\\ x_1+x_2 -1\ge 0, \\ x_1-x_2 \ge 0, \\ x_1\le 2,5, \\ 0\le x_2\le 1. \end{cases}$$

Построим прямые x₁+x₂=3 ; x₁+x₂=1 ; x₁=x₂ ; x₁=2,5 ; x₂=0 ; x₂=1. Заштрихованная область (рис. 13.2) соответствует искомому многоугольнику.

(рис 13.2) Множество решений системы неравенств

Точки A, B, C, D, E, F - угловые точки множества. Такие точки примечательны и тем, что если отыскивается наибольшее или наименьшее значение линейной функции при указанных ограничениях, условиях типа неравенств (в этом выпуклом множестве), то это значение достигается только в угловых точках. Например, если мы ищем минимум значений функции y=3x₁+4x₂ при указанных выше ограничениях, то его нужно выбирать из значений y(A)=y(2;1)=6+4=10 ; y(B)=y(2;5)=26 ; y(C)=y(2,5;0)=7,5 ; y(D)=y(1;0)=3 ; y(E)=y(0,5;0,5)=3,5 ; y(F)=y(1;1)=7. Следовательно, наименьшее значение функции при заданных выше ограничениях будет равно 3, и она принимает это значение в точке D. Наибольшее значение y=26 будет достигаться в точке B. Координаты всех точек были найдены совместным решением уравнений двух прямых, пересекающихся в этой точке, например, для нахождения координат точки E решалась система:$$\begin{cases} x_1+x_2 = 1, \\ x_1-x_2 = 0. \end{cases}$$

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

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

Пример(Транспортная модель). Пусть некоторая продукция, например, сталь, производится на заводах $$\text{З}_1, \text{З}_2, \dotsc, \text{З}_m$$. Пусть a_i - ежегодный выпуск стали на i -ом заводе $$\text{З}_i$$. Пусть эта сталь требуется на рынках P_j, j=1, 2, ..., n. Ежегодная потребность j -ого рынка в стали равна b_j. Пусть c_ij - стоимость перевозки единицы товара с завода $$\text{З}_i$$ на рынок P_j, а рынки и заводы соединены некоторыми путями. Задача состоит в определении такого плана перевозок, при котором:

удовлетворяется спрос b_j на каждом рынке P_j ;

не превышается предложение a_i каждого завода $$\text{З}_i$$ ;

минимальна полная цена S всех перевозок.

План перевозок состоит из mn неотрицательных чисел x_ij, где x_ij - количество продукции, которое должно перевозиться от $$\text{З}_i$$ на P_j. Тогда сумма - полное количество продукции, привозимой на рынок P_j. Условие 1) записывается в виде:$$\sum^m_{i=1}x_{ij} \ge b_j, \quad j=1{,}2,\dotsc, n.$$ Полное количество продукции, вывозимое из завода $$\text{З}_i$$ на все рынки P_j, равно сумме всех x_ij по всем рынкам и по всем заводам (по всем i=1,2,..., m ; j=1,2,...,n ) и, таким образом, условие 2) эквивалентно соотношению$$\sum^n_{j=1} x_{ij} \le a_i, \quad i=1{,}2,\dotsc, m.$$ Цена всех перевозок между всеми $$\text{З}_i$$ и P_i равна$$\sum^n_{j=1} \sum^m_{i=1} c_{ij}x_{ij}$$ и, следовательно, условие 3) можно записать в виде: $$S\to min$$.

При этом должны быть выполнены естественные условия:

неотрицательности перевозимой продукции: $$x_{ij}\ne 0$$ ;

предложение не должно быть меньше спроса:$$\sum^n_{j=1} b_j \le \sum^m_{i=1} a_i.$$

Следовательно, данная экономическая (транспортная) задача сведена к математической задаче: минимизировать линейную целевую функцию S при линейных ограничениях, выраженных вышеприведенными неравенствами. Минимум функции S является конечной целью оптимального планирования (получения минимальной стоимости перевозок). Эта функция называется целевой функцией транспортной задачи, она описывает (скалярно) степень достижения цели.

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

Страницы: