Методы оптимальных решений

Размещено на http://www.allbest.ru/

Федеральное агентство железнодорожного транспорта

Федеральное государственное образовательное учреждение высшего профессионального образования

«Петербургский Государственный Университет Путей Сообщения Императора Александра I»

Кафедра «Математика и моделирование»

Контрольная работа по дисциплине

«Методы оптимальных решений»

Выполнил: Студент

учебной группы 14 ЭБС - 230

Евдокимова Н.Н.

Санкт - Петербург, 2016



Задание 1.

Для функции двух переменных

,

заданной следующим выражением:

Задачи, поставленные в задании:

a. Найти стационарную точку и вычислить в ней значение функции;

b. Найти экстремальные точки и экстремальные значения;

c. Найти области выпуклости (вогнутости) функции.

Решение

a) Для нахождения стационарной точки найдем частные производные, прировняем их к 0, вычислим систему уравнений, так найдем координаты стационарной точки.

= 7*2x₁+2x₂+1;

= 2x₁+5*2x₂ - 10;

;

;

;

;

Точка M с координатами (-15/68; 71/68) - стационарная точка.

Значение функции двух переменных

в точке M вычислено при помощи Microsoft Excel.

Z (-15/68 ; 71/68) = ?10 ;

b) Чтобы найти экстремальные точки и экстремальные значения найдем частные производные второго порядка.

Обозначим:

A = =14

;

= 10

и через

? = AC - B² = 14*10 ?2² = 136;

? ? 0;



Так как ? ? 0, и A ? 0 то по достаточному условию экстремума функция Z имеет в точке М (-15/68 ; 71/68) минимум, причем значение функции Z = ?10;

c) Так как функция Z дважды дифференцируема и Z''(x₁;x₂) ? 0, то функция Z - выпуклая.

Ответ:

1. Точка M с координатами (-15/68; 71/68) - стационарная точка.

Значение функции в точке M равно = ?10

2. Функция Z имеет в точке М (-15/68 ; 71/68) минимум.

3. Функция Z - выпуклая.



Задание 2

Функция трех переменных задана следующим выражением.

Задачи, поставленные в задании:

a. Найти стационарную точку функции и вычислить в ней ее значение;

b. Найти экстремальные точки и экстремальные значения функции;

c. Найти области выпуклости (вогнутости) функции.

Решение:

a) Найдем частные производные.

= 6x₁ + 2x₂ - x₃ + 4;

= 4x₂ + 2x₁ + 5x₃ - 1; = 10x₃ - x₁ + 5x_2;

Составим и решим систему уравнений для нахождения стационарных точек.

Решив систему уравнений при помощи Microsoft Excel, с помощью обратной матрицы, найдены корни уравнений.

x₁ = -3,27;

x₂ = 6,12;

x₃ = -3,38

Найдена одна стационарная точка M (-3,27; 6,12; -3,38)

Значение функции U в точке M равно, U = 135,37

b) Чтобы найти экстремальные точки и экстремальные значения найдем частные производные второго порядка.

= 6;

= 2;

= -1;

= 2;

= 4;

= 5;

= -1;

= 5;

10;

Составим матрицу Гессе:

H =

Продолжение решения через анализ угловых миноров матрицы Гессе.

Достаточные условия экстремума. Если в некоторой точке выполнены необходимые условия экстремума и все частные производные 2-го порядка непрерывны, то существование экстремума в этой точке определяется значениями угловых миноров матрицы вторых производных (матрицы Гессе):



M1 ? 0 , M2 ? 0 - локальный минимум;

M1 ? 0 , M2 ? 0 - локальный максимум;

M2 ? 0 - экстремума нет.

Так как угловые миноры: M₁ = 15; M₂ = 10, следовательно на основании достаточного условия экстремума, функция

в точке M (-3,27; 6,12; -3,38) имеет локальный минимум.

c) Достаточным условием выпуклости функции f (x1, x2, …, xn) является положительная определенность матрицы.

Составим главные определители матрицы Гессе.

?₁ = 15;

?₂ = 10;

?₃ = 59;

Так как все определители ? 0, то матрица H положительно определена и функция

выпуклая.

Ответ:

1. Найдена одна стационарная точка M (-3,27; 6,12; -3,38)

Значение функции

в точке M равно, U = 135,37

2. В точке M (-3,27; 6,12; -3,38) имеет локальный минимум.

3. По критерию Сильвестра, матрица H положительно определена и функция

выпуклая.



Задание 3

Даны функция

и ограничения.

Задачи, поставленные в данном задании.

a. Составить функцию Лагранжа;

b. Найти стационарную точку функции Лагранжа;

c. Найти условный экстремум функции

(экстремальную точку, экстремальное значение и тип экстремума.)

Решение:

a) Составить функцию Лагранжа.

Используем метод множителей Лагранжа:

Обозначив

ц₁(x₁,x₂,x₃) = 4x₁ - 2x₂ + 2x₃

ц₂(x₁,x₂,x₃) = 7x₁ + 5x₂ - 3x₃

где ц_i(x) - ограничения в неявном виде (i=1..n), что аргументы функции связаны уравнением

j (x , y , z) = 0 , называемым уравнением связи.

экстремальный лагранж линейный программирование

Функция Лангранжа имеет вид:

L(x_1,x₂,…,x_n) = f(x_1,x₂,…,x_n) +

Константы л_k ,(k = 1,….,m) называют множителями Лагранжа.

В качестве целевой функции, подлежащей оптимизации является

Функция Лагранжа имеет вид:

L(x₁,x₂,x_3x,л) = 12x₁² + 9x₂² + 5x1₁x₂ - 9x₁x₃ - 2x₂x₃ - 35x₁ - 60x₂ + 20x₃ + л₁(4x₁ - 2x₂ + 2x₃ - 200) + л₂(7x₁ + 5x₂ - 3x₃ - 400)

b) Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным x_i неопределенным множителям л.

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

;

Необходимые условия условного экстремума выражаются системой

Решение системы даёт координаты точки (или системы точек), в которой возможен условный экстремум.

Решив данную систему уравнений с помощью Microsoft Excel, получим

x₁ =47,99;

x₂ = 38,07;

x₃ = 42,09;

л₁ = 24,29;

л₂ = -146,49;

Мы получили одну стационарную точку M (-0,28;1,85;2,41).

c) Выяснить, условный минимум или условный максимум имеет функция в найденной точке, можно, как и ранее, необходимо вычислить матрицу Гессе для точки M.

Дана функция

Найдем частные производные :

= 24x₁ + 5x₂ - 9x₃ - 35;

= 18x₂ + 5x₁ - x₃ - 60;

= 4x₃ - 9x₁ - 2x₂ + 20;



Прировняв частные производные к 0, составим систему уравнений и найдем координаты стационарной точки.

Получили стационарную точку: M (-3,15; 3,64; -10.27)

Найдем второй частный дифференциал:

= 24;

= 5;

= -9;

= 5;

= 18;

= -2;

= -9;

= -1;

= 4;

Достаточное условие экстремума функции:

Используем второй дифференциал.

d²f = f_x1x1''dx₁² + 2f_x1x2''dx₁dx₂ + 2f_x1x3''dx₁dx₃ +2f_x2x3''dx₂dx₃ + f_x2x2''dx² + f_x3x3''dx₃²

d²f = 24 + 2*5 + 2*(-9) + 2*(-1) + 18 + 4 = 36



В стационарной точке

M (-3,15; 3,64; -10.27) d²f > 0,

эта точка локального минимума.

Значение функции в данной точке равно

f (-3,15; 3,64; -10.27) = -138,026

Ответ:

1. Функция Лагранжа имеет вид:

L(x1,x2,x3x,л) = 12x12 + 9x22 + 5x11x2 - 9x1x3 - 2x2x3 - 35x1 - 60x2 + 20x3 + л1(4x1 - 2x2 + 2x3 - 200) + л2(7x1 + 5x2 - 3x3 - 400)

2. Cтационарная точка функции Лангранжа M (-0,28;1,85;2,41).

И собств. числа: л1 = 24,29; л2 = -146,49

3. В стационарной точке M (-3,15; 3,64; -10.27) d2f > 0, эта точка локального минимума.

Значение функции в данной точке равно f (-3,15; 3,64; -10.27) = -138,026



Задание 4

Составить математическую модель и найти оптимальное решение, используя процедуру «поиск решения» («solver») MS Excel.

Условие задачи:

Двум погрузчикам равной мощности за 24 часа нужно погрузить на первой площадке 230 т, на второй 168 т. Первый погрузчик на первой площадке может погрузить 10 т в час, на второй - 12 т. Второй погрузчик на каждой площадке может погрузить по 13 т в час. Стоимость погрузки 1 т первым погрузчиком на первой площадке равна 8 тыс. руб., на второй 7 тыс. руб., вторым погрузчиком на первой площадке - 12 тыс. руб., на второй - 13 тыс. руб. Первый погрузчик на второй площадке может работать не более 16 час. Найти такой план работ, чтобы стоимость работ была минимальной.

Решение:

Введем обозначения:

х₁₁ - время работы первого погрузчика на первой площадке;

х₁₂ - время работы первого погрузчика на второй площадке;

х₂₁ - время работы второго погрузчика на первой площадке;

х₂₂ - время работы второго погрузчика на второй площадке.

х₁₁ 0, х₁₂ 0, х₂₁ 0, х₂₂ 0.

По условию, первый погрузчик на второй площадке может работать не более 16 часов, значит:

х₁₂16

Ограничения на лимиты рабочего времени:

на первой площадке необходимо погрузить 230 т.:



х₁₁ + х₂₁ = 230;

на второй площадке необходимо погрузить 168 т., т.е.:

х₁₂ + х₂₂ = 160

Составим математическую модель задачи:

Общая стоимость погрузки (целевая функция):

F =8000х₁₁+7000 х₁₂+12000 х₂₁+13000 х₂₂

Найти такой план работ, чтобы стоимость работ была минимальной:

F(x₁₁, x₁₂, x₂₁, x₂₂) =8000х₁₁+7000 х₁₂+12000 х₂₁+13000 х₂₂>min.

При ограничениях на переменные:

х₁₁+ х₂₁ = 230,

х₁₂+ х₂₂ = 168,

х₁₁ /10+ х₁₂ /12 24,

х₂₁ /13+ х₂₂ /13 24,

х₁₁ /10+ х₂₁ /13 24,

х₁₂ /12+ х₂₂ /13 24,

х_ij 0;

х₁₂ /1216;

Для решения задачи воспользуемся помощью процедуры «Поиск решения» MS Excel.



Рис. №1

Итак, по оптимальному плану первый погрузчик должен погрузить 100 т. на первой площадке и 168 т. на второй, второму погрузчику надлежит погрузить 130 т. на первой площадке. Стоимость всех работ составит 3536 тыс. руб.

Ответ:

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

Первый погрузчик должен отработать на первой площадке 10 часов, на второй - 14. Второй погрузчик - 10 часов на первой площадке.

Минимальная стоимость работ составляет 3 536 тыс. руб.



Задание 5

Дана задача линейного программирования, в которой

max f = 2x₁ + 5x₂

x₁ ; x₂ 0;

Задачи, поставленные в данном задании:

a. Записать задачу в канонической и стандартной формах;

b. Записать каноническую и стандартную задачи в матричном виде;

c. Решить задачу линейного программирования геометрически;

d. Решить задачу линейного программирования симплекс-методом;

e. Составить двойственную задачу к первоначальной задаче и найти ее решение.

Решение:

a) Запись ЗЛП в канонической форме:

Для приведения задачи к канонической форме, где все ограничения имеют вид равенств, вводят дополнительные переменные

x_n+1, x_n+2,…,x_n+p ,

которые тоже считаются неотрицательными и записывают исходную задачу в виде

c₁x₁+c₂x₂+…+c_nx_n+0*x_n+1+0*x_n+2+…+0*x_n+p => min

Введем дополнительные переменные x₃, x₄, x₅. Переводя мах в min, запишем задачу в виде:

-2*x₁ - 5*x₂ + 0*x₃ +0*x₄ +0*x₅ => min;

;

x₁>0, x₂>0, x₃>0, x₄>0, x₅>0;

Запись ЗЛП в стандартной форме:

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

c₁x₁ + c₂x₂ +…+c_nx_n =>max

то, умножая её на (- 1), приведем её к виду:

(-c₁)x1 +(- c₂ )x₂ +…+(-c_n )x_n =>min

Таким образом, получаем:

min f = - 2x₁ - 5x₂

x₁ ; x₂ 0;

b) Запись канонической задачи в матричном виде:

Найти минимальное значение функции

f(x) = CX, при условиях ,

где C = (-2; -5; 0; 0; 0) - вектор - строка коэффициентов при переменных.

X = (x₁, x₂, x₃, x_4, x₅ ), Х ? 0

A = (a_ij)_m*n - матрица размерности m*n, столбцами которой являются вектор-столбцы A_j.

A = ;

B = ;

Запись стандартной задачи в матричном виде:

Найти максимальное значение функции

f(x) = CX,

при условиях

AX ? B ,

Где C = (-2; -5), X = (x₁, x₂), Х?0,

A = ;

B = ;

c) Решение ЗЛП графическим методом.

max f = 2x₁ + 5x₂

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

Так как x_i0, то рассмотрим только первую координатную четверть.

Определяем полуплоскости, задаваемые неравенствами. Для этого в неравенства подставляем координаты любой точки, не лежащей на соответствующей прямой. Если неравенство верное, то штрихуем в сторону выбранной точки. В результате построений получаем многоугольник B₀EIB₄(рис. 1).

Построим прямую, отвечающую значению функции f = 0.

2x₁ + 5x₂= 0

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации f(X). Начало вектора - точка (0; 0), конец - точка (2; 5).

Будем двигать эту прямую(перпендикулярную к вектору - градиенту), параллельным образом. Так как ищется максимальное значение целевой функции f(x), поэтому двигаем прямую до последнего касания области B₀EIB₄.

Максимального значения целевая функция достигает в точке I. Точка I получена, в результате пересечения прямых (2) и (3), находим ее координаты, решая систему уравнений:

Решив систему уравнений, получим: x₁ = 4, x₂= 5

Можно найти максимальное значение целевой функции:

f_max(x) = 2*4 + 5*5 = 33

d) Решить задачу линейного программирования симплекс-методом

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

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

Определим максимальное значение целевой функции

f(x) = 2x₁ + 5x₂

при следующих условиях-ограничениях.

Перейдем к канонической форме записи ЗЛП и составим матрицу коэффициентов.

Матрица коэффициентов A = a(ij) имеет вид:

A =

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

Решим систему уравнений относительно базисных переменных: x3, x4, x5

Полагая, что свободные переменные равны 0, получим первый опорный план:

x₁= (0,0,8,4,5)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5
x3	8	1	-2	1	0	0
x4	4	1	0	0	1	0
x5	5	0	1	0	0	1
f(x0)	0	-2	-5	0	0	0

Алгоритм симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

min (- , - , 5 / 1) = 5

Следовательно, 3-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	min
x3	8	1	-2	1	0	0	-
x4	4	1	0	0	1	0	-
x5	5	0	1	0	0	1	5
f(x1)	0	-2	-5	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂. плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x₂. и столбец x₂..

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
8-(5 * -2)/1	1-(0 * -2)/1	-2-(1 * -2)/1	1-(0 * -2)/1	0-(0 * -2)/1	0-(1 * -2)/1
4-(5 * 0)/1	1-(0 * 0)/1	0-(1 * 0)/1	0-(0 * 0)/1	1-(0 * 0)/1	0-(1 * 0)/1
5 / 1	0 / 1	1 / 1	0 / 1	0 / 1	1 / 1
0-(5 * -5)/1	-2-(0 * -5)/1	-5-(1 * -5)/1	0-(0 * -5)/1	0-(0 * -5)/1	0-(1 * -5)/1

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	18	1	0	1	0	2
x4	4	1	0	0	1	0
x5	5	0	1	0	0	1
F(X1)	25	-2	0	0	0	5

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

min (18 / 1 , 4 / 1 , - ) = 4

Следовательно, 2-ая строка является ведущей.

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

Базис	B	x1	x2	x3	x4	x5	min
x2	18	1	0	1	0	2	18
x4	4	1	0	0	1	0	4
x5	5	0	1	0	0	1	-
f(x2)	25	-2	0	0	0	5	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 2 войдет переменная x₁

Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x₁ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₁ и столбец x₁.

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

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	14	0	0	1	-1	2
x4	4	1	0	0	1	0
x1	5	0	1	0	0	1
f(x2)	33	0	0	0	2	5

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x2	14	0	0	1	-1	2
x4	4	1	0	0	1	0
x1	5	0	1	0	0	1
f(x3)	33	0	0	0	2	5

Ответ:

Оптимальное значение функции

f_max(x)= 2*4 + 5*5 = 33

достигается в точке с координатами:

x₁ = 4,

x₂ = 5

x₃ = 14

x₄ = 0 x₅ = 0

e) Составить двойственную задачу к первоначальной задаче и найти ее решение.

Рассмотрим задачу в стандартной форме:

max f = 2x₁ + 5x₂

x₁ 0; x₂ 0 ;

Домножим уравнение (1 )на (-1)

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

min f^* = 8*y₁ + 4*y₂ + 5*y₃

Строим ограничения, транспонируя матрицу коэффициентов в ограничениях.

A = ;

A^T =

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

y₁ 0; y₂ 0; y₃ 0;

Решение двойственной задачи найдем с помощью теорем двойственности.

По первой теореме двойственности:

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

F_max = F^*_min

max f = min f^* = 33

Используем вторую теорему двойственности: так как в оптимальном решении исходной задачи x₁ ?0 и x₂ ?0, то на оптимальном решении двойственной задачи первое и второе ограничения двойственной задачи выполняется как равенство. Подставим x_опт в ограничения исходной задачи, получим, что первое ограничение выполняется как строгое неравенство, значит y₁ = 0. Получаем систему:

;

;

Решение двойственной задачи:

y_опт =(0; 2; 5), min f^* = 33



Задание 6

Дана задача линейного программирования,

max f = 3x₁ - 6x₂ + 2x₃

в которой x₁, x₂, x₃ 0

Задачи, которые необходимо решить в данном задании.

a. Записать задачу в канонической и стандартной формах;

b. Записать каноническую и стандартную задачи в матричном виде;

c. Решить задачу линейного программирования симплекс-методом;

d. Составить двойственную задачу к первоначальной задаче и найти ее решение.

Решение:

a) Записать задачу в канонической и стандартной формах;

Каноническая форма ЗЛП:

Для приведения задачи к канонической форме, где все ограничения имеют вид равенств, вводят дополнительные переменные

x_n+1, x_n+2,…,x_n+p ,

которые тоже считаются неотрицательными и записывают исходную задачу в виде

c₁x₁+c₂x₂+…+c_nx_n+0*x_n+1+0*x_n+2+…+0*x_n+p => min

Введем дополнительные переменные x₃, x₄, x₅. Переводя мах в min, запишем задачу в виде:

3*x₁ - 6*x₂ + 2*x₃ + 0*x₄ + 0*x₅ + 0*x₆ =>min

x_i =

Стандартная форма ЗЛП:

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

c₁x₁ + c₂x₂ +…+c_nx_n =>max

то, умножая её на (- 1), приведем её к виду:

(-c₁)x1 +(- c₂ )x₂ +…+(-c_n )x_n =>min

Таким образом, получаем:

min f = -3x₁ + 6x₂ - 2x₃

b) Записать каноническую и стандартную задачи в матричном виде;

Запись канонической задачи в матричном виде:

Найти минимальное значение функции

f(x) = CX, при условиях ,

где C = (3; -6; 2; 0; 0; 0) - вектор - строка коэффициентов при переменных.

X = (x₁, x₂, x₃, x_4, x₅,x₆ ), Х ? 0

A = (a_ij)_m*n - матрица размерности m*n, столбцами которой являются вектор-столбцы A_j

A =

B =

Запись стандартной задачи в матричном виде:

Найти максимальное значение функции

f(x) = CX,

при условиях

AX ? B ,

где

C = (-3; 6; -2), X = (x₁, x₂, x₃), Х?0,

A = ; B = ;

c) Решить ЗЛП симплекс-методом;

Определим максимальное значение целевой функции:

max f = 3x₁ - 6x₂ + 2x₃

при следующих условиях-ограничений:

x_i 0, i = 1,…,6

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

x_i 0, i = 1,…,6

max f = 3x₁ - 6x₂ + 2x₃

Введем искусственные переменные x: в 2-м равенстве вводим переменную x₇; в 3-м равенстве вводим переменную x₈;



Для постановки задачи на максимум целевая функция :

F(X) = 3x₁-6x₂+2x₃ - Mx₇ - Mx₈ > max

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

x₇ = 8-x₁-4x₂-8x₃+x₅

x₈ = 2-x₃+x₆

которые подставим в целевую функцию:

F(X) = 3x1-6x2 + 2x3 - M(8-x1-4x2-8x3+x5) - M(2-x3+x6) > max

Или

F(X) = (3+M)x1+(-6+4M)x2+(2+9M)x3+(-M)x5+(-M)x6+(-10M) > max



Матрица коэффициентов A = a_ij этой системы уравнений имеет вид:

A =

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

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

Решим систему уравнений относительно базисных переменных: x₄, x₇, x₈

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,6,0,0,8,2)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	6	3	3	2	1	0	0	0	0
x7	8	1	4	8	0	-1	0	1	0
x8	2	0	0	1	0	0	-1	0	1
f(x0)	10M	-3 - M	6 - 4M	-2-9M	0	M	M	0	0

Алгоритм симплекс-метода:

Итерация №0.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее:

min (6 / 2 , 8 / 8 , 2 / 1 ) = 1

Следовательно, 2-ая строка является ведущей.3

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

Пересчет симплекс-таблицы:

Формируем следующую часть симплексной таблицы.

Вместо переменной x₇ в план 1 войдет переменная x₃

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₇ плана 0 на разрешающий элемент РЭ=8. На месте разрешающего элемента в плане 1 получаем 1.

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

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

НЭ = СTЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (8), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Получаем новую симплекс-таблицу:



Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	4	2	2	0	1		0	-	0
x7	1			1	0	-	0		0
x8	1	-	-	0	0		-1		1
f(x0)	10M	-3 - M	6 - 4M	-2-9M	0	M	M	0	0

Итерация №1.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i5 и из них выберем наименьшее:

min (4 / ¹/₄ , - , 1 / ¹/₈ ) = 8

Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (¹/₈) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₈ в план 2 войдет переменная x₅.

Строка, соответствующая переменной x₅ в плане 2, получена в результате деления всех элементов строки x₈ плана 1 на разрешающий элемент РЭ=1/8

На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x₅ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены, строка x₅ и столбец x₅. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4	2	3	3	0	1		2	-	-2
x7	2			1	0	-	-1		1
x8	8	-	-	0	0		-8		8
f(x0)	4	-3	6	0	0	0	-2	M	2 + M

Итерация №2

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

min (2 / 3 , - , - ) = ²/₃

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x₄ в план 3 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 3, получена в результате деления всех элементов строки x₄ плана 2 на разрешающий элемент РЭ=3. На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x₁ плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x₁ и столбец x₁.

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

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x4		1	1	0
x7	2			1	0	-	-1		1
x8	8	0	-3	0			-7		7
f(x0)	6	0	9	0	1	0	0	M	M



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

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

x_опт: x₁ = ²/₃, x₂ = 0, x₃ = 2;

fmax(X) = 3*²/₃ -6*0 + 2*2 = 6;

d) Составить двойственную задачу к первоначальной задаче и найти ее решение.

max f = 3x₁ - 6x₂ + 2x₃

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

min f^* = 6*y₁ + 8*y₂ + 2*y₃

Строим ограничения, транспонируя матрицу коэффициентов в ограничениях:

A = ;

A^T = ;

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

y₁ 0; y₂ 0; y₃ 0;

Решение двойственной задачи найдем с помощью теорем двойственности.

По первой теореме двойственности:

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

F_max = F^*_min

fmax = f^*min = 6;

Используем вторую теорему двойственности: так как в оптимальном решении исходной задачи х₁ ?0 и х₂ ?0, то на оптимальном решении двойственной задачи первое и второе ограничения двойственной задачи выполняется как равенство. Подставим х_опт в ограничения исходной задачи, получим, что второе и третье ограничение выполняются как строгие неравенства, значит y₂=0, . Получаем систему:



;

;

Решение двойственной задачи: у_опт=(1; 0; 0 )

min f^* = 6*y₁ + 8*y₂ + 2*y₃ = 6 *1 + 8*0 + 2*0 = 6

min f^* = 6



Задание 7.

В задаче об оптимальном планировании перевозок A_i - пункты отправления; a_i - запасы в пунктах отправления; B_j - пункты назначения; b_j - заявки пунктов назначения.

	В1	В2	В3	В4	В5	ai
А1	3	3	4	4	5	350
А2	4	5	6	2	6	370
А3	4	4	5	5	6	390
А4	2	2	5	3	4	430
А5	4	2	5	6	6	400
bj	340	380	420	410	390

Задачи, которые необходимо решить в данном задании.

a. Определить начальный план транспортной задачи методом северо-западного угла;

b. Определить начальный план транспортной задачи методом минимального элемента;

c. Найти оптимальный план транспортной задачи методом потенциалов и стоимость перевозки по этому плану.

Решение.

Проверим необходимое и достаточное условие решения задачи.

Уa_i = 350 + 370 + 390 + 430 + 400= 1940

Уb_j = 340 + 380 + 420 + 410 + 390 = 1940

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



a. Определение начального плана транспортной задачи методом северо-западного угла;

	В1	В2	В3	В4	В5	ai
А1	3 (340)	3 (10)	4	4	5	350
А2	4	5 (370)	6	2	6	370
А3	4	4	5 (390)	5	6	390
А4	2	2	5 (30)	3 (400)	4	430
А5	4	2	5	6 (10)	6 (390)	400
bj	340	380	420	410	390

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

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n-1 = 9. Итак, опорный план является вырожденным.

Значение целевой функции для начального плана:

F (X) = 3*340 + 3*10 + 5*370 + 5*390 + 5*30 + 3*400 + 6*10 + 6*390 = 8600;

b. Определение начального плана транспортной задачи методом минимального элемента;

	В1	В2	В3	В4	В5	ai
А1	3	3	4 (310)	4 (40)	5	350
А2	4	5	6	2 (370)	6	370
А3	4	4	5	5	6 (390)	390
А4	2 (340)	2 (90)	5	5	5	430
А5	4	2 (290)	5 (110)	6	6	400
bj	340	380	420	410	390



Значение целевой функции для данного начального плана (стоимость перевозок по этому плану составляет):

F (X) = 2*340 + 2*90 + 2*290 + 4*310 + 5*110 +4*40 + 2*370 + 6* 390 = 6470;

Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу «северо-западного» угла.

c. Найти оптимальный план транспортной задачи методом потенциалов и стоимость перевозки по этому плану.

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

Теперь проверим его на оптимальность методом потенциалов, который заключается в последовательном улучшении опорных планов транспортной задачи на основе информации, полученной с помощью чисел, называемых потенциалы поставщиков u_i, и потребителей v_j (u_i, v_j. - двойственные переменные, то есть переменные задачи, двойственной к транспортной). Потенциалы находим из условия u_i + v_j c_ij, где cij - тарифы заполненных клеток, полагая, что u₁ = 0,

u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4; u₅ + v₃ = 5; u₅ + 4 = 5; u₅ = 1;

u₅ + v₂ = 2; 1 + v₂ = 2; v₂ = 1; u₄ + v₂ = 2; u₄ + 1 = 2; u₄ = 1;

u₄ + v₁ = 2; 1 + v₁ = 2; v₁ = 1; u₁ + v₄ = 4; 0 + v₄ = 4; v₄ = 4;

u₂ + v₄ = 2; u₂ + 4 = 2; u₂ = -2; u₃ + v₅ = 6; 1 + v₅ = 6; v₅ = 5;

	v1 = 1	v2 = 1	v3 = 4	v4 = 4	v5 = 5
u1 =0	3	3	4 (310)	4 (40)	5
u2 =-2	4	5	6	2 (370)	6
u3 = 1	4	4	5	5	6 (390)
u4 = 1	2 (340)	2 (90)	5	5	5
u5 = 1	4	2 (290)	5 (110)	6	6

Все оценки свободных клеток удовлетворяют условию

u_i + v_j c_ij,

Выбранный опорный план оптимальный.

Минимальные затраты на перевозку составят 6470.

Размещено на Allbest.ru