Выбор исследование и описание предметной области
ПРАКТИЧЕСКАЯ РАБОТА № 4.
Составить развозочный маршрут по критерию минимального пробега автомобиля. Автомобиль отправляется из пункта А и после объезда пунктов Б, В, Г, Д, Е, Ж возвращается в пункт А.
Рис. 4.1 – Технологические требования к созданию информационного обеспечения по формированию развозочного (сборочного) маршрута.
Таблица 4.1 – Исходные данные для выполнения работы №4
Вариант | Координаты пунктов | ||||||
А | Б | В | Г | Д | Е | Ж | |
1; 1 | 3; 5 | 3; 3 | 5; 2 | 9; 7 | 7; 3 | 5; 5 | |
4; 1 | 3; 5 | 6; 3 | 2; 2 | 1; 7 | 7; 4 | 3; 5 | |
3; 5 | 1; 2 | 5; 3 | 3; 9 | 3; 3 | 7; 3 | 8; 2 | |
2; 2 | 1; 7 | 7; 4 | 3; 5 | 3; 9 | 1; 2 | 5; 3 | |
2; 4 | 1; 1 | 3; 5 | 5; 3 | 3; 9 | 1; 3 | 5; 4 | |
1; 7 | 5; 3 | 3; 5 | 3; 9 | 1; 2 | 5; 3 | 3; 3 | |
3; 3 | 5; 2 | 9; 7 | 4; 1 | 6; 3 | 1; 1 | 3; 5 | |
6; 3 | 2; 2 | 1; 7 | 7; 4 | 1; 1 | 4; 1 | 3; 5 | |
5; 3 | 3; 9 | 3; 3 | 7; 4 | 1; 1 | 3; 5 | 1; 2 | |
1; 4 | 7; 1 | 1; 5 | 7; 4 | 3; 5 | 2; 2 | 1; 7 | |
1; 8 | 3; 5 | 5; 3 | 7; 3 | 8; 2 | 2; 4 | 1; 1 | |
1; 3 | 3; 5 | 6; 9 | 3; 2 | 5; 9 | 5; 7 | 5; 3 | |
9; 7 | 7; 3 | 5; 5 | 1; 1 | 3; 5 | 3; 3 | 5; 2 | |
1; 7 | 7; 4 | 3; 5 | 4; 1 | 3; 5 | 6; 3 | 2; 2 | |
3; 3 | 7; 3 | 8; 2 | 3; 5 | 1; 2 | 5; 3 | 3; 9 | |
3; 9 | 1; 2 | 5; 3 | 2; 2 | 1; 7 | 7; 4 | 3; 5 | |
3; 9 | 1; 3 | 5; 4 | 2; 4 | 1; 1 | 3; 5 | 5; 3 | |
1; 2 | 5; 3 | 3; 3 | 1; 7 | 5; 3 | 3; 5 | 3; 9 | |
6; 3 | 1; 1 | 3; 5 | 3; 3 | 5; 2 | 9; 7 | 4; 1 | |
3; 7 | 7; 8 | 4; 1 | 6; 3 | 2; 2 | 1; 7 | 7; 4 |
Методические указания к заданию № 4
Данная задача носит название «задача «коммивояжера».
Она формулируется следующим образом: имеются пунктов с заданными расстояниями между i-м и k-м пунктами. Составить оптимальный маршрут из условия минимизации суммарного пробега для машины, выходящей из «нулевого» пункта, которая должна побывать в каждом пункте по одному и только одному разу и вернуться в «нулевой» пункт.
Решение. Введем n2 альтернативных переменных xik, принимающих значение 0, если переезд из i-го пункта в k-й не входит в маршрут, и 1 в противоположном случае. Условия прибытия машины в каждый пункт и выезда из каждого пункта только по одному разу могут быть выражены равенствами
(4.1)
Однако необходимо обеспечить «непрерывность» маршрута, т.е. чтобы набор «звеньев» (i,k), для которых xik =1 (т.е. звеньев, входящих в маршрут) образовал единую цепочку (например, при n=7 цепочка (0,1)-(1,5)-(5,3)-(3,7)-(7,4)-(4,2)-(2,6)-(6,0), а не состоял бы из отдельных не связанных цепочек (например, (0,1)-(1,5)-(5,0) и (2,7)-(7,6)-(6,4)-(4,3)-(3,2)]. Это условие можно обеспечить введением дополнительных n переменных и дополнительных n2 ограничений
(4.2)
Действительно, пусть маршрут включает несколько цепочек. Тогда существует цепочка, начинающаяся и заканчивающаяся в «нулевом» пункте, но охватывающая n1 звеньев, где n1<n. Просуммировав неравенства вдоль такой цепочки (т.е. при xik=1), получим бессмысленное неравенство n1∙n ≤ n1∙(n-1) (все ui и uk при суммировании взаимно уничтожаются).
Суммарная длина пробега машины z, которую необходимо минимизировать, запишется в виде
(4.3)
В результате приходим к следующей модели частично целочисленной задачи: минимизировать z при условиях (4.1), (4.2), условиях неотрицательности и и целочисленности всех переменных xik.
ПРАКТИЧЕСКАЯ РАБОТА № 5.
Из пункта А в пункт Б и обратно отправляются 4 поезда согласно расписания: из А в Б – 9.00, 12.00, 16.00 и 20.00; из Б в А - 10.00 14.00, 18.00 и 22.00. Время в пути одинаково и равно t ч. Локомотивы, ведущие поезда, совершают в сутки два рейса - один из пункта приписки, а второй - обратно с ближайшим очередным рейсом. Найти оптимальное, прикрепление локомотивов за пунктами А и Б при котором достигается минимальный простои локомотивов.
Таблица 5.1 – Исходные данные для выполнения работы №5
№ варианта | ||||||||||
t | 0,5 | 1,0 | 1,5 | 2,0 | 2,5 | 3,0 | 3,5 | 4,0 | 4,5 | 5,0 |
№ варианта | ||||||||||
t | 5,5 | 6,0 | 6,5 | 7,0 | 7,5 | 8,0 | 8,5 | 9,0 | 9,5 | 10,0 |
Методические указания к заданию № 5
Отправляется n поездов со станции А (i=0, 1, … n) и m поездов со станции Б (j=0, 1, … m) с заданным временем движения по перегону τ. Определить оптимальное прикрепление локомотивов за станциями А и Б, при котором достигается их минимальный пробег.
Решение. Определим время простоя локомотивов, отправляющихся со одной станции в i-е время на другую станцию и в k-е время в обратном направлении по всем возможным вариантам прикрепления. Время простоя локомотивов можно определить равенствами:
со станции А: (5.1)
со станции Б: (5.2)
Введем альтернативных переменных и , принимающих значение 0, если локомотив со одной станции на другую отправляется в i-е время и не отправляется в k-е время в обратном направлении, и 1 в противоположном случае. Условия прибытия и дальнейшее отправление по каждому времени могут быть выражены равенствами:
для пункта А: , где (5.3)
для пункта Б: , где (5.4)
Суммарный простой локомотивов , который необходимо минимизировать, запишется в виде:
(5.5)
В результате приходим к следующей модели частично целочисленной задачи: минимизировать при условиях (5.3) и (5.4) и условиях двоичности всех переменных и .
ПРАКТИЧЕСКАЯ РАБОТА № 6.
Для обеспечения перевозок требуется по дням недели: 50, 40, 70, 60, 80, 40, 50 автомобилей. Машина после поездки проходит профилактический ремонт в течение двух дней при затратах С1 грн. (при срочном ремонте – 1 день и С2 грн.). Кроме того можно использовать автомобили, сняв их с другого участка, что приведет к потерям С3=500 грн. на машину в день. Определить оптимальную недельную программу подготовки машин, минимизирующую суммарные затраты автобазы.
Таблица 6.1 – Исходные данные для выполнения работы №6
№ варианта | ||||||||||
С1 | ||||||||||
С2 |
№ варианта | ||||||||||
С1 | ||||||||||
С2 |
Методические указания к заданию № 6
Для обеспечения перевозок требуется по дням недели автомобилей. Автомобили после поездки проходят профилактический ремонт в течение двух дней при затратах С1 грн. (при срочном ремонте автомобили – 1 день и С2 грн.). Кроме того можно использовать автомобили , сняв их с другого участка, что приведет к потерям С3 грн. на машину в день. Определить оптимальную недельную программу подготовки автомобилей, минимизирующую суммарные затраты автобазы.
Решение. Определим возможную программу подготовки автомобилей на каждый день недели:
- понедельник: (6.1)
- вторник: (6.2)
- среда: (6.3)
- четверг: (6.4)
- пятница: (6.5)
- суббота: (6.6)
- воскресенье: (6.7)
Суммарные затраты автобазы , которые необходимо минимизировать, запишутся в виде:
(6.8)
В результате приходим к следующей модели частично целочисленной задачи: минимизировать при условии неотрицательности всех переменных , и и равенства возможной программы и требуемой.
ПРАКТИЧЕСКАЯ РАБОТА №7
В задаче требуется, исходя из объема работы абонентского пункта, выполнить расчет характеристик информационных потоков и рассчитать необходимое количество устройств сбора и передачи информации, для чего:
- построить ступенчатые диаграммы зависимости интенсивности потока сообщений каждого типа от часа суток;
- определить час наибольшей нагрузки (ЧНН),
- считая, что информация должна оперативно передаваться по каналам связи в ЭВМ, определить необходимое число устройств сбора и передачи информации.
Обозначим сообщения разных типов (телеграмма – натурный лист, сообщения о приеме, отправлении поездов и др.) следующим образом: С1, С2, С3 и т.д. По количеству сообщений, подготавливаемых абонентским пунктом, определены средние значения числа сообщений типа С1j, С2j, С3j, передаваемые в течение j-го часа (j = 1...24), которые приведены в табл.7.3 задания.
Выбор варианта исходных данных производится по табл. 7.1 и 7.2. Исходные данные приведены в табл. 7.3 и 7.4.
Таблица 7.1 – Порядковые номера сообщений каждого типа (С1, С2, С3), поступающих на абонентский пункт
Начальная буква фамилии студента | Последняя цифра шифра студента (номер зачетки) | |||||||||
А–Б | 1,2,3 | 2,3,4 | 3,4,5 | 4,5,6 | 5,6,7 | 6,7,8 | 7,8,9 | 8,9,10 | 9,10,1 | 10,1,2 |
В–Д | 10,4,2 | 1,5,3 | 2,6,4 | 3,7,5 | 4,8,6 | 5,9,7 | 6,10,8 | 7,1,9 | 8,2,10 | 9,3,1 |
Е–З | 9,2,8 | 10,3,9 | 1,4,10 | 2,5,1 | 3,6,2 | 4,7,3 | 5,8,4 | 6,9,5 | 7,10,6 | 8,1,7 |
И–К | 8,10,6 | 9,1,7 | 10,2,8 | 1,3,9 | 2,4,10 | 3,5,1 | 4,6,2 | 5,7,3 | 6,8,4 | 7,9,5 |
Л–Н | 7,8,3 | 8,9,4 | 9,10,5 | 10,1,6 | 1,2,7 | 2,3,8 | 3,4,9 | 4,5,10 | 5,6,1 | 6,7,2 |
О–П | 6,5,9 | 7,6,10 | 8,7,1 | 9,8,2 | 10,9,3 | 1,10,4 | 2,1,5 | 3,2,6 | 4,3,7 | 5,4,8 |
Р–У | 5,3,6 | 6,4,7 | 7,5,8 | 8,6,9 | 9,7,10 | 10,8,1 | 1,9,2 | 2,10,3 | 3,1,4 | 4,2,5 |
Ф–Ш | 4,1,3 | 5,2,4 | 6,3,5 | 7,4,6 | 8,5,7 | 9,6,8 | 10,7,9 | 1,8,10 | 2,9,1 | 3,10,2 |
Щ–Э | 3,9,10 | 4,10,1 | 5,1,2 | 6,2,3 | 7,3,4 | 8,4,5 | 9,5,6 | 10,6,7 | 1,7,8 | 2,8,9 |
Ю–Я | 2,7,1 | 3,8,2 | 4,9,3 | 5,10,4 | 6,1,5 | 7,2,6 | 8,3,7 | 9,4,8 | 10,5,9 | 1,6,10 |
Таблица 7.2 – Варианты исходных данных о количестве символов в сообщениях, поступающих на абонентский пункт
Начальная буква фамилии студента | Последняя цифра шифра студента (номер зачетки) | |||||||||
А–Б | ||||||||||
В–Д | ||||||||||
Е–З | ||||||||||
И–К | ||||||||||
Л–Н | ||||||||||
О–П | ||||||||||
Р–У | ||||||||||
Ф–Ш | ||||||||||
Щ–Э | ||||||||||
Ю–Я |
При оформлении задачи студент обязан представить в записке принятые по своему варианту исходные данные в виде таблиц, а также расчеты по определению объемов информации, передаваемой в течении каждого часа.
Таблица 7.3 – Средние значения числа сообщений каждого типа (С1, С2, С3) поступающих на абонентский пункт в течение часа j ( j=1,…,24)
Номер сообщения | Час суток j | |||||||||||||||||||||||
I | ||||||||||||||||||||||||
I | ||||||||||||||||||||||||
Э | ||||||||||||||||||||||||
I | ||||||||||||||||||||||||
I | ||||||||||||||||||||||||
I |
Таблица 7.4 – Средняя длина сообщений каждого типа (С1, С2, С3) в символах
№ варианта | С1 | С2 | С3 | № варианта | С1 | С2 | С3 |
Методические указания к решению задачи №7
Объемы информации являются исходными данными для расчета комплекса технических средств, а также необходимого числа работников, участвующих в сборе, подготовке и передаче информации.
Информационные потоки существуют параллельно материальным потокам, а следовательно, и параметры их определяется объемами и динамикой эксплуатационных процессов и присущей ей сезонной, суточной и внутрисуточной неравномерностью. Для определения внутрисуточной неравномерности информационного потока фиксируется число документов (сообщений) каждого, типа, подготавливаемых и передаваемых на абонентский пункт за определенный интервал времени (обычно один час) в любой день наблюдения.
Обозначим это число документов (сообщений) через (см.табл.7.5), где i=1...n – тип документа, n – общее число типов документов (сообщений); j=1...24 – номер часа в течение дня наблюдения; k=1,...N – номер дня наблюдения, N – общее число дней наблюдения (в задаче принимаем N=1). Составив табл.7.5 определим:
– общее число сообщений i-го типа, поступивших в течение k-го дня наблюдения;
(7.1)
– среднее число сообщений i-го типа, поступающих в течение j-го часа суток (интенсивность потока сообщений i-го типа).
(7.2)
Вычисленные значения позволяют построить ступенчатую функцию зависимости интенсивности потока сообщений i-го типа от часа суток и найти интервал, на котором интенсивность информационного потока имеет максимальное значение.
Если обозначить среднее число символов, входящие в сообщение Vi, то средний объем Vj, информации в символах, содержащихся во всех сообщениях, поступающих в течение j-го часа суток.
(7.3)
Таблица 7.5 – Определение внутрисуточной неравномерности потока информации
Дни наблюдений | Число сообщений по часам наблюдений | Общее число сообщений за день | |||||
... | j | ... | |||||
... | ... | ||||||
... | ... | ||||||
. . . | . . . | . . . | . . . | . . . | . . . | . . . | . . . |
N | ... | ... | |||||
Среднее число сообщений за j-й час дня | ... | ... |
Для оценки внутрисуточной неравномерности информационного потока вводят коэффициент концентрации Sk, показывающий отношение объема информации Vmax, поступающей в час наибольшей загрузки (ЧНН), к общему суточному объему информации V, т.е.
(7.4)
где (7.5)
(7.6)
В большинстве АСУ коэффициент концентрации равен в среднем 10-15%.
Расчет необходимого числа устройств подготовки информации на данном абонентском пункте выполняется для часа наибольшей нагрузки. При этом, учитывая перерывы в работе и выполнение оператором вспомогательных функций по контролю информация, необходимое число устройств сбора информации определится из формулы:
(7.7)
где Sn – коэффициент перерывов в работе оператора, учитывающий выполнение технологических процессов обслуживания устройств (включение, проверка, заправка носителя информации и т.п.), равен доле времени, непосредственно используемой для полезной (основной) работы (принимается Sn=0,75);
SB – коэффициент, учитывающий затраты времени оператора на выполнение функций контроля и исправления передаваемой информации. Так как при передаче оперативной информации исправление ошибок происходит в режиме реального времени, будем считать SB=0,4;
В – скорость работы оператора на клавиатуре устройства (символов/мин). Скорость работы оператора зависит от типа клавиатуры (цифровая или алфавитно-цифровая), квалификации оператора и ряда других факторов. При проведении расчетов можно считать, что в средней В=100 символов/мин.
ПРАКТИЧЕСКАЯ РАБОТА № 10.
Проектирование баз данных
Выбор сущностей
Сущность – это собирательное понятие, некоторая абстракция каких-либо реально существующих объектов (процессов, явлений или событий). Это могут быть как материальные, так и нематериальные объекты. Признаком помогающим выбрать сущность, является то, что это как правило имя существительное. Тип сущности определяет множество однородных объектов с общими свойствами или характеристиками. Экземпляр сущности определяет один конкретный объект. Сущность имеет графическое обозначение которое может иметь вид:
Для выбора сущностей необходимо определить главные объекты предметной области. В пояснительной записке должен быть приведен список сущностей.
Пример: В нашей задаче выбираем следующие сущности:
Определение атрибутов
У каждой сущности есть набор некоторых характеристик. Атрибут – это поименованная характеристика сущности, принимающая значения из множества значений. Атрибуты часто бывают прилагательными или числительными. Атрибут имеет обозначение в виде прямоугольника с круглыми боками:
Атрибуты сущностей определяются по описанию в постановке задачи и приводятся в виде показанной в примере диаграммы.
Пример: Приведем диаграммы для двух сущностей:
Описание связей
Между объектами имеются различные связи. Они обычно обозначаются глаголами. Например, между сущностями кафедра и преподаватель в качестве связи выступает глагол "работает на"; между преподавателем и аудиторией связь - "проводит занятия в". Связи обозначаются в виде ромбов:
Пример: Изобразим связь "кафедра - преподаватель"
Связи могут быть бинарными между двумя сущностями, как приведено выше, тройными и многосвязными.
Пример:
Связи сами могут иметь собственные атрибуты.
Пример: Те же занятия проводятся в определенный день недели и время:
В зависимости от связи, у одних сущностей каждый экземпляр сущности обязательно должен участвовать в связи, а у других нет. Если участие обязательно то связь обозначается точкой, помещенной внутрь прямоугольника:
Если связь не обязательна, то точка ставится снаружи прямоугольника:
Пример: Между сущностями "преподаватель" и "кафедра" есть связь, которая заключается в том, что один из преподавателей является заведующим кафедрой. Но на каждой кафедре есть заведующий кафедрой, а заведующим кафедрой является не каждый преподаватель. Поэтому с учетом обязательности участия связь будет иметь вид:
Связи различаются степенью связи. Степень указывает сколько экземляров одной сущности может быть связано с одним экземпляром другой сущности. Простейшей является связь 1:1. При ней один экземпляр одной сущности может быть связан только с одним экземпляром другой и наоборот.
Пример: На каждой кафедре может быть только один заведующий и один преподаватель не может быть заведующим больше чем на одной кафедре. Тогда связь обозначается следующим образом:
Более сложной является связь 1:М или М:1. При ней один экземпляр одной сущности может быть связан с несколькими экземплярами другой, а один экземпляр другой только с одним экземпляром первой.
Пример: Рассмотрим связь "преподаватель работает на кафедре". На одной кафедре может работать несколько преподавателей, но каждый преподаватель работает только на одной кафедре. "Кафедра" называется односвязной сущностью, а "преподаватель" М-связной. Тогда связь обозначается следующим образом:
Наиболее сложной является связь М:N. При ней один экземпляр одной сущности может быть связан с несколькими экземплярами другой, и наоборот.
Пример: Рассмотрим связь "преподаватель читает предмет". Один преподаватель может читать несколько предметов и один предмет могут читать несколько преподавателей. Обе сущности будут М-связными. Тогда связь обозначается следующим образом:
В пояснительной записке необходимо привести все связи с указанием их атрибутов, если они есть, обязательности участия и степени связи, как в последних трех примерах.
Выбор ключевых выражений
Всегда должна быть возможность отличить один экземпляр сущности от другой. Для этого используется группа атрибутов, сочетания которых не повторяться. Такой набор называется ключ или ключевое выражение. Такое условие не всегда можно выполнить или потребуется использовать все атрибуты. Это неудобно, так как увеличивается объем данных и время сравнения. Поэтому обычно к каждой сущности добавляется еще один дополнительный фиктивный атрибут, который является условным кодом или номером каждого экземпляра сущности. Но может быть использован и один небольшой по размеру атрибут.
Пример: Каждый преподаватель и студент в университете имеет свой уникальный табельный номер. Каждая кафедра и студенческая группа имеет свой цифровой шифр. Так в рассмотренном ранее примере для сущности кафедра необходимо добавить код для ключевого выражения
В пояснительной записке необходимо указать какие ключевые выражения используются для каждой сущности.
Реализация на ЭВМ
Информационная система строится на ЭВМ с применением СУБД Access из пакета Microsoft Office. В ней создаются все необходимые таблицы и в них заносится информация. При этом объем информации должен составлять 15..20 записей для таблиц сущностей и 30..40 записей для таблиц связей.
С помощью мастера подстановок и схемы данных между таблицами должны быть установлены необходимые связи.
К таблицам необходимо выполнить 4 запроса. Два простых запроса выполняются для отдельных таблиц. А два более сложных для связанных между собой таблиц. Необходимо по литературе ознакомиться со всеми видами запросов такими как: запрос с параметром, запрос с вычисляемым полем, запрос с группировкой, запрос с условиями, перекрестный запрос и другие.
Для каждой таблицы необходимо построить по одной форме ввода информации. Для пары таблиц, связанных со степенью связи один ко многим нужно построить одну форму содержащую главную и подчиненную формы.
Для любых таблиц на выбор нужно построить два отчета. Один простой и один с промежуточными итогами.
Приложение 2
Пример реализации математического аппарата практической работы №4 в программной среде EXCEL
Приложение 3
Пример реализации математического аппарата практической работы №5 в программной среде EXCEL
Приложение 4
Пример реализации математического аппарата практической работы №6 в программной среде EXCEL
ПРАКТИЧЕСКАЯ РАБОТА № 4.
Составить развозочный маршрут по критерию минимального пробега автомобиля. Автомобиль отправляется из пункта А и после объезда пунктов Б, В, Г, Д, Е, Ж возвращается в пункт А.
Рис. 4.1 – Технологические требования к созданию информационного обеспечения по формированию развозочного (сборочного) маршрута.
Таблица 4.1 – Исходные данные для выполнения работы №4
Вариант | Координаты пунктов | ||||||
А | Б | В | Г | Д | Е | Ж | |
1; 1 | 3; 5 | 3; 3 | 5; 2 | 9; 7 | 7; 3 | 5; 5 | |
4; 1 | 3; 5 | 6; 3 | 2; 2 | 1; 7 | 7; 4 | 3; 5 | |
3; 5 | 1; 2 | 5; 3 | 3; 9 | 3; 3 | 7; 3 | 8; 2 | |
2; 2 | 1; 7 | 7; 4 | 3; 5 | 3; 9 | 1; 2 | 5; 3 | |
2; 4 | 1; 1 | 3; 5 | 5; 3 | 3; 9 | 1; 3 | 5; 4 | |
1; 7 | 5; 3 | 3; 5 | 3; 9 | 1; 2 | 5; 3 | 3; 3 | |
3; 3 | 5; 2 | 9; 7 | 4; 1 | 6; 3 | 1; 1 | 3; 5 | |
6; 3 | 2; 2 | 1; 7 | 7; 4 | 1; 1 | 4; 1 | 3; 5 | |
5; 3 | 3; 9 | 3; 3 | 7; 4 | 1; 1 | 3; 5 | 1; 2 | |
1; 4 | 7; 1 | 1; 5 | 7; 4 | 3; 5 | 2; 2 | 1; 7 | |
1; 8 | 3; 5 | 5; 3 | 7; 3 | 8; 2 | 2; 4 | 1; 1 | |
1; 3 | 3; 5 | 6; 9 | 3; 2 | 5; 9 | 5; 7 | 5; 3 | |
9; 7 | 7; 3 | 5; 5 | 1; 1 | 3; 5 | 3; 3 | 5; 2 | |
1; 7 | 7; 4 | 3; 5 | 4; 1 | 3; 5 | 6; 3 | 2; 2 | |
3; 3 | 7; 3 | 8; 2 | 3; 5 | 1; 2 | 5; 3 | 3; 9 | |
3; 9 | 1; 2 | 5; 3 | 2; 2 | 1; 7 | 7; 4 | 3; 5 | |
3; 9 | 1; 3 | 5; 4 | 2; 4 | 1; 1 | 3; 5 | 5; 3 | |
1; 2 | 5; 3 | 3; 3 | 1; 7 | 5; 3 | 3; 5 | 3; 9 | |
6; 3 | 1; 1 | 3; 5 | 3; 3 | 5; 2 | 9; 7 | 4; 1 | |
3; 7 | 7; 8 | 4; 1 | 6; 3 | 2; 2 | 1; 7 | 7; 4 |
Методические указания к заданию № 4
Данная задача носит название «задача «коммивояжера».
Она формулируется следующим образом: имеются пунктов с заданными расстояниями между i-м и k-м пунктами. Составить оптимальный маршрут из условия минимизации суммарного пробега для машины, выходящей из «нулевого» пункта, которая должна побывать в каждом пункте по одному и только одному разу и вернуться в «нулевой» пункт.
Решение. Введем n2 альтернативных переменных xik, принимающих значение 0, если переезд из i-го пункта в k-й не входит в маршрут, и 1 в противоположном случае. Условия прибытия машины в каждый пункт и выезда из каждого пункта только по одному разу могут быть выражены равенствами
(4.1)
Однако необходимо обеспечить «непрерывность» маршрута, т.е. чтобы набор «звеньев» (i,k), для которых xik =1 (т.е. звеньев, входящих в маршрут) образовал единую цепочку (например, при n=7 цепочка (0,1)-(1,5)-(5,3)-(3,7)-(7,4)-(4,2)-(2,6)-(6,0), а не состоял бы из отдельных не связанных цепочек (например, (0,1)-(1,5)-(5,0) и (2,7)-(7,6)-(6,4)-(4,3)-(3,2)]. Это условие можно обеспечить введением дополнительных n переменных и дополнительных n2 ограничений
(4.2)
Действительно, пусть маршрут включает несколько цепочек. Тогда существует цепочка, начинающаяся и заканчивающаяся в «нулевом» пункте, но охватывающая n1 звеньев, где n1<n. Просуммировав неравенства вдоль такой цепочки (т.е. при xik=1), получим бессмысленное неравенство n1∙n ≤ n1∙(n-1) (все ui и uk при суммировании взаимно уничтожаются).
Суммарная длина пробега машины z, которую необходимо минимизировать, запишется в виде
(4.3)
В результате приходим к следующей модели частично целочисленной задачи: минимизировать z при условиях (4.1), (4.2), условиях неотрицательности и и целочисленности всех переменных xik.
ПРАКТИЧЕСКАЯ РАБОТА № 5.
Из пункта А в пункт Б и обратно отправляются 4 поезда согласно расписания: из А в Б – 9.00, 12.00, 16.00 и 20.00; из Б в А - 10.00 14.00, 18.00 и 22.00. Время в пути одинаково и равно t ч. Локомотивы, ведущие поезда, совершают в сутки два рейса - один из пункта приписки, а второй - обратно с ближайшим