Постановка транспортной задачи. Л11

Фирма имеет 4 фабрики по производству электродов для ручной сварки и 5 центров распределения продукции. Фабрики располагаются в Мариуполе, Донском, Торезе, Киеве с производственными возможностями 200, 150, 225, 175 единиц продукции ежедневно. Распределительные центры располагаются в Мариуполе, Краматорске, Харькове, Виннице и Дружковке с потребностями 100, 200, 50, 250, 150 единиц продукции ежедневно, соответственно. Хранение на фабрике не поставленной в центр распределения единицы продукции обходится 5 грн в день, а штраф за просрочку поставки заказанный потребителем в центр распределения единицы продукции, но там не находящейся, равен 10 грн в день.

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

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

- в случае перепроизводства — фиктивный пункт распределения; стои­мость перевозок единицы продукции в этот фиктивный пункт полагается равной стоимости складирования, а объемы перевозок в этот пункт рав­ны объемам складирования

излишек продукции на фабриках;

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

Для решения данной задачи построим ее математическую модель. Неизвест­ными здесь являются объемы перевозок. Пусть x_ij — объем перевозок с i -й фабрики в j -й центр распределения. Функцией цели являются суммарные транспортные расходы, т. е.

,

где с_ij — стоимость перевозки единицы продукции с i -й фабрики в j-й центр распределения. Кроме того, неизвестные должны удовлетворять следующим ограничениям:

- неотрицательность объема перевозок;

- т. к. модель сбалансирована, то вся продукция должна быть вывезена с фабрик, и потребность всех центров распределения должна быть пол­ностью удовлетворена.

Таким образом, мы имеем следующую модель:

- минимизировать:

,

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

, ,

, ,

, ,

где a_i — — объем производства на i -й фабрике, b_j –спрос в j- м центре распределения.

8. Средство “Поиск решения” для решения оптимизационных задач л12

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

1. Введите в ячейки диапазона B3:F6 стоимости перевозок.

2. Отведите ячейки диапазона B8:F11 под значения неизвестных (объемов перевозок).

3. Введите в ячейки диапазона Н8:H11 объемы производства на фабриках.

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

5. В ячейку В16 введите функцию цели =СУММПРОИЗВ(ВЗ:F6;В8:F11)

6. В ячейки диапазонов G8:G11 введите формулы, вычисляющие объемы производства на фабриках, в ячейки диапазона B12:F12 объемы доставляемой продукции в пункты распределения. А именно:

Рис. 8.1 - Исходные данные транспортной задачи и заполненное диалоговое окно Поиск решения.

Ячейка Формула Ячейка Формула

G8 = СУММ (B8: F8) B12 = СУММ (B8: B11)

G9 = СУММ (B9: F9) C12 = СУММ (C8: C11)

G10 = СУММ (B10: F10) D12 = СУММ (D8: D11)

G11 = СУММ (B11: F11) E12 = СУММ (E8: E11)

F12 = СУММ (F8: F11)

7. Выберите команду Сервис | Поиск решения и заполните диалоговое окно Поиск решения, как показано на рис. 8.1. Окно Поиск решения имеет элементы, перечисленные в табл. 8.1.

Примечание: Поиск решения является одной из надстроек (add-ins) MS Excel. Если в меню Сервис отсутствует команда Поиск решения, для ее установки необходимо выбрать команду Сервис / Надстройки. На экране отобразится диалоговое ок­но Надстройки. В списке Список надстроек выберите Поиск решения и на­жмите кнопку ОК. Если в этом списке нет средства Поиск решения, то его надо сначала инсталлировать с диска Microsoft Office. Для этого достаточно повтор­но запустить программу установки Microsoft Office и убедиться, что выбран па­раметр установки надстройки Поиск решения.

Таблица 8.1 - Элементы окна Поиск решения

Элемент	Описание
Поле Установить целевую ячейку	Приводится ссылка на ячейку с функцией, максимум, минимум или значением которой Поиск решениябудет искать, изменяя значения параметров так, чтобы они удовлетворяли налагаемым на них ограничениям. В примере с задачей о красках в поле Установить целевую ячейкувводим B16
Группа Равной	Тип взаимосвязи между решением и целевой ячейкой устанав­ливается путем выбора переключателя в группе Равной.Для отыскания максимального значения целевой функции выбира­ется переключатель максимальному значению,минимально­го переключатель минимальному значению.Если отыски­ваются значения переменных, для которых значение функции из целевой ячейки равно установленному в поле группы Равнойзначению, то выбирается переключатель значению.В транспортной задаче выберите переключатель минимальному значению,т.к находим план перевозок с минимальными расходами.
Поле Изменяя ячейки	Приводится ссылка на диапазон ячеек или группу диапазонов ячеек, отведенных под неизвестные. Значения в этих ячейках должны изменяться в процессе поиска решения задачи, так чтобы найти решение, удовлетворяющее заданным ограничениям. В нашем случае введем в поле Изменяя ячейкидиапазон B8:F11.

Список Ограничения

Допускаются ограничения в виде равенств, неравенств, требования того, что неизвестные могут принимать только целые значения, либо только значения 0 или 1. Ограничения добавляются по одному за раз и отображаются в окне Добавление ограничения,вызываемого нажатием кнопки Добавить(рис. 2.2). • В поле Ссылка на ячейкувведите левую часть ограничений — B8:F11, вполе Ограничение— правую часть, в нашем случае — 0. Раскрывающийся список позволяет задать тип соотношения между левой и правой частями ограничения. В нашем случае выберите соотношение >=. Таким образом, требование не отрицательности переменных задано. • Нажмите кнопку Добавитьи с помощью окна Добавление ограничениявведите вторую группу ограничений, налагаемых на переменные Н8:H11= G8:G11; В13:F13= B12:F12. • Нажмите кнопку ОК для завершения ввода ограничений. На экране опять отобразится окно Поиск решения,но теперь уже заполненное

Рис. 8.2 – Окно Добавление ограничения

1. Нажмите кнопку Параметры. На экране отобразится диалоговое окно Параметры поиска решения (рис. 8.3). В диалоговом окне Параметры по­иска решения можно

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

Рис. 8.3 – Окно Параметры поиска решения

Таблица 8.2 - Элементы окна Параметры поиска решения

Элемент	Описание
Поле Максимальное время	Служит для ограничения времени, отпускаемого на поиск решения задачи
Поле Предельное число итераций	Служит для ограничения числа промежуточных вычис­лений
Поля Относительная погрешностьи Допусти­мое отклонение	Служат для задания точности, с которой отыскивается решение. Рекомендуется после нахождения решения с величинами данных параметров, заданных по умол­чанию, повторить вычисления с большей точностью и меньшим допустимым отклонением и сравнить с пер­воначальным методом. Использование подобной про­верки особенно рекомендуется для задач с целочис­ленными ограничениями на переменные
Флажок Линейная модель	Служит для поиска решения линейной задачи оптими­зации или линейной аппроксимации нелинейной зада­чи. В случае нелинейной задачи этот флажок должен быть сброшен. Для линейной задачи — установлен, т. к. в противном случае возможно получение невер­ного результата
Флажок Показывать результаты итераций	Служит для приостановки поиска решения и просмот­ра результатов отдельных итераций
Флажок Неотрицательные значения	Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указа­на в поле Ограничениедиалогового окна Добавить ограничение
Флажок Автоматическое масштабирование	Служит для включения автоматической нормализации входных и выходных значений, качественно разли­чающихся по величине. Например, максимизация прибыли в процентах по отношению к вложениям, ис­числяемым в миллионах рублей
Группа Оценки	Служит для выбора метода экстраполяции
Группа Разности	Служит для выбора метода численного дифференци­рования
Группа Метод поиска	Служит для выбора алгоритма оптимизации

9. Решение оптимизационных задач в среде MS Excel л13

9. В нашем конкретном случае установите флажок Линейная модель, а ос­тальные значения, которые используются по умолчанию, можно оставить так, как они и есть. Нажмите кнопку ОК. На экране опять отобразится окно Поиск решения.

10. Нажмите кнопку Выполнить. Средство Поиск решения найдет оптимальный план поставок продукции соответствующие ему транспортные расходы (рис. 2.4).

Рис. 2.4 – Оптимальное решение транспортной задачи

После нажатия кнопки ОК, результаты будут внесены в рабочий лист.

Рис. 2.5 – Окно Результаты поиска решения

Приложение А. Постановка задачи.

1. Транспортная задача. Имеются п пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-й центр распределения c_ij приведена в таблице, где под строкой понимается пункт производства, а под столбцом — пункт распределения. Кроме того, в этой таблице в i -й строке указан объем производства в i -м пункте производства, а в j- м столбце указан спрос в j -м центре распределения. Необходимо составить план перевозок по доставке требуемой продукции в пункты распределения, минимизирующий суммарные транспортные расходы.

1. Задача о назначении. Имеются п рабочих и m видов работ. Стоимость c_ij выполнения i -м рабочим j-й работы приведена в таблице, где под строкой понимается рабочий, а под столбцом — работа. Необходимо составить план работ так, чтобы все работы были выполнены, каждый рабочий был занят только на одной работе, а суммарная стоимость выполнения всех работ была бы минимальной.

ЛІТЕРАТУРА

Основна:

1. Курицкий Б.Я. Оптимизация вокруг нас. / Б.Я. Курицкий.- М.: «Техника», -1989. - 217с.
2. Новичков В.С. Паскаль: Учеб. для сред. спец. учеб. заведений. / В.С. Новичков, Н.И. Парфилова, А.Н. Пылькин.- М.: «Высшая школа», -1997. - 384с.,
3. Павловская Т.А. Паскаль. Программирование на языке высокого уровня. / Т.А. Павловская. Учебник для вузов. - СП.б.: «Питер», 2010. - 464 с.
4. Гарнаев А.Ю. EXCEL, VBA, INTERNET в экономике и финансах. / А.Ю. Гарнаев.- СП.б.: «БХВ-Санкт.П.», 2001. - 816 с.
5. Мак-Федрис Пол. Формулы и функции Microsoft Office Excel 2007 / Пол Мак-Федрис. Пер. с англ. -М.: И.Д. Вильямс, 2008.- 640с.
6. Вадзинский Р. Статистические вычисления в среде Excel. Библиотека пользователя. / Р.Вадзинский - СП.б.: «Питер», 2008. - 608 с.

Додаткова:

1. Степанов А.Н. Информатика: Учеб. для вузов. Степанов А.Н. / - СП.б.: «Питер», 2007. - 765 с.
2. Ларсен Рональд У. Инженерные расчёты в Excel / Рональд У. Ларсен. Пер. с англ. - М.: И.Д. Вильямс, 2002.- 544с.

КОНТРОЛЬНІ ПИТАННЯ

1. Етапи вирішення технічних завдань за допомогою обчислювальної техніки.

2. Способи запису алгоритмів.

3. Словесна форма запису алгоритмів.

4. Схеми алгоритмів.

5. Структурне програмування.

6. Структурограмми.

7. Електронна таблиця EXCEL, основні поняття.

8. Побудова таблиці значень функцій.

9. Побудова графіка функції.

10. Побудова поверхні.

11. Побудова рівняння регресії.

12. Функції робочого аркуша для знаходження рівняння лінійної регресії.

13. Функції робочого аркуша для знаходження рівняння регресії, що описує експоненціальну модель.

14. Поняття масиву.

15. Формула масиву.

16. Операції з масивами.

17. Лінійне оптимізаційне завдання.

18. Рішення лінійної задачі за допомогою засобу “Пошук рішення”.

19. Завдання про оптимальний обсяг виробництва.

20. Транспортне завдання.

21. Завдання про призначення.

22. Завдання про оптимальне планерування штатного розкладу.

23. Завдання про оптимальний склад сплаву.

24. Вирішення системи нелінійних рівнянь.

25. Фінансовий аналіз за допомогою засобів EXCEL.

26. Розрахунок ефективності капіталовкладень.

27. Розрахунок амортизації.

28. Рішення задачі оптимального планерування технологічного процесу

Дата добавления: 2014-01-07