Учебное пособие: Методические указания по курсовой работе для студентов специальности 22. 02 Автоматизированные системы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ PОССИЙСКОЙ ФЕДЕPАЦИИ

ИPКУТСКИЙ ГОСУДАPСТВЕHHЫЙ

ТЕХHИЧЕСКИЙ УHИВЕPСИТЕТ

Факультет кибернетики

МАТЕМАТИЧЕСКИЕ МЕТОДЫ СИСТЕМНОГО АНАЛИЗА И ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

Методические указания по курсовой работе

для студентов специальности 22.02

«Автоматизированные системы

обработки информации и управления „

Иркутск, 2001г.

Куцый Н.Н. Математические методы системного анализа и теория принятия решений: Пособие по курсовой работе. – Иркутск, изд-во Иркутск. гос. технич. ун-та, 2001. – 39с.

Определены цель и задачи, тематика, содержание курсовой работы по учебной дисциплине “Математические методы системного анализа и теория принятия решений». Пособие предназначено для студентов специальностей 220100 – «Вычислительные машины, системы, сети и комплексы», 220200 – «Автоматизированные системы обработки информации и управления», 071900 – «Информационные системы в наукоемких технологиях».

Библиогр. 21 назв.

Рецензент: профессор, д.т.н. Массель Л. В.

Подготовила к печати: Брянская А.Г.

План 2001. 2,4 печ. л., 2,5 уч.-изд. л. Тираж 100 экз. Зак. 366

.

ЛР № 020263 от 30.12.96

Иркутский государственный технический университет

664074, Иркутск, ул. Лермонтова, 83

1.ЦЕЛЬ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ

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

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

— освоить принципы формализации на примере реальной задачи организационного управления;

— показать знакомство с методами решения, принятыми в математическом программировании, в рамках которого решается описываемая задача;

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

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

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

— показать способность работать с литературой.

2.ТЕМАТИКА И ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Курсовая работа может разрабатываться на базе тем, освещенных в учебных занятиях по дисциплине «Математические методы системного анализа и теория принятия решений» для специальности «Авто­мати­зиро­ванные системы обработки информации и управления». Однако с учетом специфики дисциплины «Математические методы системного анализа и теория принятия решений», заключающейся в её многообразии разделов, курсовая работа может быть основана на материале, который должен быть освоен самим студентом.

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

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

3. СОДЕРЖАНИЕ КУРСОВОЙ РАБОТЫ

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

Пояснительная записка должна содержать следующие разделы:

— постановка задачи;

— обоснование разработанной математической модели;

— краткие сведения о методе решения поставленной задачи;

— алгоритм решения задачи, на основании которого составлена программа;

— фрагмент листинга программы, относящийся к реализации алгоритма решения задачи;

— проверка достоверности полученных результатов;

— руководство пользователя;

— результаты решения задачи курсовой работы на ПЭВМ по исходным данным индивидуального варианта;

— список использованной литературы.

ВАРИАНТЫ ТЕМ КУРСОВОЙ РАБОТЫ

ТЕМА 1. ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СУДОВ ПО РЕГУЛЯРНЫМ ЛИНИЯМ

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

Исходя из данных о себестоимости грузокилометра и коммерческой загрузки каждого типа судна на каждой линии устанавливается:

а) величина месячный объем перевозок одним судном j -го типа i -ой регулярной линии;

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

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

где N — общее число судов, которое необходимо распределить по m линиям.

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

Все условия данной задачи сведены в таблицу 1.

Таблица 1

№ типа судна Þ № линии ß	1	· · ·	j	· · ·	n	Минималь­­ный объем пе­ревозок
1		· · ·		· · ·
· · ·	· · ·	· · ·	· · ·	· · ·	· · ·	· · ·
i		· · ·		· · ·
· · ·	· · ·	· · ·	· · ·	· · ·	· · ·	· · ·
m		· · ·		· · ·
Число судов		· · ·		· · ·

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

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

2.Отсутствие чисел и в i -ой строке и в j- ом столбце означает невозможность использования судна j -го типа на i -ой регулярной линии.

Таблица 2

№ типа судна Þ № линии ß	1	2	3	4	Минималь­ный объем перевозок
1
2
3
4
Число судов	55	95	30	45

Вариант 1.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод искусственных переменных [9].

Вариант 1.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига [9].

Вариант 1.3. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях [11].

Вариант 1.4. Решить поставленную задачу двойственным симплекс-методом [9].

Вариант 1.5. Решить поставленную задачу следующим образом. Вначале записать прямую задачу линейного программирования; затем, осуществив переход к двойственной задаче линейного программирования, решить ее методом симплекс-таблиц, основанном на методе полного исключения Гаусса. От полученного решения перейти к решению прямой задачи [9].

Вариант 1.6. Решить поставленную задачу, применяя метод Гомори [9].

ТЕМА 2. ЗАДАЧА СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ГРАФИКА РЕМОНТА ИНСТРУМЕНТА

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

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

Конкретные числовые условия задачи сведены в таблицу.

n сутки	кол-во еди­ниц	p сутки	b рублей	q сутки	с рублей	a рублей
7	40 (j= 1(1)4); 0 j =5; 20 (j= 6,7)	3	2	2	4	6

Вариант 2.1. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига [9].

Вариант 2.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применив для нахождения начального допустимого базисного решения метод искусственных переменных [9].

Вариант 2.3. Решить поставленную задачу симплекс-методом, основанном на модифицированных жордановых исключениях [11].

Вариант 2.4. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить методом потенциалов, использовав для нахождения начального опорного плана метод северо-западного угла [9,11].

Вариант 2.5. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить методом потенциалов, использовав для нахождения начального опорного плана метод минимального элемента [9,11].

Вариант 2.6. Решить поставленную задачу следующим образом. Свести эту задачу к эквивалентной ей транспортной задаче. Последнюю решить венгерским методом [9,11].

ТЕМА 3. ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ

Имеется m пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется единиц этого продукта, во втором — единиц, в i -ом — единиц, и, наконец, в m -ом пункте — единиц продукта. Этот продукт следует доставить в n пунктов назначения (потребления), причем в первый пункт назначения следует доставить единиц продукта, во второй — единиц, в j -й — единиц, и, наконец, в n -й пункт — единиц продукта.

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

Удельные стоимости и время перевозок приведены в таблице, при этом:

1) на пропускные способности коммуникаций ограничения не накладываются;

2) и — количество условных единиц продукта;

3) в верхних отделениях клеток таблицы помещены удельные стоимости в рублях, а в нижних — время перевозок в часах.

B j Þ A i ß	B 1	B 2	B 3	B 4	B 5	B 6	B 7	B 8	a i
A 1									180
A 2									140
A 3									50
A 4									150
A 5									80
A 6									80
A 7									70
bj	50	80	10	40	140	110	130	150

Вариант 3.1. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод северо-западного угла [9].

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

Вариант 3.3. Составить план, минимизирующий общую стоимость перевозок; определить уровень временных затрат при этом плане; произвести, если это возможно, дооптимизацию по времени. Поставленную задачу решить венгерским методом [9].

Вариант 3.4. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Поставленную задачу решить, применяя метод, в основе которого лежит построение «разгрузочного» цикла [13].

Вариант 3.5. Составить план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок; определить для этого плана стоимость перевозок; произвести, если это возможно, дооптимизацию по критерию стоимости. Первую часть задачи решить, применяя вариант метода потенциалов, при дополнительных условиях, вводимых последовательно в процесс решения [13].

ТЕМА 4. ЗАДАЧА О НАИЛУЧШЕМ РАСПРЕДЕЛЕНИИ ПРОГРАММЫ МЕЖДУ НЕСКОЛЬКИМИ ПРЕДПРИЯТИЯМИ

(ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ ОБОРУДОВАНИЯ)

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

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

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

№ типа пред­прия­тия Þ № изделия ß	1	2	3	4	5	Число изделий в комплекте
1	100	400	20	200	600	2
2	15	200	25	50	250	1
3	100	150	200	25	350	3
Число предприятий	5	3	40	9	2

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

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

Вариант 4.3. Решить поставленную задачу, применяя метод Гомори.

ТЕМА 5. ИССЛЕДОВАНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО НАЗНАЧЕНИЯ НА АВИАРЕЙСЫ

Авиалиния, работающая в течение всей недели, имеет расписание рейсов, приведенное в таблице. Между полетами, экипажи должны иметь отдых не менее 5 часов. Вместе с тем экипаж не должен ждать рейса более чем 24 часа. Задача заключается в следующем. Где должны базироваться экипажи и какие рейсы они должны обслуживать, чтобы суммарное время, которое все экипажи имеют на ожидание обратного рейса, было минимальным.

Москва — Санкт-Петербург	Санкт-Петербург – Москва
№ рейса	Отправление	Прибытие	№ рейса	Отправление	Прибытие
1	7 час.	8 час.	101	8 час.	9 час. 15 мин.
2	8 час.	9 час.	102	8 час. 30 мин.	9 час. 45 мин.
3	13 час. 30 мин.	14 час. 30 мин.	103	12 час.	13 час. 15 мин.
4	18 час. 30 мин.	19 час. 30 мин.	104	17 час 30 мин.	18 час. 45 мин.
5	20 час.	21 час.	105	19 час.	20 час. 15 мин.
6	23 час. 30 мин.	0 час. 30 мин.	106	22 час.	23 час. 15 мин.

ТЕМА 6. ИССЛЕДОВАНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ ОБЪЕМОВ ВЫПУСКАЕМЫХ ИЗДЕЛИЙ

На рис.1 показаны технологические маршруты изготовления трех изделий на предприятии. Исходя из данных, приведенных ниже, сформулируйте и решите задачу выбора объема выпуска каждого изделия. Продажные цены изделий первого, второго и третьего соответственно равны 5,0; 4,5; 3,5 единиц стоимости, исследуйте загрузку оборудования при полученном оптимальном плане и определите расходы сырья.

Рис. 1.

Изделия	СТАНКИ
А	B	C	Д
1.Выпуск в час	500	1000	1850	-
2.Выпуск в час	12000	1500	2300	1400
3.Выпуск в час	-	-	1600	800
Эксплуатационные затраты в час
500	450	800	600
Время простоя %	10	5	5	10
Сырье
P	O	K
Расход единиц сырья на изделие 1	1	1,25	2,0
Расход единиц сырья на изделие 2	-	2,0	2,5
Расход единиц сырья на изделие 3	1,5	-	1,75
Стоимость единиц сырья	0,25	0,35	0,3

Вариант 6.1. Исходя из данных, приведенных в таблице, сфор­мулируйте и решите задачу выбора объема выпуска каждого изделия. Исследуйте загрузку обо­рудования при полученном оп­ти­мальном решении и определите расходы сырья. При решении примените вариант симплексного метода, изложенного в [1].

Вариант 6.2. Исходя из данных, приведенных в таблице, сфор­мулируйте и решите задачу выбора объема выпуска каждого изделия. Исследуйте загрузку оборудования при полученном оп­ти­мальном решении и определите расходы сырья. При решении примените метод симплекс-таблиц.

ТЕМА 7. ДВУХЭТАПНАЯ ТРАНСПОРТНАЯ ЗАДАЧА

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

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

Таблица 1

Холодильники Þ Маслодельные заводы ß	Николаевка	Павловск	Александровка
1-ый масло­дель­ный завод	20	23	16
2-ый масло­дель­ный завод	15	10	24

Таблица 2

Пункты торговлиÞ Холодильники ß	Гончарово	Гришево	Гмелино	Седаново
Николаевка	17	22	20	23
Павловск	20	25	24	22
Александ­ровка	16	21	25	11

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

Вариант 7.2. Данную двухэтапную транспортную задачу свести к классической транспортной задаче, при решении которой использовать метод «северо-западного угла» с последующим применением метода потенциалов.

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

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

ТЕМА 8. ДИНАМИЧЕСКАЯ ЗАДАЧА ВЫБОРА ОБЪЕМА ПАРТИЙ

Предприятие должно разработать календарную программу выпуска некоторого вида изделий на плановый период, состоящий из N отрезков. Предполагается, что для каждого из отрезков известен точный прогноз спроса на выпускаемую продукцию; для разных отрезков времени спрос не одинаков. Временем изготовления партий изделий пренебрегаем. Стоимость выпуска партии зависит от ее объема. Предприятию часто бывает выгодно изготавливать в течение некоторого отрезка продукцию в объеме превышающем спрос в пределах этого отрезка, и хранить излишки, используя их для удовлетворения спроса в последующие периоды. Вместе с тем, хранение запасов связано с определенными затратами, в состав которых входят, в частности, расходы по содержанию запасов, арендная плата за складские помещения и т.д. Обозна­чим через затраты по хранению избыточного запаса на i -ом отрезке.

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

Вариант 8.1. Число отрезков N = 6,

где

Спрос по периодам равен соответственно

Вариант 8.2. Число отрезков N = 8,

где

Спрос по периодам равен соответственно

Выяснить, при каком соотношении между фиксированной стоимостью заказа партии А и удельными затратами на хранение S оптимальная программа изготовления деталей будет совпадать со спросом, т.е.

Вариант 8.3. Число отрезков N = 7,

где

Спрос по периодам равен соответственно

Найти оптимальные программы выпуска партий и сравнить их для S = 1,2,4.

ТЕМА 9. ЗАДАЧА УПРАВЛЕНИЯ ЗАПАСАМИ ПРИ СЛУЧАЙНОМ СПРОСЕ

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

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

Вариант 9.1. Решить поставленную задачу при стоимости одного изделия 200 руб., затраты в случае выхода изделия из строя 500 руб. при максимальном количестве исследуемых деталей равном семи. Вероятности выхода из строя n изделий задана в виде: P (1)=0,35; P (2)=0,22; P (3)=0,16; P (4)=0,1; P (5)=0,08; P (6)=0,06; P (7)=0,03.

Исследовать зависимость величины минимума целевой функции от соотношения

Вариант 9.2. Решить поставленную задачу при стоимости одного изделия 200 руб., затраты в случае выхода одного изделия из строя 500 руб. При определении вероятности выхода из строя n изделий следует руководствоваться следующими выражениями

Исследовать изменение минимума целевой функции от параметра а = 0(1)10. Ответить на вопрос о физическом смысле параметра a в данной задаче.

ТЕМА 10. ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСКРОЕ МАТЕРИАЛОВ

(О МИНИМИЗАЦИИ ОТХОДОВ)

Пусть некоторый полуфабрикат (например, листы фанеры) поступил на предприятие в виде m различных партий, содержащих соответственно единиц полуфабрикатов одинакового для каждой партии размера. Из поступивших полуфабрикатов требуется изготовить возможно большее число комплектов деталей, в каждый из которых входит деталей первого вида, деталей второго вида, ..., деталей l -го вида. Пусть каждую единицу полуфабриката можно раскроить на детали n различными способами, причем при раскрое единицы i -й партии j -м способом получается деталей s- го вида.

Конкретные данные задачи приведены ниже.

В обработку поступили три партии досок для изготовления комплектов из четырех деталей, причем первая содержит 50 досок длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая, третья содержит 100 досок длиной по 3 м каждая. Каждый комплект состоит из двух деталей по 2 м каждая и двух деталей длиной в 1,25 м каждая.

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

Доска длиной 6,5 м может быть распилена на детали требуемых размеров следующими способами:

1) 3 детали по 2 м;

2) 2 детали по 2 м и 2 детали по 1,25м ;

3) 1 деталь в 2 м и 3 детали по 1,25 м ;

4) 5 деталей по 1,25 м.

Доска длиной в 4 м может быть распилена на детали следующими способами:

1) 2 детали по 2 м;

2) 1 деталь в 2 м и 1 деталь в 1,25м ;

3) 3 детали по 1,25м .

Доска длиной в 3 м может быть распилена на детали следующими способами:

1) 1 деталь в 2 м;

2) 2 детали по 1,25м .

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

Вариант 10.2. Решить поставленную задачу методом симплекс-таблиц, основанном на методе полного исключения Гаусса, применяя для нахождения начального допустимого базисного решения метод Данцига.

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

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

Вариант 10.5. Решить поставленную задачу следующим образом. Вначале записать прямую задачу линейного программирования; затем осуществив переход к двойственной задаче линейного программирования решить ее методом симплекс-таблиц, основанном на методе полного исключения Гаусса. От полученного решения перейти к решению прямой задачи.

Вариант 10.6. Решить поставленную задачу, применяя метод Гомори.

ТЕМА 11. УПРАВЛЕНИЕ СИСТЕМОЙ МАРКОВСКОГО ТИПА С ДОХОДАМИ

Имеется предприятие, выпускающее галстуки, которое планирует свою работу на 12 месяцев вперед.

Предприятие может находиться в одном из двух состояний:

а) модель предыдущего месяца удачна;

б) модель предыдущего месяца неудачна.

Переходы за месяц из одного состояния в другое описываются матрицей вероятностей . С каждым переходом из состояния i в состояние j матрица доходов R.

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

а) k = 1 — не проводить никаких дополнительных исследований;

б) k = 2 — провести дополнительные исследования конъюнктуры спроса;

в) k = 3 — затратить дополнительные средства на рекламу своей продукции.

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

Вариант 11.2. Применив метод итераций по стратегиям Ховарда найти оптимальную стратегию управления, обеспечивающую максимальный доход предприятия.

Конкретные данные заданы следующим образом.

Стратегия k = 1

j Þ i -	1	2	j Þ i -	1	2
P=	1	0,5	0,5	R=	1	7	3
2	0,3	0,7	2	5	1

Стратегия k = 2

Провести дополнительные исследования коньюктуры рынка

j Þ i -	1	2	j Þ i -	1	2
P=	1	0,6	0,4	R=	1	3	-5
2	0,7	0,3	2	1	-18

Стратегия k = 3

Затратить дополнительные средства на рекламу своей продукции

j Þ i -	1	2	j Þ i -	1	2
P=	1	0,7	0,3	R=	1	2	-8
2	0,8	0,2	2	-20

ТЕМА 12. ЗАДАЧА О ДОБЫЧЕ ПЕСКА В КАРЬЕРАХ И ЕГО ДОСТАВКЕ

Строительный песок добывается в трех карьерах и доставляется на четыре строительных площадки. Данные о производительности карьеров за сутки (в тоннах), потребностях в песке строительных площадках (в тоннах), затратах на добычу песка (руб/тонна) и транспортных расходах приведены в следующей таблице

ai ¯ bj ®	40	35	30	45	di
46	4	3	2	5	2
34	1	1	6	4	3
40	3	5	9	4	1

Недостающее количество песка – 30 т за сутки можно обеспечить следующими тремя путями:

1)увеличение производительности 1-го карьера, что повлечет за собой дополнительные затраты на добычу 1 т в 3 руб.

2)увеличение производительности 2-го карьера в дополнительными затратами в 2 руб. на добычу 1 т.

3)эксплуатация нового карьера с затратами на добычу 1 т – 5 руб., и на транспортировку к указанным строительным площадкам —

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

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

Вариант 12.2. Поставленную задачу решить методом потенциалов, использовав для нахождения начального опорного плана метод «северо-западного угла».

Вариант 12.3. Поставленную задачу решить венгерским методом.

Тема 13. Задача о пополнении запасов

Акционерное общество «Меркурий» имеет сорок автоцистерн для перевозки нефтепродуктов. Каждая машина обута в десять шин, запас которых хотя, поэтому желательно иметь в своем распоряжении не слишком больший запас; но при отсутствии шин в запасе акционерное общество терпит убытки из-за невозможности выполнить отдельные заказы на перевозки.

За шинами следит осмотрщик, который по виду шин выносит заключение о ее состоянии. Он подметил, что шина, изношенная на 20% прошла 6000 км; на 40% — 12 000 км; на 60 % — 18 000 км; на 80 % — 24 000 км и на 100 % — 30 000 км. Но, как бы там ни было, не все шины выдерживают 30 000 км.

Исследование, которое проводилось в течение многих лет, показало, что согласно статистике, на 100 шин, введенных в эксплуатацию, 5 выходят из строя после 6000 км, 10 – между 6000 и 12 000 км; 25 – между 12 000 и 18 000 км; 30 – между 18 000 и 24 000 км; 30 между 24 000 и 30 00 км. Таким образом, можно определить кривую продолжительности жизни шин, которая давала бы число шин, находящихся еще в эксплуатации после пробега 6000, 12 000 и т.д. километров.

Дирекция планирует ездки машин на неделю; важно заказывать шины в количестве, достаточном, чтобы произвести вследствие износа или случайного повреждения. Допустим, что машина пробегает за неделю 2000 км; что за неделю дает пробег в 80 000 км для всех машин и 800 000 км для всех шин.

Какой должен быть режим их поступления, или, иными словами, норма поступления запасов?

Вариант 13.1. Решить поставленную задачу рекуррентным способом [10].

Вариант 13.2. Решить поставленную задачу, применяя расчет по математическим ожиданиям [10].

ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ

1.Сведение к задаче линейного программирования задачи темы 1.

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

N типа судна Þ N линии ß	1	2	3	Мини­мальный объем перевозок
1				300000
2				200000
3				100000
4				500000
Число судов	50	95	30

Составить математическую модель для задачи линейного программирования следующего содержания. Математическую модель составить для двух вариантов: 1.поставлено требование, чтобы в перевозках участвовали все суда; 2. часть судов, при условии выполнения условия минимального объема перевозок разрешается сдавать в аренду.

Обозначим через число судов j- го типа (j =1,2,3), которое планируется закрепить за i -й (i -1,2,3,4) регулярной линией.

С учетом введенных обозначений математическая модель задачи для 1-го варианта может быть представлена

найти

при ограничениях

и при

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

Математическая модель для 2-го варианта может быть представлена

и при

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

найти

при ограничениях

и при

Из сопоставления двух моделей для и видно, что соответствует и соответствует

2.Сведение к задаче линейного программирования задачи темы 2

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

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

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

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

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

число инструментов, сдаваемых в обычный ремонт в конце -го дня;

число инструментов, сдаваемых в срочный ремонт в конце го дня;

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

Тогда число инструментов, поступающих в употребление в начале го дня, состоит:

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

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

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

где количество инструмента, купленного для использования в 1-й день; , так как до начала выполнения производственной программы в ремонт не мог поступать использованный инструмент и в первые дней (в нашем случае 2 дня) еще не поступит из ремонта в употребление ни одного инструмента, сданного даже в срочный ремонт, а в первые дней (в нашем случае 3 дня) не поступит в употребление ни одного инструмента, сданного в обычный ремонт.

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

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

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

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

Тем самым задача заключается в минимизации общей стоимости издержек

при ограничениях

и условиях

3.Сведение к транспортной задаче задачи темы 2.

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

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

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

при

при

при

и стоимость перевозки со склада нового инструмента в любой пункт потребления

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

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

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

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

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

Условия эквивалентной транспортной задачи представлены в виде следующей таблицы.

rj ri	10	10	10	10	10	50
10	∞	∞	5	1	1
10	∞	∞	∞	5	1
10	∞	∞	∞	∞	5
10	∞	∞	∞	∞	∞
10	∞	∞	∞	∞	∞
50	6	6	6	6	6

Здесь для уравновешивания баланса производства и потребления с потребностью пятьдесят, равной разности между суммарным количеством инструмента, который имеется на складе в качестве нового инструмента плюс изношенный за пять дней, и количеством инструмента, используемого за пять дней; стоимости перевозок в фиктивный пункт потребления равны нулю. Числа в клетках (стоимости перевозок) равны стоимостям обычного или срочного ремонта одного инструмента или покупки одного нового инструмента. Стоимость означает, как сказано выше, что инструмент, сданный в ремонт в конце го дня, не успеет вернуться к началу го дня даже из срочного ремонта (не сможет быть отремонтирован к концу дня «ни за какие деньги»); например, означает, что инструмент, сданный даже в срочный ремонт в конце первого дня, еще не поступит в употребление во второй день, так как он лишь в конце второго дня вернется из срочного ремонта. При решении транспортной задачи вместо знака ¥ следует поставить, как отмечено выше, число М, которое гораздо больше самой высокой стоимости, которая встречается в исходной задаче.

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

rj ri	10	10	10	10	10	50
10	10
10	10
10	10
10	10
10	10
50	10	10	10	10	10	20

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

Тема 3. Транспортная задача по критерию времени

Покажем на конкретном примере решение транспортной задачи по критерию времени.

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

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

Подчеркнем два момента:

а)перевозки считаются законченными, если закончилась самая длительная перевозка;

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

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

то по этому плану в общем случае продукт потребителю не будет доставлен в кратчайший срок.

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

Дальнейшие расчеты можно вести одним из двух методов: 1)минимизировать функцию но при дополнительных условиях, вводимых последовательно в процессе решения; 2)производить последовательные преобразования решения путем построения так называемых «разгрузочных циклов».

Первый способ. 1-ый шаг. Имеем начальный опорный план

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

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

2-ой шаг. Для измененной на 2-ом шаге матрицы ищем оптимальное решение, минимизирующее функцию

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

Отсюда

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

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

Возвращаемся к 1-ому шагу, продолжая расчеты в той же последовательности

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

2-ой шаг. Исходя из этой матрицы, применением метода потенциалов находим

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

Второй способ. 1-ый шаг. Имеем начальный опорный план

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

2-й шаг. В плане перевозок строим «разгрузочный» цикл, начиная с элемента , при этом на нечетном местах этого цикла , при этом считаем стоящим на первом месте.

В данном случае в «разгрузочный» цикл входят элементы Перемещая по этому циклу число получим новый план перевозок, равный

Так как перевозка не оказалась равной нулю, то продолжаем построение «разгрузочного» цикла, вновь начиная с элемента .

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

1-ый этап. Наибольшим элементом для элементов плана оказывается элемент поэтому и подчеркиваем.

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

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

Авиалиния, работающая в течение всей недели, имеет расписание рейсов, приведенное в таблице 5.1.

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

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

Таблица 5.1

Пункт А ® пункт В	Пункт В ® пункт А
№ рейса	Отправление	Прибытие	№ рейса	Отправление	Прибытие
1	06.00	12.00	101	05.30	11.30
2	07.30	13.30	102	09.00	15.00
3	11.30	17.30	103	15.00	21.00
4	19.00	01.00	104	18.30	00.30
5	00.30	06.30	105	00.00	06.00

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

Предположим, например, что экипаж базируется (живет) вА и обслуживает рейс 3 в направлении В и рейс 102 в противоположном направлении. Этот экипаж должен ждать в пункте В 15.5 часа (от 17.30 до 09.00). Составим путем аналогичных расчетов две матрицы, оформленные в виде таблиц 5.2 и 5.3, элементы которых отражают величины потерянного времени, считая в первом случае, что все экипажи живут в пункте А, а во втором, что все они живут в пункте В. В таблице 5.2. элемент время ожидания при обслуживании рейса под номером (вылет из пункта проживания А ) и обслуживание рейса, номер которого определяется как (возвращение в пункт проживания А из пункта В ). В таблице 5.3 элемент время ожидания при обслуживании рейса под номером (вылет из пункта проживания В ) и обслуживание рейса, номер которого определяется как (возвращение в пункт проживания В из пункта А ).

Таблица 5.2

Все экипажи живут в пункте А

17.5	21	3	6.5	12
16	19.5	1.5	5	10.5
12	15.5	21.5	1	6.5
4.5	8	14	17.5	23
23	2.5	8.5	12	17.5

Таблица 5.3

Все экипажи живут в пункте B

18.5	15	9	5.5
20	16.5	10.5	7	1.5
20.5	14.5	11	5.5
7.5	4	22	18.5	13
13	9.5	3.5	18.5

Составим теперь на основе этих двух таблиц третью (таблица 5.4.), каждый элемент которой будет являться меньшим из чисел, занимающих соответствующие клетки в двух исходных таблицах. При этом мы не будем принимать во внимание числа, которые не превосходят четырех, учитывая потребности экипажа в отдыхе. Например, если нам представится выбор между числами (1, 101; место жительства в пункте А ) и (101, 1; место жительства в пункте B ), то выбрать следует (1, 101), которое дает нам ожидание в 17,5 часа вместо 18,5 часа. Напротив из (3, 102; место жительство в пункте А ) и (102,3; место жительства в пункте B ) мы выбираем (3, 102), хотя этому варианту и соответствует меньшее время, т.к. вариант (102,3) оставляет на отдых меньше 4 часов и поэтому неприемлем. Отметим, что время ожидания свыше 24 часов мы предусмотрительно не учитывали в наших таблицах.

Таблица 5.4

17,5	15	9	5,5	12
16	16,5	10,5	5	10,5
12	15.5	14.5	11	5,5
4.5	8	14	17.5	13
13	9,5	8,5	12	17,5

Назовем назначением факт приписания экипажа одному из рейсов (скажем (102,1) (3,102), (104,2) и т.д.). Понятно, что каждый экипаж может быть назначен лишь на один прямой и один обратный рейс. Тем самым, любое возможное решение задачи о назначениях может быть представлено таблицей, элементами которой являются числа 0 и 1, причем в каждой строке и в каждом столбце имеется только одна единица, отмечающая выбранное значение. В таблице 5.5 приведен пример возможного решения.

Таблица 5.5

1

1

1

1

1

Решение, описываемое таблицей 5.5 соответствует, как можно установить рассматривая и предыдущие таблицы, рейсам (2,101), (102,1), (5,103), (104,3), (105,4), т.е. при таком варианте трем экипажам следует базироваться в пункте А, а двум — в пункте B. Суммарные потери времени будут составлять

15 + 16 + 5,5 + 14 + 12 = 62,5 часа.

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

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

Процесс решения расчленяется на шесть этапов.

ЭТАП 1. ПОЛУЧЕНИЕ НУЛЕЙ

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

Таблица 5.6.

17,5	15	9	5,5	12
16	16,5	10,5	5	10,5
12	15.5	14.5	11	5,5
4.5	8	14	17,5	13
13	9,5	8,5	12	17,5

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

где для рассматриваемого случая

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

Таблица 5.7

1	2	3	4	5
1	13	7	0,5	0,5	6,5
2	11,5	8,5	2	5
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12

ЭТАП 2. ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ

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

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

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

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

Следовательно, необходим переход к следующему, третьему этапу.

Таблица 5.7а

1	2	3	4	5
1	13	7	0,5	0,5	6,5
2	11.5	8,5	2	5
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12

ЭТАП 3. ПОИСКИ МИНИМАЛЬНОГО НАБОРА СТРОК И СТОЛБЦОВ, СОДЕРЖАЩИХ ВСЕ НУЛИ

Будем выполнять действия в такой последовательности:

а) пометим символом (§) все те строки, которые не содержат ни одного подчеркнутого двойной чертой нуля;

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

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

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

Этот процесс позволит нам получить минимальное число строк и столбцов, которые содержат все подчеркнутые двойной чертой или перечеркнутые нули. Как это происходит, будет видно на этапе 4.

В нашем примере помечена строка 1; столбцов, которые следовало бы отметить, нет.

Таблица 5.8

1	2	3	4	5
1	13	7	0,5	0,5	6,5	§
2	11.5	8,5	2	5
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12

ЭТАП 4. ЗАВЕРШЕНИЕ ЭТАПА 3

Отметим заливкой каждую непомеченную строку и каждый помеченный столбец. Это даст нам минимальное число строк и столбцов, которые содержат все перечеркнутые или подчеркнутые двойной чертой нули. В рассматриваемом примере необходимо отметить заливкой строки 2,3,4,5 и не отмечать заливкой столбцов.

Таблица 5.9

1	2	3	4	5
1	13	7	0,5	0,5	6,5	§
2	11,5	8,5	2	5
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12

ЭТАП 5. ПЕРЕМЕЩЕНИЕ НЕКОТОРЫХ НУЛЕЙ

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

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

В рассматриваемом примере по-прежнему неотмеченными заливкой элементами являются элементы строки 1; наименьший элемент этой строки равен 0,5. Поэтому вычтем 0,5 из всех элементов столбцов 1,2,3,4,5 и прибавим 0,5 к элементам строк 2,3,4,5. Если формально рассмотреть эти действия, т.е. вычитание и сложение, то следует отметить, что фактически выполнено вычитание 0,5 из элементов строки 1. Тем самым получим таблицу 5.10.

Таблица 5.10

1	2	3	4	5
1	12,5	6,5	6
2	11,5	8,5	2	5
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12

ЭТАП 6. ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ ИЛИ ВЫПОЛНЕНИЕ ОЧЕРЕДНОГО ШАГА

Будем в новой, полученной на этапе 5, таблице, которая содержит числа , искать оптимальное решение, как это представлено в описании этапа 2. Если при этом получим оптимальное решение, то процесс заканчивается. Если это не так, то повторим этапы 3,4 и 5. Затем, при необходимости, вернемся к этому этапу еще раз.

Повторим этап 2 в рассматриваемом примере получим таблицу 5.11.

Таблица 5.11

1	2	3	4	5
1	12,5	6,5	6	§
2	11,5	8,5	2	5	§
3	7,5	7,5	6	6
4	5,5	12,5	7,5
5	8,5	1,5	7	12	§
§	§

Таблица 5.11 содержит новые перечеркнутые и подчеркнутые двойной чертой нули. И так как мы получили четыре подчеркнутых двойной чертой нуля, количество которых не равно размерности нашей таблицы, то переходим к этапу 3.

Преследуя учебные цели, опишем более или менее подробно последующие поэтапные действия. Пометим символом (§) строку 1, как строку, которая не содержит ни одного подчеркнутого двойной чертой нуля. Отметим символами (§) столбцы 3 и 4, каждый из которых содержит перечеркнутый нуль в помеченной строке 1. Отметим строки 2 и 5, как строки, каждая из которых имеет подчеркнутый двойной чертой нуль, в каждом из помеченных столбцов.

Отметим заливкой каждую непомеченную строку и каждый помеченный столбец, т.е. в нашем случае это строки 3 и 4, а столбцы также 3 и 4, но это не более чем совпадение.

Рассмотрим часть таблицы, которая неотмечена заливкой и возьмем наименьшее в ней, т.е. здесь 1.5 и вычтем это число из элементов столбцов 1,2 и 5, как из неотмеченных заливкой столбцов и строк. Тем самым мы получим таблицу 5.12.

Таблица 5.12

1	2	3	4	5
1	11	5	4,5	§
2	10	7	2	3,5	§
3	7,5	7,5	7,5	7,5
4	7	14	7,5	§
5	7	7	10,5	§
§	§	§	§

Применим к таблице 5.12 действия этапа 2 и получим, что число подчеркнутых двойной чертой не равно размерности матрицы, т.е. пяти. Тем самым переходим к этапу 3. Затем в таблице 5.12 отметим заливкой непомеченную строку 3 и помеченные столбцы 2,2,3,4. Оформим результаты действий в виде таблицы 5.13.

Таблица 5.13

1	2	3	4	5
1	11	5	4,5	§
2	10	7	2	3,5	§
3	7,5	7,5	7,5	7,5
4	7	14	7.5	§
5	7	7	10,5	§
§	§	§	§

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

Таблица 5.14

1	2	3	4	5
1	11	5	1
2	10	7	2
3	11	11	11	11
4	7	14	4
5	7	7	7

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

9 + 5 + 5,5 + 4,5 + 9,5 =33,5.

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

Таблица 5.15

1	2	3	4	5
1	1
2	1
3	1
4	1
5	1

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

В первом столбце 1 соответствует времени 4,5 из таблицы 5.4, а это значение времени взято из таблицы 5.2 и из чего следует, что 1-ый экипаж живет в пункте А и обслуживает рейсы 1 и 104. Перерыв 4,5 часа.

Во втором столбце 1 соответствует времени 9,5 часа из таблицы 5.4, а это значение взято из таблицы 5.3, из чего следует, что 2-ой экипаж живет в пункте B и обслуживает рейсы 105 и 2. Перерыв 9,5 часов.

Продолжая этот процесс далее получим.

3-й экипаж живет в пункте B. Обслуживает рейсы 101 и 3. Перерыв 9 часов.

4-й экипаж живет в пункте A и обслуживает рейсы 4 и 102. Перерыв 5 часов.

5-й экипаж живет в пункте B. Обслуживает рейсы 103 и 5. Перерыв 5,5 часов.

ЛИТЕРАТУРА

1.Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971. — 534с.

2.Акоф Р. Искусство решения проблем. — М.: Мир, 1982. -224с.

3.Алексеев А.Д. Многовариантная транспортная задача по критерию времени//Известия АН СССР. Техническая кибернетика. — 1984. — № 6. — С.188-189.

4.Банди Б. Основы линейного программирования. — М.: Радио и связь, 1989. — 176с.

5.Вентцель Е.С., Овчаров Л.А. Прикладные задачи теории вероятностей. — М.: Радио и связь, 1983. — 416с.

6.Гольштейн Е.Г., Юдин Д.В. Задачи линейного программирования транспортного типа. — М., Наука, 1969. — 284с.

7.Данциг Дж. Линейное программирование. Его применения и обобщения/Пер. с англ. -–М., Наука, 1969. – 284с.

8.Дегтярев Ю.И. Исследование операций: Учеб. для вузов по спец. АСУ. – М.: Высшая школа, 1986. – 320с.

9.Зайченко Ю.П. Исследование операций. – 2-е изд., перераб. и доп. Киев: Вища школа, 1979. 392с.

10.Кофман А., Фор Р. Займемся исследованием операций/Пер. с франц. под ред. А.А. Корбута. — М.: Мир, 1966. -279с.

13.Калихман И.Л. Сборник задач по линейной алгебре и программированию. — М.: Высшая школа, 1969. — 160с.

14.Зайченко Ю.П., Шумилова С.А. Исследование операций. Сборник задач. — Киев: Вища школа. Изд-во Киев. ун-та, 1984. — 224с.

15.Исследование операций: В 2-х томах/ Под ред. Дж. Моуэра, С. Элмаграби. — М.: Мир, 1981.

16.Калихман И.Л. Линейная алгебра и программирование. — М.: Высшая школа, 1967. — 427с.

17.Кофман А. Методы и модели исследования операций. — М.: Мир,1966. — 524с.

18.Кудрявцев Е.М. Исследование операция в задачах, алгоритмах и программах. — М.: Радио и связь, 1984. -183с.

19.Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы. — М.: Наука,1986. — 260с.

20.Сакович В.А. Исследование операций (детерминированные методы и модели): Справ. пособие. — Минск: Высш. шк., 1985. — 256с.

21.Ховард Р.А. Динамическое программирование и марковские процессы/Пер. с англ. В.В. Быкова; Под ред. Н.П. Бусленко. — М.: Советское радио, 1964. — 192с.