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

Транспортная задача

На трех станциях отправления имеется соответственно 30, 50, и 20 ед. однородного груза, который нужно доставить в четыре пункта назначения согласно их потребностям. Эти данные, а также стоимость перевозки единицы груза от каждой станции отправления к каждому пункту назначения указаны в таблице. Составить план перевозок грузов, чтобы затраты на эти перевозки были минимальными.

Пункты отправления	Запасы груза	Пункты назначения




Потребности

Решение.

Этап 1.

Часто условие транспортной задачи оформляют матрицей:

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

1. «Составить план перевозок грузов» - значит определить сколько, от куда и куда надо перевезти груза, чтобы достичь поставленной цели - «затраты на эти перевозки были минимальными». Введем управляющие переменные: - количество груза, перевозимого из пункта в пункт ( ).

2. Стоимость этой перевозки составит . Тогда целевая функция - суммарные затраты, связанные с реализацией всего плана перевозок – запишется выражением:

в общем виде , где

в нашей задаче

3.Для построения системы ограничений проверим, является ли задача сбалансированной.

Суммарная мощность поставщиков

ед Суммарная мощность потребителей

Следовательно, условие сбалансированности не выполнено.

4. Запишем систему ограничений:

По потребителю: мощности поставщиков меньше мощности потребителей, следовательно, кто-то из потребителей получит груза меньше, чем его потребность .

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

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

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

;

Прямые ограничения .

Этап 2.

1. Подготовим форму для ввода исходных данных (Рис 15.),

В нашем примере матрица затрат по доставке груза с конкретной станции отправления каждому потребителю вводится в ячейки блока В3:E5. В ячейках В6:E6 указываются потребности в пунктах назначения , мощности поставщиков записаны в блоке F3:F5.

Рис. 15 Ввод исходных данных.

2. Зарезервируем изменяемые ячейки, в которых после решения задачи будет находиться оптимальный план перевозок . Размерность этого массива обязательно должна совпадать с размерностью матрицы затрат: выделим блок ячеек I3:L5 (можно ввести в эти ячейки «1» ) (рис. 16).

Рис 16. Создание формы для ввода условий задачи.

3. Введем зависимость для целевой функции (рис. 17). Оптимальное значение целевой функции будет помещено в ячейке В8:

· Курсор в ячейку В8 .

· Мастер функций fx / Математические / СУММПРОИЗВ (В3:E5; I3:L5)

Рис. 17 Ввод зависимости для целевой функции

4. Введем зависимости ограничений, стоящие в левых частях ограничений.

- вводим условия реализации мощностей поставщиков (рис 18.):

· Курсор в ячейку М3.

· Мастер функций fx / Математические / СУММ (I3:L3)

· Курсор в ячейку М3.

· Растянуть (копировать) ячейку М3 в ячейки М4 и М5.

Рис. 18. Ввод зависимостей ограничений по поставщикам.

- вводим зависимостей ограничений по потребителям (рис. 19):

· курсор в ячейку I6. ;

· Мастер функций fx / Математические / СУММ (I3:I5)

· Курсор в ячейку I6.

· Растянуть (копировать) ячейку I6 в ячейки J6, K6 и L6.

Рис. 19. Ввод зависимостей ограничений по потребителям.

На этом ввод зависимостей закончен.

Этап 3. Запуск программы Поиск решений

После выбора команд Поиск решения появится диалоговое окно Поиск решения.

· Назначение целевой ячейки: курсор в поле Установить целевую ячейку. . Левой кнопкой мыши щелкнуть на ячейке В8.

· Ввести направление целевой функции: минимальному значению.

· Ввести адреса искомых переменных: курсор в поле Изменяя ячейки. . Выделить мышью адреса ячеек I3:L5.

· Ввести ограничения:

o курсор в поле Ограничения . Выбрать режим Добавить .

o курсор в поле Ссылка на ячейку

o выбрать мышью ячейки I6:L6

o ввести знак ограничения <=

o курсор в правое окно Ограничение .

o указать мышью адреса В6:E6

o

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

Рис. 20. Введены все ограничения.

· Выбрать параметры модели: рис 4.

Этап 4. Выполнить.

На экране диалоговое окно Результат поиска решения (рис.18.) .

Рис.21. Решение найдено.

Найденный план перевозок означает, что общая стоимость перевозок составит 235 ден.ед., если

ед. груза перевести со станции 1 потребителю 3;

ед. груза перевести со станции 2 потребителю 1;

ед. груза перевести со станции 2 потребителю 3;

ед. груза перевести со станции 2 потребителю 4;

ед. груза перевести со станции 3 потребителю 2.

Неудовлетворены будут потребители и , т.к. они получат груза меньше, чем составляют их потребности. Так, например, потребность составляет 35 ед. груза (ячейка C6), а получит он только 20 ед. (ячейка J6).

Остальные потребители удовлетворены полностью.

Вопросы:

1. Сколько груза должно быть перевезено из А2 в П1?

2. С кем работает поставщик А2?

3. С кем работает потребитель П4?

4. Измените модель, добавив условие:

1. Потребности П2 обязательно должны быть удовлетворены. (F=265)

2. Запрещены перевозки в направлении А2 –П3.(F=245)

3. В направлении А3—П1 необходимо перевезти не менее 5 тонн.(F=250)

4. Возможности А3 стали равны 50; (F=290)

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

Известна матрица эффективности. Осуществить назначение продавцов по торговым точкам для достижения максимального объема продаж.

Прода- вец средний дневной объем продаж продуктов по торговым точкам, у.е.

-

(назначение продавца на торговую точку недопустимо по медицинским показаниям, т.е. в матрице эффективностей знаком «-» проставлен запрет назначений).

Решение.

Этап 1.

Построим математическую модель задачи о назначениях.

1. Введем управляющие переменные:

- факт назначения ресурса на работу :

, если кандидат назначен на работу ,

, если кандидат не назначен на работу .

2. Объем продаж -го продавца на -ой торговой точке равны , , .

Функция цели - объем продаж по всем продавцам и всем торговым точкам - определяется выражением:

, или

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

4. Построим систему ограничений.

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

или

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

, или

Добавим ограничение - двоичные переменные.

Кроме того, в задаче имеется дополнительное ограничение: запрет назначения продавца на торговую точку , которое реализуется ограничением

Этап 2.

1.Подготовим форму для ввода исходных данных (Рис. 22.).

В нашем примере матрица эффективности назначений продавцов по торговым точкам вводится в ячейки блока В3:E6.

Зарезервированы изменяемые ячейки H3:K6 - для создания матрицы назначений (размерность матрицы назначений должна совпадать с размерностью матрицы эффективности). В этих ячейках будут находиться оптимальные значения управляющих переменных .

Рис. 22. Создание формы для ввода условий задачи.

2. Введем зависимость для целевой функции (рис. 23).

Оптимальное значение целевой функции будет помещено в ячейке В8

· Курсор в ячейку В8 .

· Мастер функций fx / Математические / СУММПРОИЗВ (В3:E6; H3:K6)

Рис. 23 Ввод зависимости целевой функции

2. Введем зависимости ограничений (рис 24.).

- вводим условия по продавцам:

· курсор в ячейку L3. ;

Мастер функций fx / Математические / СУММ (H3:K3)

Скопировать ячейку L3 в L4, L5 и L6.

- вводим условия удовлетворения запросов по торговым точкам:

· курсор в ячейку Н7. ;

Мастер функций fx / Математические / СУММ(Н3:Н6);

Скопировать ячейку Н7 в I7, J7 и K7.

Рис 24. Ввод формул для вычисления левых частей ограничений.

Этап 3. Запуск программы Поиск решений

· Назначение целевой ячейки: курсор в поле Установить целевую ячейку. Левой кнопкой мыши щелкнуть на ячейке В8.

· Ввести направление целевой функции: максимальному значению.

· Ввести адреса искомых переменных: курсор в поле Изменяя ячейки. . Выделить мышью ячейки Н3:К6.

· Ввести ограничения:

o курсор в поле Ограничения . Выбрать режим Добавить .

o курсор в поле Ссылка на ячейку

o выбрать мышью ячейки в L3: L6

o ввести знак ограничения =

o курсор в правое окно Ограничение .

o Ввести 1

o Выбрать режим Добавить

o курсор в поле Ссылка на ячейку

o выбрать мышью ячейки в Н7: К7

o ввести знак ограничения =

o курсор в правое окно Ограничение .

o Ввести 1

o Добавим ограничение - двоичные переменные .

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

· Выбрать параметры модели: рис 4.

Этап 4. Выполнить (рис.25.).

На экране диалоговое окно Результат поиска решения.

Рис.25. Решение найдено.

Найденный план назначений означает, что суммарный объем продаж будет максимальным и составит 218у.е., если:

- продавец назначен на торговую точку ;

- продавец назначен на торговую точку ;

- продавец назначен на торговую точку ;

- продавец назначен на торговую точку .

Все ограничения при этом выполнены.

Вопросы:

Измените модель, добавив условие:

1. На третьей точке обязательно должен работать продавец П2.(F=173)

2. Запрещено назначение продавца П1 на торговую точку Т2.(F=218)

3. Измените модель при условии, что закрыли IV торговую точку. (F=173)

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

1) Продавец П1 обязательно должен быть назначен на какую-либо торговую точку.(F=173)

2) Продавец П1 обязательно должен быть назначен на 2 торговую точку.(F=169)

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

Задание 1.

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

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

К1

К2

К3 -

К4

Потребности

Составить оптимальный план перевозок, обеспечивающий минимальные транспортные расходы.

Ответ:

В1 В2 В3 В4

К1

К2

К3

К4

ФЦ=

Задание 2.

Эффективность работы продавцов (объем продаж) в различных торговых точках приведена в таблице:

Торговые точки продавец I II III IV

А

В

С

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

Ответ:

I II III IV

А

В

С

ФЦ=

Читайте также:
Русский классицизм в XIX веке: Художественная культура XIX в. развивалась под воздействием ...
Продление сроков использования СИЗ: Согласно пункта 22 приказа Минздравсоцразвития России от...
Понятие о дефектах. Виды дефектов и их характеристика: В процессе эксплуатации автомобилей происходит...
Роль языка в формировании личности: Это происходит потому, что любой современный язык – это сложное ...

Рекомендуемые страницы:

Поиск по сайту

©2015-2020 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-12 Нарушение авторских прав и Нарушение персональных данных