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

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

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

и условиях

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

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

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

Имеется

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

Назначим следующие стоимости перевозок

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

при

при

при

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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