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

Лабораторнаяработа № 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)имеем:.

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

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

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

;

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

;

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

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

;

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

=>

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

,а из ограничений(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. Решим задачус учетом изменившихсяданных.

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

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

=>

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

,.

,.

,

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

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

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

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

4вариант.

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

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

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

=>

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

,при этом .

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

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

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

		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).

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

;

;

Тогда:

.

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

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

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

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

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

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

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

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

=> .

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

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

,

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

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

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

.

(4).

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

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

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

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

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

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

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

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

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

(5)

(6)

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

(5).

(6)

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

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

откуда

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

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

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

Из теорииизвестно, чтосправедливыследующиеформулы: (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-говида в единицеполученногосплава. Тогдафункция цели(себестоимостьединицы сплавав у.е.) запишетсяследующимобразом:

.

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

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

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

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

Экономическиполученноерешение интерпретируетсяследующимобразом: дляполученияединицы сплаваминимальнойсебестоимостинеобходимовзять 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 не входит винтервал устойчивостидвойственныхоценок, тодвойственныеоценки и номерабазисных переменныхсменятся ().

.

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

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

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

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

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

.

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

=>

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

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

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

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

Получимследующеерешение: ,.Таким образом,для изготовлениянового сплаванеобходимовзять 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,514у.е. (отрицательныйкоэффициентв целевой функциив данном случаене имеет экономическогосмысла, т.к.свидетельствуето полученииресурса с доплатой.В этом случаересурс выступаетв роли антиблага).Критерий изменитсяна .

б)

=> ,

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

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

а) ,тогда

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

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

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

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

,или ,.

,или ,

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

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

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

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

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

– при :;

– при :;

– при :;

– при :;

– при :;

.

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

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

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

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

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

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

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

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

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

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

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

Возьмем,например, какизменяющийсякоэффициент.Его изменениевлечёт за собойизменениеоценки толькосвободнойпеременной:

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

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

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

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

а) 100,2%

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

б) 110%

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

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

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

,.

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

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

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

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

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

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

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

Оптимальноерешение будет,.Это означает,что для производстванового сплавабудет использоваться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);

ну и конечно

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

;;

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

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

.

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

.

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

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

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

(1).

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

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

; ; ; ;

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

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

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

(2).

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

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

.

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

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

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

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

;;

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

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

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

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

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

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

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 столбецисключены.

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

.

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Строим цикл:

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

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

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

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

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

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

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

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

Определяем

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

.

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

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

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

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

(3)

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

;

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

;;

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

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

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

Определяем

.

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

Определяем

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

Определяем

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

.

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

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

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

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

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

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

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

.

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

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. Постановказадачи о многомерномранце.

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

Во всех трехслучаях суммарноерасстояниеот порта догородов недолжно превышать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

;

;

;

;

;

3

;

;

;

;

4

;

;

;

;

;

5

;

;

;

;

;

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

;

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

.

7

;

;

;

;

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

;

;

;

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

;

;

;

;

;

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

;

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

.

9

;

;

;

;

;

9

;

;

;

;

;

;

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

.

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

4