Лабораторные работы по Основам теории систем

Лабораторнаяработа № 2

ТелешовойЕлизаветы, гр.726,

Цель работы:Решениезадач линейногопрограммированиясимплекс-методом.Варианты разрешимостизадач линейногопрограммирования.

1 вариант.

1. Четыре студента:Иванов, Петров,Сидоров и Васильевпошли на концертгруппы «Чайф»,захватив пиво2 сортов: «Русич»и «Премьер».Определитьплан распитиянапитков дляполучениямаксимальногосуммарногоопьянения (в

).Исходные данныеданы в таблице:

Студент	Нормавыпитого		Запасы (в литрах)
	«Русич»	«Премьер»
Иванов	2	2	1.5
Петров	3,5	1	1,5
Сидоров	10	4	4,5
Васильев	–	1	0,7
Крепостьнапитка	16 %	10 %

2. Математическаямодель.

2.1 Управляемыепараметры

x₁[л]– количествовыпитого пива«Русич».

x₂[л]– количествовыпитого пива«Премьер».

– решение.

2.2 Ограничения

– количествопива «Русич»,выпитого Ивановым.

– количествопива «Премьер»,выпитого Ивановым.

–общее количествопива, выпитогоИвановым.

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

(л).

Аналогичностроим другиеограничения:

(л).

(л).

(л).

3. Постановказадачи.

Найти

^*,где достигаетсямаксимальноезначение функциицели:

4. Решение.

при:

Приведемзадачу к каноническомувиду:

Определимначальныйопорный план:

.

Это решениеявляется опорным,т.к. вектораусловий приположительныхкомпонентахрешения линейнонезависимы,также

,где ,но не все оценкиположительны( ,где )

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

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

Предположим,что

,тогда:

Запишем новыйопорный план:

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

=>

При увеличении

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

Из ограничения(2)имеем:

.

Подставляяв функцию цели:

получаем:

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

Начальнаясимплекс-таблица:

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X3	2	2	1	0	0	0	1,5
0	X4	3,5	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

;

Пересчитаемэлементы исходнойтаблицы поправилу четырехугольника:

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,428	1	-0,572	0	0	0,642
16	X1	1	0,286	0	0,286	0	0	0,428
0	X5	0	1,14	0	-2,86	1	0	0,214
0	X6	0	1	0	0	0	1	0,7
	F	0	-5,424	0	4,576	0	0	6,857

;

Пересчитаввсе оценки,видим, что

,значит критерийможно улучшить.Будем увеличивать .Пусть ,тогда:

откуда получаем:

;

Все оценкиопорного планадолжны бытьнеотрицательны,а значит должнывыполнятьсяусловия:

=>

Выведем избазиса

.Теперь базиснымипеременнымиявляются ,а свободными .Выразим функциюцели черезновые переменные:

,а из ограничений(2)и (3): .Тогда: ;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	0	1	3	-1,25	0	0,375
16	X1	1	0	0	1	-0,25	0	0,375
10	X2	0	1	0	-2,5	0,875	0	0,1875
0	X6	0	0	0	2,5	-0,875	1	0,5125
	F	0	0	0	-9	4,75	0	7,875

Пересчитаввсе оценки,видим, что

,значит критерийможно улучшить.Будем увеличивать .Пусть ,тогда:

откуда получаем:

;

Все оценкиопорного планадолжны бытьнеотрицательны,а значит должнывыполнятьсяусловия:

=>

Выведем избазиса

.Теперь базиснымипеременнымиявляются ,а свободными .Выразим функциюцели черезновые переменные:

,а из ограничений(1)и (2): .Тогда: ;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X4	0	0	0,333	1	-0,416	0	0,125
16	X1	1	0	-0,333	0	0,166	0	0,25
10	X2	0	1	1,833	0	-0,166	0	0,5
0	X6	0	0	-0,833	0	0,166	1	0,2
	F	0	0	3	0	1	0	9

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

Видим, что

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

2 вариант.

Отмечаяуспешно сданнуюсессию, вышеупомянутыестуденты взялистолько же пиваи в таких жепропорциях,за исключениемтого, что вместопива «Премьер»было купленопиво «Окское»,крепость которого6,4 % (дешевое иразбавленное).Определитьплан распитиянапитков дляполучениямаксимальногосуммарногоопьянения (в

).

Функция цели:

.

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

=>

Решаемсимплекс-методом:

		16	6,4	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	2	2	1	0	0	0	1,5
0	X4	3,5	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

,

		16	6,4	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,428	1	-0,571	0	0	0,642
16	X1	1	1,286	0	0,286	0	0	0,428
0	X5	0	1,142	0	-2,85	1	0	0,214
0	X6	0	1	0	0	0	1	0,7
	F	0	-1,82	0	4,571	0	0	6,857

;

		16	6,4	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	0	1	3	-1,25	0	0,375
16	X1	1	0	0	1	-0,25	0	0,375
6,4	X2	0	1	0	-2,5	0,875	0	0,1875
0	X6	0	0	0	2,5	-0,875	1	0,5125
	F	0	0	0	0	1,6	0	7,2

;

Видим, чтовсе оценкиположительны,значит оптимальноерешение достигнуто.Но одна из свободныхпеременных(

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

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X4	0	0	0,333	1	-0,416	0	0,125
16	X1	1	0	-0,333	0	0,166	0	0,25
10	X2	0	1	1,833	0	-0,166	0	0,5
0	X6	0	0	-0,833	0	0,166	1	0,2
	F	0	0	0	0	1	0	7,2

Если оптимальноерешение достигнутов 2-х точках, тооно достигаетсяи на отрезкемежду ними.Можно составитьуравнениеданного отрезкапо формуле:

;

;

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

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

3 вариант.

СтудентПетров, решивдогнать поколичествувыпитого студентаСидорова, выпил4 доли пива «Русич»вместо запланированных3,5. Решим задачус учетом изменившихсяданных.

Функцияцели:

.

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

=>

Решим задачусимплекс-методом.

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X3	2	2	1	0	0	0	1,5
0	X4	4	1	0	1	0	0	1,5
0	X5	10	4	0	0	1	0	4,5
0	X6	0	1	0	0	0	1	0,7
	F	-16	-10	0	0	0	0	0

, .

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	В
0	X3	0	1,5	1	-0,5	0	0	0,75
16	X1	1	0,25	0	0,25	0	0	0,375
0	X5	0	1,5	0	-2,5	1	0	0,75
0	X6	0	1	0	0	0	1	0,7
	F	0	-6	0	4	0	0	6

, .

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
10	X2	0	1	1,666	-0,333	0	0	0,5
16	X1	1	0	-0,166	0,333	0	0	0,25
0	X5	0	0	-1	-2	1	0	0
0	X6	0	0	-0,666	0,333	0	1	0,2
	F	0	0	4	2	0	0	9

,

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

В случаевырожденногорешения симплекс-таблицаможет зацикливаться.Существует2 способа предупреждениязацикливания:

а)

– изменениехода ограниченияна некоторыевеличины .Они должны бытьмалы, чтобыизменения былинесущественны.

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

4вариант.

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

Функция цели:

.

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

=>

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

,при этом .

Решаемвспомогательнуюзадачу симплекс-методом:

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	2	2	-1	0	0	0	1	0	0	0	1,5
1	X8	3.5	1	0	-1	0	0	0	1	0	0	1,5
1	X9	10	4	0	0	-1	0	0	0	1	0	4,5
1	X10	0	1	0	0	0	-1	0	0	0	1	0,7
	F	15,5	8	-1	-1	-1	-1	0	0	0	0	0

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	0	1,428	-1	0,571	0	0	1	-0,571	0	0	0,642
0	X1	1	0,285	0	-0,285	0	0	0	0,285	0	0	0,428
1	X9	0	1,142	0	2,857	-1	0	0	-2,85	1	0	0,214
1	X10	0	1	0	0	0	-1	0	0	0	1	0,7
	F	0	3.571	-1	3,428	-1	-1	0	-4,42	0	0	1,557

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X7	0	0	-1	-3	1,25	0	1	3	-1,25	0	0,375
0	X1	1	0	0	-1	0,25	0	0	1	-0,25	0	0,375
0	X2	0	1	0	2,5	-0,875	0	0	-2,5	0,875	0	0,187
1	X10	0	0	0	-2,5	0,875	-1	0	2,5	-0,875	1	0,512
	F	0	0	-1	-5,5	2,125	-1	0	4,5	-3,12	0	0,887

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X8	0	0	-0,333	-1	0,416	0	0,333	1	-0,416	0	0,125
0	X1	1	0	0,333	0	-0,166	0	-,333	0	0,166	0	0,25
0	X2	0	1	-0,833	0	0,166	0	0,833	0	-0,166	0	0,5
1	X10	0	0	0,833	0	-0,166	-1	-0,833	0	0,166	1	0,2
	F	0	0	0,5	-1	0,25	-1	-1,5	0	-1,25	0	0,325

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
1	X8	0	0	0	-1	0,35	-0,4	0	1	-0,35	0,4	0,205
0	X1	1	0	0	0	-0,1	0,4	0	0	0,1	-0,4	0,17
0	X2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X3	0	0	1	0	-0,2	-1,2	-1	0	0,2	1,2	0,24
	F	0	0	0	-1	0,35	-0,4	-1	0	-1,35	-0,6	0,205

		0	0	0	0	0	0	1	1	1	1
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	в
0	X5	0	0	0	-2,85	1	-1,14	0	2,857	-1	-1,142	0,585
0	X1	1	0	0	-0,285	0	0,285	0	0,285	0	-0,285	0,228
0	X2	0	1	0	0	0	-1	0	0	0	1	0,7
0	X3	0	0	1	-0,571	0	-1,42	-1	-1,571	0	1,428	0,357
	F	0	0	0	0	0	0	-1	-1	-1	-1	0

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

Решим исходнуюзадачу:

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X5	0	0	0	-2,85	1	-1,14	0,585
16	X1	1	0	0	-0,285	0	0,285	0,228
10	X2	0	1	0	0	0	-1	0,7
0	X3	0	0	1	-0,571	0	-1,42	0,357
	F	0	0	0	-4,576	0	-5,424	3,648

К

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

5вариант.

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

.

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

=>

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

;

		16	10	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	в
0	X5	0	0	0	-2,85	1	-1,14	0,585
16	X1	1	0	0	-0,285	0	0,285	0,228
10	X2	0	1	0	0	0	-1	0,7
0	X3	0	0	1	-0,571	0	-1,42	0,357
	F	0	0	0	-4,576	0	-5,424	3,648

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

;F = 3,648.

Д

елаемвывод: оптимальноерешение можетсуществоватьи при неограниченностиобласти.

Область неограничена,но существуетоптимальноерешение

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

11

Лабораторнаяработа № 3

ТелешовойЕлизаветы, гр.726,

Теориядвойственностив задачах линейногопрограммирования.

Задача:

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

Сырье	Содержаниев процентах
Компоненты	1	2	3	4	5
Свинец	10	10	40	60	70
Цинк	10	30	50	30	20
Олово	80	60	10	10	10
Стоимость,у. е.	4	4,5	5,8	6	7,5

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

Решениезадачи:

Пусть х_i – доля сырьяi-говида в единицеполученногосплава. Тогдафункция цели(себестоимостьединицы сплавав у.е.) запишетсяследующимобразом:

.

Системаограниченийбудет иметьвид:

(1).

Запишемсистему вканоническомвиде:

(2).

Решимпоставленнуюзадачу методомискусственного базиса. Дляэтого составимрасширеннуюзадачу:

(3).

Составимвспомогательнуюцелевую функцию:

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

;

;

Тогда:

.

Запишем начальнуюсимплекс-таблицу:

		4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
M	X9	1	1	1	1	1	0	0	0	1	0	1
0	X6	0,8	0,6	0,1	0,1	0,1	1	0	0	0	0	0,3
M	X10	0,1	0,3	0,5	0,3	0,2	0	-1	0	0	1	0,1
0	X8	0,1	0,1	0,4	0,6	0,7	0	0	1	0	0	0,4
	F	-4	-4,5	-5,8	-6	-7,5	0	0	0	0	0	0
	FM	1,1	1,3	1,5	1,3	1,2	0	-1	0	0	0	1,1

Оптимальнаясимплекс-таблицабудет иметьвид:

		4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28
	FM	0	0	0	0	0	0	0	0	-1	-1	0

Полученноерешение будетоптимальным,поскольку всеоценки неположительные.Запишем оптимальноерешение:

и оптимальноезначение целевойфункции: .

Экономическиполученноерешение интерпретируетсяследующимобразом: дляполученияединицы сплаваминимальнойсебестоимостинеобходимовзять 40% сырья№2 и 60% сырья №3.При этом сплавсодержит ровно30% олова, более20% (точнее, 42%) цинкаи менее 40% (28%) свинца.Минимальнаясебестоимостьединицы сплавасоставляет5,28 у.е.

Математическаямодель и экономическийсмысл двойственнойзадачи.

Задача, двойственнаяк исходной,строитсяследующимобразом:

1) Исходнаязадача – наминимум, следовательно,двойственнаязадача – намаксимум.

2) Матрицакоэффициентовсистемы ограниченийбудет представлятьсобой транспонированнуюматрицу соответствующихкоэффициентовисходной задачи.При этом всеограничениядолжны бытьодного типа,например "большеили равно".Поэтому преобразуемвторое и четвертоеограниченияк типу "большеили равно",умножив их на–1, затем транспонируемполученнуюматрицу:

=> .

3) Числопеременныхв двойственнойзадаче равночислу ограниченийв исходной,т.е. 4, и наоборот,число ограниченийв двойственнойзадаче равночислу переменныхв исходной,т.е. 5. Переменная

двойственнойзадачи соответствуетпервому ограничениюисходной задачи,переменная –второму, –третьему, а –четвёртому.

4) Коэффициентамипри переменных

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

,

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

.

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

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

Таким образом,математическаямодель двойственнойзадачи следующая:

.

(4).

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

, , и .Из ограниченийвидно, что величина имеет размерность[у.е./ед. сплава],величина –[у.е./ед. олова], –[у.е./ед. цинка], а –[у.е./ед. свинца].Указать экономическийсмысл переменной не представляетсявозможным всилу условиязадачи. Чтокасаетсяэкономическогосмысла переменных и ,то в системе(1) они соответствуетвторому и четвёртомуограничениям,отражающимотносительнуюизбыточностьресурсов "олово"и "свинец", т.е.они могут бытьрассмотреныкак условныйубыток длядержателя этогоресурса, илицену, выплачиваемуюего приобретателю.Таким образом,олово и свинецвыступают вданной задачев качествеантиблага, чтоэкономическитакже достаточноабсурдно.Экономическийсмысл переменной ,отражающейограниченностьресурса "цинк",виден явно: онапредставляетсобой двойственнуюоценку, илиусловную ценуэтого ресурса.

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

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

Целеваяфункция даннойдвойственнойзадачи экономическиинтерпретируетсякак максимальнаяприбыль фирмы-поставщикаресурсов.

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

1. Решениес помощью IBLP.

Введязадачу в программу,получаем следующееоптимальноерешение:

		1	-0,3	0,1	-0,4	0	0	0	0	0
Св	Б.П.	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	В
1	Y1	1	0	0,54	-0,46	0	-0,2	1,2	0	0	6,06
-0,3	Y2	0	1	0,4	-0,6	0	-2	2	0	0	2,6
0	Y5	0	0	-0,12	-0,12	1	-1,4	0,4	0	0	0,02
0	Y8	0	0	-0,2	-0,2	0	0	-1	1	0	0,2
0	Y9	0	0	-0,3	-0,3	0	0	-1	0	1	1,7
	T	0	0	0,32	0,12	0	0,4	0,6	0	0	5,28

.Значение целевойфункции приэтом равно5,28.

2. Решениепо второй теоремедвойственности.

Согласновторой теоремедвойственности,планы

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

(5)

(6)

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

(5).

(6)

Из системы(5) видно, что вовтором и третьемуравненияхв скобках получаетсяноль, поскольку

и положительны, .Из системы (6)получаем, что , поскольку втретьем и четвёртомуравненияхв скобках получаютсяположительныечисла.

Из первогои третьегоуравненийсистемы (5) имеем:

откуда

Таким образом,

.

3. Решениес помощьюсимплекс-таблицыисходной задачи.

Запишем ещераз оптимальнуюсимплекс-таблицуисходной задачи:

		4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28
	FM	0	0	0	0	0	0	0	0	-1	-1	0

Из теорииизвестно, чтосправедливыследующиеформулы:

(7); (8).

В системеограничений(2) исходной задачипеременной

соответствуетпервое ограничение,содержащеебазисную переменную ,переменной – второе, содержащеебазисную переменную ,переменной – третье, содержащеебазисную переменную и – четвёртоес переменной .Запишем условие(7) для оценок , , и приведеннойсимплекс-таблицы: ; ; ; ;

Теперь запишемусловие (8) длянашего случая:

,что покомпонентнозаписываетсякак: , , , ,откуда , , ,

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

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

4. Решениечерез матрицу,обратную кбазисной.

Оптимальноерешение двойственнойзадачи можнонайти по формуле

.Как видно изоптимальнойсимплекс-таблицы, .Тогда .Соответственно,

.

Получим:

,

Откуда

.

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

; .

Экономическаяинтерпретациятрех теоремдвойственности.

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

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

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

, , и соответственно).В случае положительностидвойственнойоценки (в нашемслучае и )справедливыравенства

,

т.е.первый и второй"ресурсы"используютсяполностью иявляются дефицитными.Следует оговориться,что первоеравенствовыполняетсявсегда, в противномслучае задачане имеет решения.Это логическипонятно, посколькусумма частейвсегда равнацелому. Чтокасается третьегои четвёртогоресурсов, тоони имеют нулевуюдвойственнуюоценку, т.е. этиресурсы неявляется дефицитным.Рассмотримтеперь условие(5). Поскольку

,то справедливынеравенства:

.

Экономическиэто значит, чтозатраты насырье №1, 4 и 5 превосходятвозможныезатраты в случаезакупки отдельныхресурсов, поэтомуэти виды сырьяиспользоватьсяне будут. С другойстороны,

, ,следовательно,

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

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

,т.е. в нашем случаекак изменяютсяминимальныеиздержки напроизводствоединицы сплавав зависимостиот изменения"ресурсов".Так, пусть, например,максимальнаядоля оловаувеличитсяна 0,1, т.е. до 40 %. Тогда,по третьейтеореме двойственности,минимальныеиздержки напроизводствоединицы сплавауменьшатсяна [у.е.].С другой стороны,изменениеминимальнойдоли цинка илисвинца не приведетк изменениюминимальныхиздержек, посколькуих двойственныеоценки равнынулю. Но двойственныеоценки позволяюто влиянии нацелевую функциюне любых измененийресурсов, алишь таких,какие не приводятк недопустимостиоптимальногорешения.

7

Лабораторнаяработа № 4

ТелешовойЕлизаветы, гр.726,

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

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

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

Сырье	Содержаниев процентах
Компоненты	1	2	3	4	5
Свинец	10	10	40	60	70
Цинк	10	30	50	30	20
Олово	80	60	10	10	10
Стоимость,у. Е.	4	4,5	5,8	6	7,5

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

Математическаямодель:

Пусть х_i – доля сырьяi-говида в единицеполученногосплава. Тогдафункция цели(себестоимостьединицы сплавав у.е.) запишетсяследующимобразом:

.

Системаограниченийбудет иметьвид:

Запишемсистему вканоническомвиде:

Оптимальнаясимплекс-таблица:

		4	4,5	5,8	6	7,5	0	0	0	M	M
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28

Оптимальноерешение:

и оптимальноезначение целевойфункции: .

Экономическиполученноерешение интерпретируетсяследующимобразом: дляполученияединицы сплаваминимальнойсебестоимостинеобходимовзять 40% сырья№2 и 60% сырья №3.При этом сплавсодержит ровно30% олова, более20% (точнее, 42%) цинкаи менее 40% (28%) свинца.Минимальнаясебестоимостьединицы сплавасоставляет5,28 у.е. Оптимальныедвойственныеоценки

.

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

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

при расчётеконкретныхзначений. (Этоделается дляболее нагляднойэкономическойинтерпретацииинтерваловустойчивости.)

Пусть свободныечлены изменилисьна

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

.

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

=>

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

.

Теперь найдёминтервалыустойчивости(интервалустойчивостидвойственныхоценок к изменениюправой частиограниченияили i-горесурса – такоемножество i–горесурса, прикотором двойственныеоценки не меняются):

1)

, :

=> ,

2)

, :

=> ,

3)

, :

=> , .

4)

, :

=> , .

Полученныерезультатыэкономическиозначают, чтосвободный членв первом ограниченииможет менятьсяот 0,5 до 1,26,но экономическогосмысла это никакого не имеет,т.к. сумма составляющихдолей сплававсегда 100%. Содержаниеолова в новомсплаве варьируетсяот 10%до 60%,цинка – от нуля(

не имеет экономическойинтерпретации)до 42%и свинца – от28%до 100% (аналогичнослучаю с цинком не может бытьобъясненаэкономически).Возможны такжеразличныекомбинацииизменений,которые описываетобласть устойчивости(интервалыустойчивостиявляютсясвоеобразнымичастными случаямиобласти устойчивости).При данныхизмененияхресурсов двойственныеоценки не изменятся,а значити номерабазисных переменныхтакже не изменятся.

И

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

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

Изменимусловие задачиследующимобразом:

а) содержаниеолова в новомсплаве не должнопревосходить15%;

Интервалустойчивостидля олова – это

.15% или 0,15 входятв этот интервал,следовательнодвойственныеоценки не изменятсяи оптимальноерешение будет(при ).

.

По третьейтеореме двойственностинайдём значениекритерия приэтом решении:

=> .

б) содержаниецинка должнобыть не менее45%;

Интервалустойчивостидля цинка -

.Т.к. содержаниецинка в сплаведолжно бытьне более 42%, а т.к.0,45 не входит винтервал устойчивостидвойственныхоценок, тодвойственныеоценки и номерабазисных переменныхсменятся ( ).

.

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

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	-0,03
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28

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

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

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	2	1	0	1	1,5	0	5	0	2,5	-5	0,25
0	X8	0,3	0	0	0,5	0,75	0	1,5	1	0,35	-1,5	0,075
5,8	X3	-1	0	1	0	-0,5	0	-5	0	-1,5	5	0,75
0	X6	-0,3	0	0	-0,5	-0,75	1	-2,5	0	-1,35	2,5	0,075
	F	-0,8	0	0	-1,5	-3,65	0	-6,5	0	2,55	6,5	5,475

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

.Оптимальноезначение критерия .Это означает,что для производстваединицы сплаванеобходимовзять 25% второгосырья и 75% третьегосырья. При этомдоля цинка вновом сплавебудет ровно45%, олова 22,5% и свинца32,5%. Минимальнаястоимость тоннысплава будет5,475 у.е.

в) в новомсплаве должнобыть менее 40%олова и более30% цинка;

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

; ):

.

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

=>

г) менее 60%олова и более40% цинка;

В данномслучае изменениясоставляют:увеличениесодержанияолова на 30% и цинкана 30%, т.е

и .Поэтому

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

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	-0,1
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	5,28

Оптимальнаясимплекс-таблица:

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	2	1	0	1	1,5	0	5	0	2,5	-5	0.5
0	X8	0,3	0	0	0,5	0,75	0	1,5	1	0,35	-1,5	0,15
5,8	X3	-1	0	1	0	-0,5	0	-5	0	-1,5	5	0,5
0	X6	-0,3	0	0	-0,5	-0.75	1	-2.5	0	-1.35	2,5	0,25
	F	-0,8	0	0	-1,5	-3,65	0	-6,5	0	2,55	6,5	5,15

Получимследующеерешение:

, .Таким образом,для изготовлениянового сплаванеобходимовзять 50%сырья №2и 50% сырья№3.

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

Предположим,что появиласьвозможностьпокупать сырьёу других поставщиковпо более низкойцене: цинк по2 у.е., а за оловои свинец, т.к.согласноэкономическомусмыслу задачиони являются"антиблагами",мы получаембольшую доплатуот их поставщика:1,5 у.е. и 0,5 у.е. соответственно.Руководительпредприятиявыделил назакупку ресурсов3 у.е.

Решение:

По ранееполученнымрезультатаммы знаем, чтопредприятиетратит минимумсредств (5,28 у.е.)когда в полученномсплаве ровно30% олова, 42% цинкаи 28% свинца (будемсчитать дляудобства, чтодля производства10 тонн сплаванеобходимо3 тонны олова,4,2 тонны цинкаи 2,8 тонн свинца).Т.к. олово и свинецмы получаемс доплатой, товозьмём их вполном объёме,необходимомдля производствасплава. От "покупки"олова мы получим

,а от свинца – ,т.е. всего 5,9 у.е.(в связи с ихдоходностью,а не убыточностьювременно исключимих из рассмотрения).

Будем вестианализ закупокцинка. На первойитерации мыне закупаемцинк, т.к. в этомслучае он быприносил большеубытка (двойственнаяоценка равнанулю по сравнениюс предлагаемойценой в 2 у.е.).Решив новуюзадачу безпроизводстваолова и свинца,мы безусловновыйдем за границыобласти устойчивостидвойственныхоценок. Крометого, сменитсярешение: двойственнаяоценка цинкаувеличитсядо 3 и новое значениецелевой функциипонизится до4 у.е. Вычтем изэтих затратна производствосплава доходот полученияолова и цинка:

.Это значит, чтона производствосплава мы нетолько не тратимсредств, но иполучаем прибыль1,9 у.е.

С увеличениемдвойственнойоценки цинкастановитсявыгодно покупатьего. Но мы располагаемсуммой денегтолько 3 у.е. иможем закупитьна них 1,5 тоннвместо 2 необходимых.Теперь намнужно производитьтолько 0,5 тонныцинка. На второйитерации мыполучаем такоеже решение:критерий равен4 у.е. и двойственнаяоценка цинка,которого мыпроизводим3 тонны, равна4.

Таким образом,мы получилиоптимальноерешение расходованиявыделенных3 у.е.: "закупать"с доплатой 4тонны оловаи 5 тонн свинцаи покупать поцене 2 у.е. 1,5 тонныцинка. При такомплане предприятиеполучит прибыльот производствасплава в размере1,9 у.е.

2.Анализ чувствительностиоптимальногорешения задачик изменениюкоэффициентовцелевой функции.

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

1. Пусть, сначала,меняется ценавторого и третьегоресурсов (базисныепеременные).

а)

.

Тогда оптимальнаясимплекс-таблицабудет иметьвид:

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F		0	0				0	0		0

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

=> ,

Это значит,что цена первогоресурса можетменяться отнуля (бесплатный,недефицитныйресурс) до 4,514у.е. (отрицательныйкоэффициентв целевой функциив данном случаене имеет экономическогосмысла, т.к.свидетельствуето полученииресурса с доплатой.В этом случаересурс выступаетв роли антиблага).Критерий изменитсяна

.

б)

		4	4,5	5,8	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F		0	0				0	0		0

=> ,

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

.

2. Рассмотримслучай со свободнойпеременной.

а)

,тогда

Условиеоптимальностиоценки:

=> => .

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

, .

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

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

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

, или , .

, или ,

Оптимальныерешения при конкретныхизмененияхкоэффициентов.

а)стоимостьвторого сырьяувеличиласьдо 4,5 у.е

Интервалустойчивостикоэффициентацелевой функции

.Цена 4,5 у.е. входит в этотинтервал, значитоптимальноерешение неизменится, акритерий станет у.е.

б) стоимостьтретьего сырьяуменьшиласьдо 3 у.е

Интервалустойчивостидля

.3 у.е. ( )не принадлежитинтервалу,значит какие-тооценки будутне оптимальными:

– при

: ;

– при

: ;

– при

: ;

– при

: ;

– при

: ;

.

Скорректируемсимплекс-таблицу:

		4	4,5	3	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
3	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	1,1	0	0	-3	-4,5	3	0	0	-9,42	0	3,6

Через двеитерации получаемоптимальнуюсимплекс-таблицу:

		4	4,5	3	6	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4	X1	1	1	0	-0,666	-1	0	0	-3,33	1,333	0	0
0	X6	0	-0,2	0	0,466	0,7	1	0	2,333	-1,03	0	0,2
3	X3	0	0	1	1,666	2	0	0	3,333	-0,333	0	0,1
0	X7	0	-0,2	0	0,466	0,7	0	1	1,333	-0,033	-1	0,4
	F	0	-0,5	0	-3,66	-5,5	0	0	-3,33	4,333	0	3

Получимоптимальноерешение

.Стоимостьсплава понизиласьдо 3 у.е. за единицу.

в) издержкина первое сырьёвозросли до6 у.е

Стоимостьпервого сырьяможет изменятьсяв пределах

.6 у.е. входят винтервал, значитоптимальноерешение неизменится, атакже останетсяпрежнем критерий( , ).

г) издержкина четвёртыйресурс упалидо 4 у.е.

При падениииздержек до4 у.е. за тоннуоптимальноерешение должноизмениться,т.к. нижняя границаинтервалаустойчивости– 5,8 у.е. Оценка

.

		4	4,5	5,8	4	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	1,8	-1,7	-2,6	0	0	-6,06	0	5,28

Оптимальнаясимплекс-таблица:

		4	4,5	5,8	4	7,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0,4
4	X4	0,6	0	0	1	1,5	3	0	5	-2,3	0	0,6
5,8	X3	-1	0	1	0	-0,5	-5	0	-5	3,5	0	0
0	X7	0	0	0	0	0	-1	1	-1	1	-1	0,2
	F	-1,1	0	0	0	-4,4	-8	0	-9	10,2	0	4,2

С помощьюсимплекс-методаполучаем оптимальноерешение

и оптимальноезначение критерия у.е.

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

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

Возьмем,например, какизменяющийсякоэффициент

.Его изменениевлечёт за собойизменениеоценки толькосвободнойпеременной :

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

Возьмём такжедля наглядностиизменение ещёодного коэффициента,т.к. полученныйвыше результатозначает, чтосодержаниесплава (т.е всехкомпонентов)в первом сырьеможет менятьсяот 0% до 100% (формальноот 0% до 100,3%).

, , , ,т.е. содержаниесвинца в первомсырье варьируетсяв пределах от0% до 100% ( и экономическогосмысла не имеют).

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

а) 100,2%

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

б) 110%

, (не входит винтервалустойчивости).

–оценка неоптимальная.

Симплекс-методомполучим оптимальноерешение:

, .

4. Введение новойпеременной.

Предположим,что появиласьвозможностьиспользоватьновый вид сырья,в котором содержится40% олова, 60% цинкаи 30% свинца, икоторый обладаетстоимостью3,5 у.е. за единицу.Определим новыйплан производства.

Пусть

–доля шестого(нового) сырьяв сплаве. Тогда:

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

.

Доход на тоннунового сырьябудет равен

,а затраты – 3,5у.е. (Новое ограничениев двойственнойзадаче )Тонна сырьяприносит большедохода, чемиздержек на1 у.е., поэтомубудем увеличиватьиспользованиеэтого сырья.

Запишем новуюсимплекс-таблицус учётом новойпеременной:

		4	4,5	5,8	6	7,5	3,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6’	X6	X7	X8	X9	X10	В
4,5	X2	1,4	1	0	0	0	0,6’	2	0	0	-0,2	0	0,4
0	X8	0,12	0	0	0,2	0,3	1	0,6	0	1	-0,46	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	-2	0	0	1,2	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,1	-0,4	1	0	0,54	-1	0,32
	F	-0,02	0	0	-0,2	-1,7	1	-2,6	0	0	-6,06	0	5,28

Оптимальнаясимплекс-таблица:

		4	4,5	5,8	6	7,5	3,5	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6’	X6	X7	X8	X9	X10	В
3,5	X6’	2,333	1,666	0	0	0	1	3,333	0	0	-0,333	0	0,666
0	X8	-0,066	-0,133	0	0,2	0,3	0	0,333	0	1	-0,433	0	0,066
5,8	X3	-1,33	-0,666	1	1	1	0	-3,33	0	0	1,333	0	0,333
0	X7	0,633	0,366	0	0,2	0,3	0	0,333	1	0	0,466	-1	0,466
	F	-3,56	-2,53	0	-0,2	-1,7	0	-7,66	0	0	-6,566	0	4,266

Оптимальноерешение будет

, .Это означает,что для производстванового сплавабудет использоваться33,3% третьего сырьяи 66,6% нового шестогосырья. Минимальнаястоимостьсплава будет4,266 у.е. Видим, чтоиспользованиенового видасырья действительновыгодно, т.к.издержки напроизводствосплава снизилисьс 5,28 у.е. за единицудо 4,266 у.е.

5. Введение новогоограничения

Пусть дляпроизводствасплава нужноиспользоватьещё один компонент– медь, содержащуюсяв сырье в количествах40%, 10%, 20%, 20% и 30% соответственно.Содержаниееё в новом сплавене должно бытьменьше 20%.

Системаограниченийбудет иметьвид:

Оптимальноерешение первоначальнойзадачи:

.Проверим,удовлетворяетли оно новомуограничению:

.

Ограничениене выполняется,поэтому длярешения задачиприведём новоеограничениек каноническойформе:

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

После несложныхвычисленийполучим:

.

Новая симплекстаблица будетвыглядетьследующимобразом:

		4	4,5	5,8	6	7,5	0	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	В
4,5	X2	1,4	1	0	0	0	2	0	0	-0,2	0	0	0,4
0	X8	0,12	0	0	0,2	0,3	0,6	0	1	-0,46	0	0	0,12
5,8	X3	-0,4	0	1	1	1	-2	0	0	1,2	0	0	0,6
0	X7	0,12	0	0	0,2	0,3	-0,4	1	0	0,54	-1	0	0,32
0	X11	0,34	0	0	0	0,1	0,2	0	0	-0,22	0	1	0,04
	F	-0,02	0	0	-0,2	-1,7	-2,6	0	0	-6,06	0	0	5,28

Оптимальноерешение получимс помощьюдвойственногосимплекс-метода.

		4	4,5	5,8	6	7,5	0	0	0	0	0	0
Св	Б.П.	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	В
4,5	X2	0	1	0	0	-0,411	1,176	0	0	4,117	0,705	0	0,235
0	X8	0	0	0	0,2	0,264	0,529	0	1	0,353	-0,382	0	0,106
5,8	X3	0	0	1	1	1,117	-1,76	0	0	-1,17	0,941	0	0,647
0	X7	0	0	0	0,2	0,264	-0,47	1	0	0,353	0,617	-1	0,305
4	X1	1	0	0	0	0,294	0,588	0	0	-2,94	-0,647	0	0,117
	F	0	0	0	-0,2	-1,69	-2,58	0	0	-0,058	-6,047	0	5,282

Оптимальноерешение:

.Это значит, чтодля производствасплава с учётомпримеси мединеобходимовзять 11,7% первого сырья,23,5% второго сырьяи 64,7% третьегосырья. Минимальнаястоимостьединицы такогосплава будет5,282 у.е.

13

Лабораторнаяработа № 5

ТелешовойЕлизаветы, гр.726,

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

1. Постановказадачи.

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

В амбаре было4 мышиных норы:в первой проживало15 мышей, во второй– 20, в третьей– 10 мышей, а вчетвертой –25 мышей, а также5 источниковпищи, от которыхи кормиласьвся эта оравамышей: у окорока– 5 мышей, у мешкакрупы – 18 мышей,у мешка муки– 17 мышей, у мешкакартошки – 22мыши и у стопкистарых газети журналовэротическогосодержания– 8 мышей.

И тут мышивспомнили, чтокогда-то в стопкежурналов лежалакнижка поматематическомупрограммированию.Конечно мышидавным-давноуспели ее сгрызть,но кое-что изнее они, покагрызли, прочитатьуспели, в частности,как решатьтранспортныезадачи.

Считая что

–количествомышей из -тойноры, питающихсяу -тогоисточника пищи, –количествомышей, проживающихв -тойноре, –количествомышей, питающихсяу -тогоисточника пищи,мыши определили,что для того,чтобы были всеони были сыты,необходимовыполнение2 условий:

1)

;

2)

;

ну и конечно

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

; ;

Ну, и длянаглядностинарисовалиее в виде таблицы:

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5	18	17	22	8
нора1	15
нора2	20
нора3	10
нора4	25

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

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

.

Безусловно,цель мышей –добраться доеды с минимальнымипотерями подороге, то есть:

.

Таким образом:

2. Двойственаязадача.

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

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

(1).

Система (1) ибудет служитьв дальнейшемкритериемоптимальностиплана.

Запишемподробно двойственнуюзадачу на основеэтого ограничения:

; ; ; ;

Критериемдвойственнойзадачи будетмаксимизациявыгодности:

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

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

(2).

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

Посколькухотят есть всемыши во всехнорах, то модельзакрытая, т.е.

.

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

1) Выбираемкоммуникацию,которую можнобольше всегозагрузить.

2) Максимальноее загружаемв соответствиис (2).

3) Корректируемобъемы производстваи потребленияна величинувыбраннойперевозки,вычисляя остаткипроизводстваи потребления:

; ;

4) Вычеркиваемв транспортнойтаблице строкуили столбецс нулевым объемомпроизводстваили потребления:

если

– вычеркиваем -туюстроку;

если

– вычеркиваем -тыйстолбец;

5) Повторяемэтот процессс пункта 1 по4, пока не будутперечеркнутывсе строки илистолбцы

В нашем случаеэто выглядитследующимобразом:

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5 2 0	18 0	17 2 0	22 0	8 0
нора1	15 0			15
нора2	20 2 0		18	2
нора3	10 2 0	2				8
нора4	25 3 0	3			22

Римскимицифрами пронумерованпорядок итераций.

I.

; ; ; – 4 столбецисключен.

II.

; ; ; – 2 столбецисключен.

III.

; ; ; – 1 строкаисключена.

IV.

; ; ; – 5 столбецисключен.

V.

; ; ; – 4 строкаисключена.

VI.

; ; ; – 3 строкаи 1 столбецисключены.

VII.

; ; ; – 2 строкаи 3столбец исключены.

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

;

.

По этомуопорному планукоту достанетсяаж 13 мышей (0,18 частьмыши отдельновряд ли выживет).“Жирноему будет”-,подумалимыши и сталисоставлятьдругой опорныйпланметодомсеверо-западногоугла.

4. Метод северо-западногоугла.

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

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

,I – множествономеров пунктовпроизводства;

,J – множествономеров пунктовпотребления;

Последовательнопо итерациямметода получаем:

I.

; ; ; – 1 столбецисключен.

II.

; ; ; – 1 строкаисключена.

III.

; ; ; – 2 столбецисключен.

IV.

; ; ; – 2 строкаисключена.

V.

; ; ; – 3 столбецисключен.

VI.

; ; ; – 3 строкаисключена.

VII.

; ; ; – 4 столбецисключен.

VIII.

; ; ; – 4 строкаи 5 столбецисключены.

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5 0	18 8 0	17 5 0	22 17 0	8 0
нора1	15 10 0	5	10
нора2	20 12 0		8	12
нора3	10 5 0			5	5
нора4	25 8 0				17	8

Получилиследующийопорный план:

.

.

Те же самые13 мышей, и дажехуже предыдущегоопорного плана(если учитыватьсотые). Пришлосьмышам использоватьметод минимальныхзатрат.

5. Методминимальныхзатрат.

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

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5 0	18 0	17 0	22 20 18 15 0	8 0
нора1	15 0				15
нора2	20 3 0			17	3
нора3	10 2 0				2	8
нора4	25 7 20	5	18		2

I.

; ; ; – 2 столбецисключен.

II.

; ; ; – 1 столбецисключен.

III.

; ; ; – 4 строкаисключена.

IV.

; ; ; – 5 столбецисключен.

V.

; ; ; – 3 строкаисключена.

VI.

; ; ; – 3 столбецисключен.

VII.

; ; ; – 2 строкаисключена.

VIII.

; ; ; – 1 строкаи 4 столбецисключены.

Опорный план:

Целеваяфункция:

Этот опорныйплан понравилсямышам значительнобольше, но всеравно потеридостаточновелики (7 мышей).Теперь требовалосьрешить этузадачу и найтиоптимальныйплан. И сделатьони это собралисьсамым точнымметодом – методомпотенциалов.

6. Решение задачиметодом потенциалов.

Если пландействительнооптимален, тосистема (1) будетвыполняться,т.е.:

1) для каждойзанятой клеткитранспортнойтаблицы суммапотенциаловдолжна бытьравна

для этой клетки;

2) для каждойнезанятойклетки суммапотенциаловне больше (меньшеили равно)

.

Построимдля каждойсвободнойпеременнойплана числа

и они должныбыть положительны.Так как числопотенциаловравно 9, а системасостоит из 8уравнений, тодля нахождениякакого-либорешения этойсистемы необходимопервому изпотенциаловпридать произвольноезначение (например: ).Далее последовательнонаходим значениявсех потенциалов.Распишем подробноэту процедуру.

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5	18	17	22	8
нора1	15				15
нора2	20			17	3
нора3	10				2	8
нора4	25	5	18		2

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

:

Видно, что

и меньшенуля, значитсуществующийопорный планможно улучшить.Поскольку ,нужно ввестив базис вектор,соответствующийклетке (2; 1), длячего загрузитьее некоторымколичествомединиц груза(мышей). Но, таккак мы, увеличиваязагрузку (2; 1),нарушаем балансстрок и столбцовраспределительнойтаблицы, тоследует изменитьобъемы поставокв ряде другихзанятых клеток.А чтобы числобазисных переменныхосталось прежним,необходимовывести избазиса однупеременную.Выводитсяобычно та переменная,у которой загрузкав цикле минимальна.

Строим цикл:

(2; 1) – начальнаяточка цикла;

Что характерно,для этой точки(впрочем каки для других)мы можем построитьтолько одинцикл. Каждойклетке циклаприписываемопределенныйзнак:

(2; 1) – “+”, (4;1) – “-”, (4; 4) – “+” (2; 4) –“-”.

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5	18	17	22	8
нора1	15				15
нора2	20			17	3
нора3	10				2	8
нора4	25	5	18		2

В клеткахс “+” – увеличиваемзагрузку, а вклетках с “-”– уменьшаем.Величина, накоторую увеличиваемили уменьшаемвсегда однаи она определяетсяиз условия:

,где –содержимоеклеток с “-”.

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

,а значит избазиса будетвыведена (2;4), где в процессереализациицикла загрузкауменьшитсядо 0.

Перейдемк новому опорномуплану

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5	18	17	22	8
нора1	15				15
нора2	20	3		17
нора3	10				2	8
нора4	25	2	18		5

Определяем

Все

больше 0, следовательноплан оптимальный.

.

Целеваяфункция приэтом плане:

М-да, незначительноеулучшение длямышей. Целых6 мышей и ещеодин мышиныйхвостик – таковаежедневнаядань коту Василию.Но делать нечего,и стали мышидействоватьпо этому плану.

7. Открытая модель.

И все былобы хорошо, нов 3 норе появилсядополнительныйприплод – 10 мышей,следовательнов ней сталопроживать 20мышей, а количествомышей, питающихсяу источниковпищи, осталосьтем же. Получиласьтак называемаяоткрытая модель,где:

(3)

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

с объемомпотребления:

;

идополнительныепеременные

приводящиеограничение-неравенство(3) к виду равенстви пониманиекак фиктивныеперевозки изпунктов производствав фиктивныйпункт потребления.Новая математическаямодель:

; ;

При этом во2 и 3 норах всемыши должныбыть накормлены(во второй –самые умныемыши, а в третьей– большой приплод),поэтому второеи третье ограничения– уравнения.В первое и четвертоеограничениядобавим новыепеременныеR₁и R₄для уравновешиваниясистемы. А таккак этих источниковпищи на самомделе нет, то изатраты (потерипо дороге) наних нулевые.

В транспортнойтаблице в последнемстолбце введемеще 2 переменныев (2; 5) и (3; 5) – R₂и R₃, чтобыстолбец былполностьюзаполнен, а таккак перевозкив этих коммуникацияхне должны быть,то наложим наних очень большиештрафы М и включимвсе новые переменныев целевую функцию:

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

).Напишем новуютранспортнуютаблицу и найдемначальныйопорный планметодом минимальныхзатрат.

Пища Норы		окорок	мешок крупы	мешок муки	мешок картошки	журналы	R
		5 0	18 15 0	17 0	22 10 0	8 0	10 5 0
нора 1	15 5				10		5
нора 2	20 3 0		3	17
нора 3	2012 0				12	8
нора 4	25 10 5 0	5	15				5

Определяем

.

меньше 0, поэтомусуществующийопорный планможно улучшить.Поскольку –наибольший,то мы будемвводить в базисвектор, соответствующийклетке (4; 4). Строимцикл ипереходим кновому опорномуплану.

Пища Норы		окорок	мешок крупы	мешок муки	мешок картошки	журналы	R
		5	18	17	22	8	10
нора 1	15				5		10
нора 2	20		3	17
нора 3	20				12	8
нора 4	25	5	15		5

Определяем

меньше 0, поэтомусуществующийопорный планможно такжеулучшить. Теперьмы будем вводитьв базис вектор,соответствующийклетке (2; 1). Строимцикл ипереходим кновому опорномуплану.

Пища Норы		окорок	мешок крупы	мешок муки	мешок картошки	журналы	R
		5	18	17	22	8	10
нора 1	15				5		10
нора 2	20	3		17
нора 3	20				12	8
нора 4	25	2	18		5

Определяем

Все

больше 0, следовательноплан оптимальный.

.

Целеваяфункция приэтом плане:

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

8. Запрещенныеперевозки.

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

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

Пища Норы		окорок	мешоккрупы	мешокмуки	мешоккартошки	журналы
		5	18	17	22	8
Нора1	15				15
Нора2	20	2	18
Нора3	10				2	8
Нора4	25	3		17	5

Видно, чтоэтот план ужеявляется оптимальным.

Целеваяфункция:

.

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

10

Лабораторнаяработа № 6

ТелешовойЕлизаветы, гр.726,

Решениезадачи о ранцеметодом ветвейи границ.

1. Постановказадачи.

1929 год. В СШАвеликая депрессия,введен сухойзакон. Странапросто задыхаетсябез спиртного.В этот сложныймомент группаинициативныхграждан подруководствомАль Капонерешает помочьродной стране.Ими планируетсяпоставка алкогольнойпродукции изЛиверпуля вШтаты. Благодарныесогражданеиз 5 крупныхгородов СШАготовы платитьбольшие деньгиза тонну спиртного:2000 долл. в Бостоне,3000 в Детройте,2500 в Вашингтоне,3200 в Нью-Йоркеи 1800 долл в Чикаго.Все 5 городовнаходятся наразном расстоянииот порта, кудаприбывает груз:Бостон – 250 миль,Детройт – 300 миль,Вашингтон –500 миль, Нью-Йорк–100 миль и Чикаго– 600 миль. Требуетсявыбрать города,в которых можнополучить максимальнуюприбыль отпродажи спиртного.При этом суммарноерасстояниеот этих портовдо порта с грузомне должно превышать1000 миль.

2. Решение задачи.

Данная задачаявляется задачейо ранце вида:

,(1)

где критериемявляется функция

,(2)

которая можетбыть устремленаи к максимуму,и к минимуму.

Для началасоставим следующуюматематическуюмодель:

Пусть

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

;

Целевойфункцией иликритерием будетявляться максимальнаяблагодарностьсограждан:

.

Далееотбираем портыпо приоритетности,т.е. в порядкеубывания отношения

:

(3); (2); (4); (1); (5).

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

,посколькуотношение наибольшее,и следовательнопродажа спиртногов Нью-Йоркедаст наибольшуюприбыль принаименьшихзатратах, которыезависят отрасстояния.Вычитая изсуммарногорасстояния расстояниедо порта мыполучим расстояние,которое разделяетсямежду остальнымигородами, т.е.:

, ;

Аналогичнорассуждая,далее получаем:

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому

будет дробным: ,=> .

Таким образом,начальныйопорный план:

.

Значениецелевой функции:

.

Но

обязательноцелое. Поэтомучтобы определить,чему все жеравен :0 или 1 вычислимследующиезначения:

;–целая частькритерия присуществующемопорном плане.

;–значениекритерия прицелочисленномопорном плане,т.е. .

МножествоD, которомупринадлежит

имеет , .Разделим егона 2 подмножества,такие что:

;

- здесь .

-здесь .

1) Анализмножества D₁.

Поскольку

целевая функцияи ограничениябудут иметьвид:

Строим новыйопорный план:

, ;

, ;

, ;

Т.к.

,поэтому будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

,при .

2) Анализмножества D₂.

Поскольку

целевая функцияи ограничениябудут иметьвид:

=> .

Строим новыйопорный план:

, ;

, ;

Т.к.

,поэтому будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

,при .

3) Отсевнеперспективногоподмножества.

.

Так как

и больше Rec,то оба подмножестваможно считатьперспективными,но поскольку ,то далее мыбудем исследоватьподмножествоD₂.Разделим егона 2 подмножества,такие что:

;

- здесь .

-здесь .

4) Анализмножества D₃.

Поскольку

, целевая функцияи ограничениябудут иметьвид:

.

Строим новыйопорный план:

, ;

, ;

Т.к.

,поэтому будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

,при .

5) Анализмножества D₄.

Поскольку

, целевая функцияи ограничениябудут иметьвид:

=> .

Строим новыйопорный план:

, ;

Т.к.

,поэтому будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

,при .

6) Отсевнеперспективногоподмножества.

.

Так как

и больше Rec,то оба подмножестваможно считатьперспективными,но поскольку ,то далее мыбудем исследоватьподмножествоD₃.Разделим егона 2 подмножества,такие что:

;

- здесь .

-здесь .

7) Анализмножества D₅.

Поскольку

, , целевая функцияи ограничениябудут иметьвид:

.

Строим новыйопорный план,очевидно:

.При , ограничениевыполняетсявсегда.

;

,при .

8) Анализмножества D₆.

Поскольку

, , целевая функцияи ограничениябудут иметьвид:

.

Ограничениенесовместное,поскольку дажепри

оно не выполняется.Следовательномножество D₆не существует.

Таким образом,оптимальнымпланом даннойзадачи будет:

,то есть алкогольвыгоднее всегопоставлятьв 3 города: Детройт,Вашингтон иНью-Йорк. Приэтом прибыльсоставит 8700 долл.

3. Постановказадачи о многомерномранце.

Всвязи с тем,что спиртноестало хорошораскупаться,Аль Капонерешил увеличитьпоставки. Ночтобы мирноспящее ФБР недай бог непроснулось,было решеноосуществлятьпоставки черезтри разныхпорта на восточномпобережье. Ценына спиртноев пяти вышеуказанныхгородах неизменились,расстояниеже от них (в милях)до портов указанов следующейтаблице:

	Бостон	Детройт	Вашингтон	Нью-Йорк	Чикаго
Порт1	250	300	500	100	600
Порт2	100	200	700	400	300
Порт3	500	400	300	550	150

Во всех трехслучаях суммарноерасстояниеот порта догородов недолжно превышать1000 миль. Требуетсярешить тот жесамый вопрос:в какие городавыгоднее поставлятьпродукцию?

4. Решение задачио многомерномранце (вручную).

Задачао многомерномранце имеетследующуюматематическуюмодель:

,(3)

где критериемявляется функция

,(4)

Отзадачи об одномерномранце она отличаетсяналичием несколькихограничений.Таким образом,математическаямодель:

Пусть

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

;

Целевойфункцией иликритерием будетявляться максимальнаяблагодарностьсограждан:

.

Решимзадачу оценкикритерия длякаждого ограниченияв отдельности.Пусть множество

относитсяк первомуограничению, –ко второму, а –к третьему.

1) Анализмножества

.

(3); (2); (4); (1); (5).

Определяемначальный план:

, ;

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому

будет дробным: ,=> .

Таким образом,начальныйопорный план:

.

;

2) Анализмножества

.

(1); (2); (5); (3); (4).

Определяемначальный план:

, ;

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниетакже равно300 миль, поэтому

будет целым: ,=> .

Таким образом,опорный план:

.

;

3) Анализмножества

.

(5); (2); (3); (4); (1).

Определяемначальный план:

, ;

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 550 миль,поэтому

будет дробным: ,=> .

Таким образом,опорный план:

.

;

4) Вычислениеверхней и нижнейграниц.

Вычисляемверхнюю границу:

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

Определяемопорные планыдля третьегоограничения:

a)

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому

.Таким образом: .

б)

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100 миль,поэтому

.Таким образом: .

в)В этом случае

.

Вычисляемнижнюю границу:

;

;

;

.

5) Ветвлениемножества D.

;

- здесь .

-здесь .

6) Анализмножества D₁.

a)Определяемначальный пландля

:

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

б)Определяемначальный пландля

:

, ;

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 700 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

в)Определяемначальный пландля

:

, ;

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 100миль, поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

г)Вычислениеверхней и нижнейграниц.

Вычисляемверхнюю границу:

;– первоеограничениеболее жесткое.

Определяемопорные планыдля первогоограничения:

–В этом случае

.

–

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 450 миль,поэтому

.Таким образом: .

–

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100миль, поэтому

.Таким образом: .

Вычисляемнижнюю границу:

Т.к.

,то ;

;

.

7) Анализмножества D₂.

Поскольку

,то:

.

=> ;

a)Определяемначальный пландля

:

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

б)Определяемначальный пландля

:

, ;

, ;

, ;

Таким образом,новый опорныйплан:

.

;

в)Определяемначальный пландля

:

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 400миль, поэтому

будет дробным: ,=> .Таким образом,новый опорныйплан: .

;

г)Вычислениеверхней и нижнейграниц.

Вычисляемверхнюю границу:

;– третьеограничениеболее жесткое.

Определяемопорные планыдля третьегоограничения:

–

, ;

Впоследнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому

.Таким образом: .

–

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 50 миль,поэтому

.Таким образом: .

– В этом случае

.

Вычисляемнижнюю границу:

Т.к.

,то ;

;

.

8) Отсевнеперспективногоподмножества.

.

Так как

и больше Rec,то оба подмножестваперспективные,но поскольку ,то далее мыбудем исследовать ,как болееперспективное.

;

- здесь .

-здесь .

9) Анализмножества D₃.

Поскольку

,то:

a)Определяемначальный пландля

:

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 600 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

б)Определяемначальный пландля

:

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 700 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

в)Определяемначальный пландля

:

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 350миль, поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

г)Вычислениеверхней и нижнейграниц.

Вычисляемверхнюю границу:

;– третьеограничениеболее жесткое.

Определяемопорные планыдля третьегоограничения:

–

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 100 миль,поэтому

.Таким образом: .

–

, ;

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеравно 300миль, поэтому

.Таким образом: .

–В этом случае

.

Вычисляемнижнюю границу:

;

Т.к.

,то ;

.

10) Анализмножества D₄.

Поскольку

,то:

.

=> ;

a)Определяемначальный пландля

:

, ;

В последнемслучае оставшеесяпосле другихгородов расстояниеменьше 500 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

б)Определяемначальный пландля

:

, ;

, ;

Таким образом,новый опорныйплан:

.

;

в)Определяемначальный пландля

:

В этом случаеоставшеесяпосле другихгородов расстояниеменьше 150 миль,поэтому

будет дробным: ,=> .

Таким образом,новый опорныйплан:

.

;

г)Вычислениеверхней и нижнейграниц.

Вычисляемверхнюю границу:

;– третьеограничениеболее жесткое.

Определяемопорные планыдля третьегоограничения:

Очевидно,что поскольку

,то .

Вычисляемнижнюю границу:

Т.к.

,то ;

.

Т

аккак и больше Rec,то оба подмножестваперспективные,но поскольку ,то подмножество более перспективное,следовательнооптимальнымпланом будет .То есть города,удовлетворяющиевсем 3 условиями при этом дающиемаксимальнуюприбыль – Детройти Нью-Йорк.

11

Лабораторнаяработа № 7

ТелешовойЕлизаветы, гр.726,

Решениезадачи коммивояжераметодомветвейи границ.

1. Постановказадачи.

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

	Деди бабка	Заяц	Волк	Медведь	Лиса
Деди бабка	0	6	4	5	2
Заяц	6	0	3	3,5	4,5
Волк	4	3	0	5,5	5
Медведь	5	3,5	5,5	0	2
Лиса	2	4,5	5	2	0

2. Математическаямодель задачи.

Для решениязадачи присвоимкаждому пунктумаршрута определенныйномер: дед ибабка – 1, заяц– 2, волк – 3, медведь– 4 и лиса – 5.Соответственнообщее количествопунктов

.Далее введем альтернативныхпеременных ,принимающихзначение 0, еслипереход изi-тогопункта в j-тыйне входитв маршрут и 1 впротивномслучае. Условияприбытия вкаждый пункти выхода изкаждого пунктатолько по одномуразу выражаютсяравенствами(1) и (2).

(1)

(2)

Для обеспечениянепрерывностимаршрута вводятсядополнительноnпеременных

и дополнительныхограничений(3).

(3)

Суммарнаяпротяженностьмаршрута F,которую необходимоминимизировать,запишется вследующем виде:

(4)

В нашем случаеэти условиязапишутся вследующем виде:

(1); (2);

(3)

(4)

3. Решение задачиметодом ветвейи границ.

1) Анализмножества D.

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

=> ;

Аналогичноопределяемматрицу минимальныхрасстоянийпо столбцам.

=> ;

;

Выберемначальный план:

.Тогда верхняяоценка:

.

Очевидно,что

,где означает переходиз первогопункта в j-тый.Рассмотримэти подмножествапо порядку.

2

) Анализ подмножестваD₁₂.

;

;

;

;

;

3

) АнализподмножестваD₁₃.

;

;

;

;

4

) АнализподмножестваD₁₄.

;

;

;

;

;

5

) АнализподмножестваD₁₅.

;

;

;

;

;

6)Отсев неперспективныхподмножеств.

;

ПодмножестваD₁₃ и D₁₅неперспективные.Т.к.

,но ,то далее будемрассматриватьподмножествоD₁₄.

.

7

) АнализподмножестваD₁₄₂.

;

;

;

;

;

8)Анализ подмножестваD₁₄₃.

;

;

;

;

9)Анализ подмножестваD₁₄₅.

;

;

;

;

;

10)Отсев неперспективныхподмножеств.

;

ПодмножествоD₁₄₃неперспективное.Т.к.

,но ,то далее будемрассматриватьподмножествоD₁₄₅.

.

9

) АнализподмножестваD₁₄₅₂.

;

;

;

;

;

9

) АнализподмножестваD₁₄₅₃.

;

;

;

;

;

;

Оптимальноерешение:

.

.

Такимобразом, маршрутколобка: деди бабка – медведь– лиса – заяц– волк – дед ибабка.

4