Основы математического программирования (стр. 3 )

Z(m2) = -2000*0 + 0*0,3 + 2000*0,5 + 2000*0,2 = 1400

Z(m3) = -3000**0,3 + 1000*0,5 + 3000*0,2 = 800

Отсюда оптимальное решение m* = m2

3. Условия конфликта.

Здесь вводится предположение о том, что для любых mi – uj будет наименее благоприятной.

Поэтому здесь выбирают «наименьшее зло». Выписываются минимумы строк.

m1 → -1000 m2 → -2000 m3 → -3000

Из которых выбирается максимум. (что соответствует стратегии m1).

4. Условия неопределенности.

Здесь нет информации для предсказания значения и. поэтому приходится использовать методы искусственного снятия неопределенности.

4.1. Критерий Лапласа-Байеса. Предполагается, что вероятности наступления различных состояний среды равны между собой.

т. е. P(ui) = 0,25, для всех i.

Тогда столбец Г выглядит следующим образом:

Z(m1) = 0,25*(-1000 + 1000 + 1000 + 1000) = 500

Z(m2) = 0,25*(-2000 + 0 + 2000 + 2000) = 500

Z(m3) = 0,25*(-3+ 1000 + 3000) = 0

Здесь две оптимальные стратегии m1 и m2.

4.2. Критерий Вальда.

(Пессимистический или максиминный)

Ситуация сводится к ситуации в условиях конфликта.

Z(mi) = min Yij

j

m* = m1

4.3. Оптимистический (или максимаксный)

Z(m1) = 1000, Z(m2) = 2000, Z(m3) = 3000, Z(mi) = max Yij

j

m* = m3

4.4. Критерий Гурвица (или смешанный критерий, строящийся на основе оптимистического и пессимистического критериев)

Z(mi) = α min Yij + (α -1) max Yij

j j

α – «степень пессимизма» (при α = 1 критерий превращается в критерий Вальда, при α = 0 – в оптимистический.)+

Пусть α = 0,3, что ближе к оптимистическому критерию.

Z(m1) = -1000*0,3 + 1000*0,7 = 400

Z(m2) = -2000*0,3 + 2000*0,7 = 800

Z(m3) = -3000*0,3 + 3000*0,7 = 1200

m* = m3

Раздел 2. Линейное программирование

2.1. Метод Жордана-Гаусса

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

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

Система m линейных уравнений с n переменными имеет вид:

{

a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 …………………………………………….. am1xl + am2xl + … + amnxn = bm

(1)

aij (i = 1, 2, …, m; j = 1, 2, …, n) – произвольные числа, называемые коэффициентами при переменных.

bi (i =1, 2, …, m) – произвольные числа, называемые свободными членами.

В более краткой форме:

n

∑ aijxj = bi (i = 1, 2, …, m)

j = 1

Решением системы называется такая совокупность n чисел (x1 = k1, x2 = k2, …, xn = kn), при подстановке которых каждое уравнение системы превращается в верное равенство.

Система уравнений называется совместной, если имеет хотя бы одно решение.

Несовместной – если не имеет решения.

Совместная система называется определенной, если она имеет единственное решение.

Неопределенной – если решений больше одного.

Две системы называются равносильными или эквивалентными, если имеют одно и тоже множество решений

Систему линейных уравнений можно записать в матричной форме:

А =

(

a11 а21…а1n a21 a22 … a2n …………….. am1 am2 … amn

)

X =

(

x1 x2 … xn

)

B =

(

b1 b2 … bm

)

А – матрица коэффициентов при переменных или матрица системы;

X – матрица-столбец переменных;

В – матрица-столбец свободных членов.

Так как число столбцов матрицы Аmxn равно числу строк матрицы Хnx1, то их произведение есть матрица-столбец.

На основании определения равенства матриц можно записать:

АХ = В

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

А|B =

(

a11 а2 1… а1n b1 a21 a22 … a2n b2 …………….. am1 am2 … amn bm

)

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

1. На каждом шаге выбирается любой разрешающий элемент аrs≠ 0

где r-я строка называется разрешающей строкой

s-й столбец - разрешающим столбцом

2. Все элементы разрешающего столбца, кроме аrs, становятся равными нулю.

3. Все элементы разрешающей строки делятся на разрешающий элемент.

4. Остальные элементы находятся по правилу прямоугольника

а'ij = aij – (ais* arj)/ars

Заменяемый элемент	aij	__________________________	ais
				Разрешающий столбец
	arj	__________________________	ars	Разрешающий элемент
		Разрешающая строка

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

Задача. Методом Жордана-Гаусса решить систему уравнений.

{

– 3x1 – 7x2 – 8x3 + 2x4 = – 4 x1 + 3x2 + 4x3 – 2x4 = 2 2x1 – x2 + 3x3 = 4 2x1 + 4x2 + 4x3 = 2

1. Выпишем расширенную матрицу.

(

-3 1 3 4 -2 2

-4 2 4 2

)

А|B =

(

a11 а2 1… а1n b1 a21 a22 … a2n b2 …………….. am1 am2 … amn bm

)

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

Например а21.

3. Так как а21=1, то элементы второй строки не меняются. В новой матрице элементы первого столбца, кроме а'21 = а21 =1, становятся равными нулю.

4. Другие элементы новой матрицы находятся по правилу прямоугольника.

а'12 = - 7 – (3*-3)/1 = -7 + 9 =2

а'13 = -8 – (4*-3)/1 = -8 + 12 = 4

a'14 = 2 – (-2*-3)/1 = 2 -6 = -4

a'15 = -4 – (2*-3)/1 = 2

a'32 = -1 – (2*3)/1 = -7

a'33 = 3 – (2*4)/1 = -5

a'34 = 0 – (-2*2)/1 = 4

a'35 = 4 – (2*2)/1 = 0

a'42 = 4 – (3*2)/1 = -2

a'43 = 4 – (4*2)/1 = -4

a'44 = 0 – (-2*2)/1 = 4

a'45 = 2 – (2*2)/1 = -2

Новая матрица имеет вид:

(

0 2 4 -4 0 0

2 2 0 -2

)

5. В качестве разрешающего элемента выберем а12. (любой элемент ≠ 0, любой строки, кроме второй).

6. Делим все элементы разрешающей (первой) строки на а21 = 2. Новые элементы второго столбца, кроме а''12 будут равны нулю. Другие элементы находим по правилу прямоугольника.

а''23 = 4 – (3*4)/2 = 4 – 6 = -2

a''24 = -2 – (3*-4)/2 = -2 + 6 = 4

a''25 = 2 – (3*2)/2 = 2 -3 = - 1

a''33 = -5 – (-7*4)/2 = -5 + 14 = 9

a''34 = *-4)/2 = 4 – 14 = -10

a''35 = 0 – (2*-7)/2 = 0 + 7 = 7

a''43 = -4 – (4*-2)/2 = -4 + 4 = 0

a''44 = 4 – (-4*-2)/2 = 4 – 4 = 0

a''45 =*2)/2 = -2 + 2= 0

Новая матрица имеет вид:

(

1 0 -2 4 0 0 9 -10 0 0 0 0

1 -1 7 0

)

7. В качестве разрешающего элемента выбираем а33, вычеркиваем строку состоящую из нулевых элементов. Пересчитываем элементы.

a14 = -2 – (-10*2)/9 = -2 +20/9 = 2/9

a15 = 1 – (7*2)/9 = - 5/9

a24 = 4 –(-2*-10)/9 = 4 – 20/9 = 16/9

a25 = -1 – (7*-2)/9 = 5/9

Новая матрица имеет вид:

(

0 1 0 2/9 1 0 0 16/9 0 0 1 -10/9

-5/9 5/9 7/9

)

8. Так как все строки матрицы брались в качестве разрешающих, выпишем систему уравнений, соответствующую последней матрицы

{	х2 + 2/9х4 = -5/9 x1 + 16/9x4 = 5/9 x3 – 10/9x4 = 7/9

Полагая неосновную переменную х4 = с, получаем решение системы

х1 = 5/9 – 16/9c; x2 = -5/9 – 2/9c; x3 = 7/9 -10/9c; x4 = c

Базисное решение при с = 0

2.2. Практическое занятие. Метод Жордановых исключений

Решить систему уравнений

х1 + 2х2 + 3х3 = 6

2х1 – 3х2 + х3 = 0

3х1 – 2х2 + 4х3 = 5

х1 – х2 + 3х3 = 3

Ответ: (1, 1, 1)

3х1 – х2 + 2х3 = 2

4х1 – 3х2 + 3х3 = 3

х1 + 3х2 = 0

5х1 + 3х3 = 3

Ответ: (-3с, с, 5с + 1) с – любое число

2.3. Практическое занятие. Метод Жордановых исключений

Решить систему уравнений

3х1 – 2х2 + 3х3 – 3х4 = 0

3х1 – 2х2 – х3 + х4 = 0

х1 – х2 + 2х3 + 5х4 = 0

Ответ: (14с; 21с; с; с) с – любое число

2х1 + х2 + х3 + х4 = 1

х2 – х3 + 2х4 = 2

2х1 + 2х2 + 3х4 = 3

Ответ: (- с1 +1/2c2 – 1/2; с1 – 2с2 + 2; с1; с2) с1, с2 – любые числа

Найти базисное решение системы уравнений:

х1 + 2х2 – х3 = 5

2х1 – х2 – 3х3 = – 4 (- 3/5; 14/5;; 0; 14) (0; 19/7; 3/7)

3х1 + х2 – х3 – 2х4 = – 4

х1 + х2 – х3 + 2х4 = 1

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

Повторение.

В 1947 г. Американский ученый Дж. Данциг описал один из основных методов решения задач линейного программирования, получивший название «симплексный».

Построение модели экономической задачи включает в себя следующие этапы:

1. выбор переменных задачи;

2. составление системы ограничений;

3. выбор целевой функции.

Переменными задачи называются величины х1, х2, ,,,, хn, которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора. Х = (х1, х2, ,,,, хn).

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

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

Общая задача математического программирования формулируется следующим образом:

Найти экстремум целевой функции Z(X) = f(х1, х2, ,,,, хn) → max (min)

И соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений:

{	φi (х1, х2,…хn ) = 0, i =1, 2, …, l φi (х1, х2,…хn ) ≤(≥) 0, i =l+1, l+2, …, m

Если целевая функция и система ограничений линейны, то задача математического программирования называется задачей линейного программирования.

_________________________________________________________________________

В общем случае задача линейного программирования может быть записана в виде:

{	Z(X) = c1x1 + c2x2 + … + cnxn →max (min) (1) a11x1 + a12x2 + … + a1nxn = b1 (2) ………………………………………………… al1xl + al2xl + … + alnxn = bl a(l+1)1xl + a(l+1)2xl + … + a(l+1)nxn ≤ bl+1 ……………………………………………….. am1xl + am2xl + … + amnxn ≤ bm xj ≥ 0, j = 1, 2, … , t, t ≤ n (3)

Данная запись означает следующее: найти экстремум целевой функции задачи (1) и соответствующие ему переменные X (х1, х2,…хn ) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3)

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

Применим необходимое условие экстремума функции, которое состоит в том, что частные производные функции многих переменных или равны нулю, или не существуют.

В данном случае

∂Z/∂xi = ci = 0, i = 1, 2, …, n

Но если все сi =0,то и Z = 0, т. е. экстремум функции не обнаруживается.

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

Основная задача линейного программирования (ОЗ.

Ставится следующим образом.

Имеется рад переменных

х1, х2, …, xn

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

{	a11x1 + a12x2 + … + a1nxn = b1 (4) a21x1 + a22x2 + … + a2nxn = b2 ……………………………………………. am1x1 + am2x2 + … + amnxn = bm

Или в матричной форме

АХ = В

И, кроме того, обращали бы в минимум линейную функцию

Z = c1x1 + c2x2 + … + cnxn (5)

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

Z* = – c1x1 – c2x2 – …– cnxn

Условимся называть допустимым решением ОЗ любую совокупность переменных

x1 ≥ 0, х2 ≥ 0, …, хn ≥ 0

удовлетворяющую системе уравнений (4).

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

Основная задача линейного программирования не обязательно должна иметь решение. Может оказаться, что уравнения (4) противоречат друг другу или они имеют решение, но не в области неотрицательных значений х1, х2, …, xn. Тогда ОЗ не имеет допустимых решений. Может оказаться, что допустимые решения ОЗ существуют, но среди них нет оптимального: функция Z в области допустимых решений не ограничена снизу.

Рассмотрим вопрос о существовании допустимых решений ОЗ.

Наличие допустимых решений определяется только системой (4).

Рассмотрим понятие ранга матрицы.

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

Для совместимости системы линейных уравнений (4) необходимо и достаточно, чтобы ранг матрицы системы был равен рангу ее расширенной матрицы.

Если система уравнений-ограничений ОЗ совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг. Этот общий ранг называется рангом системы, он представляет собой число линейно независимых уравнений среди наложенных ограничений.

Очевидно, что ранг системы r не может быть больше числа уравнений m.

r ≤ m

Очевидно также, что ранг системы не может быть больше общего числа переменных

r ≤ n

Структура задачи линейного программирования существенно зависит от ранга системы ограничений (4).

Рассмотрим случай, когда r = n, т. е. когда число линейно независимых уравнений, входящих в систему (4), равно числу независимых переменных.

Если отбросить избыточные уравнений, являющиеся линейными комбинациями других, то система уравнений-ограничений ОЗ принимает вид (т. е. здесь m = n)

{	a11x1 + a12x2 + … + a1nxn = b1 (6) a21x1 + a22x2 + … + a2nxn = b2 ……………………………………………. an1x1 + an2x2 + … + annxn = bn

Так как r = n, то и определитель, составленный из коэффициентов не равен нулю.

Из алгебры известно, что в этом случае система (6) имеет единственное решение.

Итак, при r = n система уравнений-ограничений ОЗ имеет единственное решение:

х1 = с1, х2= с2 , …, xn = сn

Если в этом решении хотя бы одна из величин с1, с2, сn отрицательна, то полученное решение не допустимо и, значит ОЗ не имеет решение.

Если все величины с1, с2, сn неотрицательны, то найденное решение является допустимым. Оно же является оптимальным, поскольку единственное.

Очевидно, что этот случай тривиален.

В дальнейшем будем рассматривать только случаи, когда r < n, т. е. когда число уравнений, которым должны удовлетворять переменные х1, х2, …, xn меньше числа самих переменных.

Тогда, если система совместна, у нее существует бесчисленное множество решений.

При этом n – r переменным можно придавать произвольные значения (свободные переменные), а остальные r переменных выражаются через них.

Эти r переменные называются базисными.

Таким образом, если ранг системы уравнений ОЗ равен r, то всегда можно выразить какие-то r базисных переменных через n-r остальных и, придавая свободным переменным любые значения, получить бесчисленное множество решений системы.

В дальнейшем, записывая уравнения ОЗ, мы будем считать их линейно-незавиcимыми; при этом ранг системы будет равен числу уравнений m.

Заключение.

1. Если число уравнений m = r меньше, чем число переменных n, то система уравнений имеет бесчисленное множество решений, т. е. совокупностей значений х1, х2, …, xn, удовлетворяющих уравнениям-ограничениям (6). Если среди них нет ни одного, для которого все х1, х2, …, xn неотрицательны, то это значит, что ОЗ не имеет допустимого решения.