Модификации транспортной задачи

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

К наиболее часто встречающимся ограничениям можно отнести:

1) запрет на поставку товара от поставщика к потребителю (блокировка)

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

2) обеспечение перевозки от поставщика к потребителю в точности единиц груза

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

3) от поставщика к потребителю должно быть завезено не менее единиц груза

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

4) от поставщика к потребителю должно быть завезено не более единиц груза

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

Примеры решения задач с ограничениями 1 – 4«вручную» приведены в [2].

При решении модифицированной транспортной задачи с использованием надстройки Excel «Поиск решений» первое ограничение также реализуется изменением в условии задачи: если критерием оптимальности являются минимальные затраты на все перевозки, то для обеспечения запрета тариф перевозки в соответствующей ячейке необходимо сделать сколь угодно большим числом (поставка становится дорогой, а, значит, невыгодной).Второе – четвертоеусловия приводят к введению вмодель задачи, а, значит, и в «Поиск решений», дополнительного ограничения для соответствующей ячейки[1], [5].

При составлении плана перевозок часто весьма важной задачей является экономия времени, даже в ущерб стоимости перевозки. Например, при транспортировке скоропортящихся продуктов необходима их доставка в пункты назначения за минимальное время. В период уборки урожая важно как можно быстрее доставить зерно на заготовительные пункты. К подобным задачам относятся переброска сил быстрого реагирования в районы стихийного бедствия, доставка медицинских грузов и другие аналогичные задачи. Модели подобных задач уже не являются задачами линейного программирования, так как их целевые функции не линейны. Рассмотрение таких задач выходит за рамки данного пособия. Алгоритм решения транспортной задачи по критерию времени приведен в учебнике [2].

Задача о назначениях

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

Исторически задача об оптимальном назначении была первой задачей линейного программирования. Ее решение впервые было предложено в 1931 г. венгерским математиком Эгервари.

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

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

то работник i назначен на операцию j;

если

то работник i не назначен на операцию j.

Тогда математически задачу о назначениях можно записать в виде

Получили транспортную задачу с единичными ресурсами и потребностями.Система (4) означает, что каждый исполнитель будет назначен на выполнение единственной работы, а система (5) – каждая работа будет выполняться единственным исполнителем. Решение задачи о назначениях можно получить методом потенциалов[2]или с использованием надстройки«Поиск решения» в Excel[3], [5].

Если количество работ и их исполнителей не совпадают, то задача будет открытой. Тогда одна из систем (4) или (5) будет системой неравенств знака « ».

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

Задачи для самостоятельного решения

Задание 1. Решить задачу целочисленного программирования:

а) графическим способом;

б) методом Гомори;

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

 

Варианты 1.1 – 1.10
1.1		1.2
1.3		1.4
1.5		1.6
1.7		1.8
1.9		1.10

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

Варианты 2.1 – 2.10

 

2.1. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4
А1
А2
А3
А4
Потребности

 

2.2. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

 

2.3. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4
А1
А2
А3
А4
Потребности

2.4. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

 

2.5. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4
А1
А2
А3
А4
Потребности

 

2.6. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

 

2.7. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

 

2.8. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

 

2.9. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

2.10. Транспортная таблица

Поставщики	Потребители	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
А4
Потребности

 

 

Задание 3. Сформулировать экономико-математическую модель транспортной задачи, найти оптимальный план перевозок груза от поставщиков к потребителям. Сделать выводы экономического характера. Решение «вручную» проверить средствами Excel.

Варианты 3.1 – 3.10

Задачи 3.1 – 3.5. Минимизировать расходы на доставку продукции со складов фирмы магазинам-заказчикам. Тарифы на перевозку единицы продукции, объёмы запасов продукции на складах и объёмы заказанной продукции представлены в матрицах перевозок.

 

3.1. Матрица перевозок

Магазин   Склад	Магазины-заказчики	Запасы на складе (ед. прод.)
«Анна»	«Вада»	«Ева»	«Алла»	«Мех»
«Таганка»
«ВВЦ»
«Щёлково»
«Коньково»
Объём заказа (ед. прод.)

 

 

3.2. Матрица перевозок

Магазин   Склад	«Росстек»	«Шер»	«Ткани»	«Мода»	«Вита»	Запасы на складе (ед.прод.)
Иваново
Москва
Новгород
Серпухов
Объём заказа (ед.прод.)

 

 

3.3. Матрица перевозок

Магазин   Склад	«Всё для дома»	«Здоровый сон»	«Фея»	«Ночное царство»	«Мех»	Запасы на складе (ед.прод.)
«Вороново»
«Фили»
«Беляево»
«Выхино»
Объём заказа (ед.прод.)

 

 

3.4. Матрица перевозок

Магазин   Склад	ВДНХ	Юго- Западная	Фили	Арбатская	Сокольники	Запасы на складе (ед.прод.)
Пролетарская
Митино
Строгино
Объём заказа (ед.прод.)

 

 

3.5. Матрица перевозок

Магазин   Склад	Тверь	Рязань	Тула	Чехов	Запасы на складе (ед.прод.)
Москва
Санкт-Петербург
Саратов
Самара
Объём заказа (ед.прод.)

 

Задачи 3.6 – 3.10. Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ. Имеются экономические оценки транспортных затрат (в у.е.) на перевозку 1тонны песка с карьеров на ремонтные участки.Числовые данные для решения содержатся ниже в матрицах планирования (повариантам).

Требуется:

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

2) Что произойдет с оптимальным планом, если изменятся условия перевозок:

а) появится запрет на перевозки от первого карьера до второго участка работ?

б) от второго карьера до третьего участка работ объем перевозок будет не менее (не более, ровно)3 т?

 

3.6. Матрица планирования:

Участки работ Карьеры	В1	В2	В3	В4	В5	Предложение
А1
А2
А3
Потребности

3.7. Матрица планирования:

Участки работ Карьеры	В1	В2	В3	В4	В5	Предложение
А1
А2
А3
Потребности

3.8. Матрица планирования:

Участки работ Карьеры	В1	В2	В3	В4	В5	Предложение
А1
А2
А3
Потребности

3.9. Матрица планирования:

Участки работ Карьеры	В1	В2	В3	В4	В5	Предложение
А1
А2
А3
Потребности

3.10. Матрица планирования:

Участки работ Карьеры	В1	В2	В3	В4	В5	Предложение
А1
А2
А3
Потребности

Задание 4. Сформулировать экономико-математическую модель дискретнойзадачи линейного программирования, найти ее оптимальный план. Сделать выводы экономического характера. При решении задачи воспользоваться средствами Excel.

Варианты 4.1 – 4.10

4.1.Компания «Корвет» производит программное обеспечение на CD-ROM.Компания оценивает возможность развития шести новых программных приложений. В таблице представлена информация о затратах и ожидаемой чистой прибыли от продажи приложений (в тыс. долл.).

 

Приложение	Затраты на развитие	Число программистов	Чистая прибыль
П1
П2
П3
П4
П5
П6
Ресурсы

 

У «Корвета» 60 программистов. На развитие новых программных приложений фирма может выделить 3, 5 млн долл.

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

1) ожидается, что клиенты, заинтересованные в приложении П4, будут заинтересованы также в приложении П5 и наоборот. Таким образом, эти приложения должны либо вместе развиваться, либо вместе не развиваться;

2) развитие приложения П1 имеет смысл только при наличии приложения П2. Таким образом, если развивается приложение П1, должно развиваться и приложение П2, но приложение П2 может развиваться и без приложения П1;

3) развиваться может только одно из приложений П3 и П6;

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

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

 

 

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

Ожидаемые затраты на реализацию каждого проекта и доход от них приведены в таблице.

Проект	Затраты на весь проект	Доход от всего проекта
1 год	2 год	3 год	4 год
	10, 5	14, 4	2, 2	2, 4	32, 4
	8, 3	12, 6	9, 5	3, 1	35, 8
	10, 2	14, 2	5, 6	4, 2	17, 75
	7, 2	10, 5	7, 5		14, 8
	12, 3	10, 1	8, 3	6, 3	18, 2
	9, 2	7, 8	6, 9	5, 1	12, 35
Возможное вложение (в тыс. долл.)

 

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

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

 

 

Сырье	Нормы затрат	Наличие, кг
Хлеб «Бородинский»	Хлеб «Жито»	Батон «Чайный»	Батон «Городской»
Мука пшеничная	0, 2	0, 15	0, 4	0, 35
Мука ржаная	0, 25	0, 3	-	-
Яйцо	0, 02	0, 025	0, 04	0, 035
Масло	0, 01	0, 03	0, 1	0, 15
Дрожжи	0, 005	0, 005	0, 01	0, 01
Вес изделия	0, 65	0, 85	0, 7	0, 6
Стоимость одного изделия

 

После проведения маркетинговых исследований установлено, что ежедневный спрос на «Бородинский» хлеб колеблется в пределах от 150 до 300 кг; спрос на хлеб «Жито» меняется соответственно от 300 до 450 кг; на батон «Чайный» – от 200 до 300 кг; на батон «Городской» – от 200 до 400 кг. Определить оптимальный ежедневный объем выпускаемой хлебобулочной продукции, обеспечивающий максимальную ее стоимость.

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

 

Период	Программные продукты	Ресурс фирмы
А	Б	В	Г	Д
1 кв.
2 кв.
3 кв.			-
4 кв.			-		-
Прибыль

 

4.5. Управляющему банком предложены четыре проекта, претендующие на получение кредита в банке. Ресурс банка в каждом периоде, потребности проектов и прибыль по ним приведены в таблице (в усл. ед.):

 

Проект	Потребности проектов в объемах кредитов	Прибыль
Период 1	Период 2	Период 3	Период 4
А
Б
В
Г
Ресурс банка

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

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

 

Продавец	Объемы продаж по торговым точкам, USD/тыс.шт.
I	II	III	IV	V	VI
A				-
B
C
D
E
F

Назначение первого продавца на четвертую торговую точкунедопустимо по медицинским показаниям, поэтому в матрице объемов продаж проставлен запрет – «-».

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

 

 

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

Продавец	Объемы продаж по торговым точкам, USD/тыс.шт.
I	II	III	IV	V	VI
A
B
C
D
E

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

 

 

4.8. Мастер должен назначить на 10 типовых операций 12 рабочих. Данные о времени, которое затрачивают рабочие на выполнение каждой операции, приведены в матрице эффективностей назначений:

Операции Рабочие	О1	О2	О3	О4	О5	О6	О7	О8	О9	О10
Р1
Р2
Р3			-
Р4			-
Р5			-
Р6							-
Р7
Р8
Р9
Р10
Р11
Р12

 

В матрице эффективностей назначений проставлен запрет «-», если рабочий не может выполнять соответствующую операцию.

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

 

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

 

Время выполнения, час. Работник	Работа 1	Работа 2	Работа 3	Работа 4	Работа 5
Р1
Р2
Р3
Р4
Р5

 

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

2) Предприятие «Смена» может принять на работу еще одного рабочего по совместительству, который выполняет каждую работу в течение следующего времени:

 

Время выполнения, час. Работник- совместитель	Работа 1	Работа 2	Работа 3	Работа 4	Работа 5
Р6

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

 

4.10. Фирма получила заказы на выполнение ремонтных работ на пяти объектах (евроремонт пяти квартир). Для выполнения этих заказов фирма располагает шестью бригадами, каждая из этих бригад выполняет один заказ «под ключ». Ниже в таблице приведены оценки времени (в днях), необходимого бригадам для выполнения всех работ и сдачи объектов заказчикам (исходя из состава и квалификации работников бригады).Оценки даны бригадирами и опыт работы их в фирме дает основания руководству доверять им.

 

Время выполнения, чел.-дни Бригада	Объект 1	Объект 2	Объект 3	Объект 4	Объект 5
Р1
Р2
Р3
Р4
Р5
Р6

 

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

⇐ Предыдущая123456789Следующая ⇒

Поделиться:

Популярное:

1. I I. Цели, задачи, результаты выполнения индивидуального проекта
2. II. Основные задачи управления персоналом.
3. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
4. II. Цели, задачи и предмет деятельности
5. III. Задачи, решаемые организацией с помощью ИСУ и ИТУ.
6. III. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ РАЙОННОЙ ОРГАНИЗАЦИИ ПРОФСОЮЗА
7. III. Экономико-управленческие задачи производственной практики
8. А. П. Петрова. «Сценическая речь» - Пути воплощения сверхзадачи
9. Анализ использования основных фондов: задачи, объекты, этапы, источники информации, основные показатели.
10. Анализ финансового состояния организации: задачи, методы, виды, последовательность, информационная база.
11. Анализ финансовых результатов: задачи, объекты, этапы, источники информации, основные показатели.
12. Аналитические возможности, задачи и основные направления анализа СНС