Задача о назначениях. Линейное программирование icon

Задача о назначениях. Линейное программирование


Скачать 28.73 Kb.
НазваниеЗадача о назначениях. Линейное программирование
Размер28.73 Kb.
ТипЗадача

Інформаційні системи та технології.

Зміївська І.В., Обоянська Л.А.


ПРАКТИЧНЕ ЗАНЯТTЯ

ТЕМА ЗАНЯТИЯ: ТРАНСПОРТНЫЕ ЗАДАЧИ. ЗАДАЧА О НАЗНАЧЕНИЯХ. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

Тема занятия. Линейное программирование. Транспортные задачи.

Цель занятия: Изучить методы и алгоритмы решения транспортных задач с использованием технологий MS EXCEL

ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ.

Транспортная задача. Имеются n пунктов производства, в которых сосредоточен некоторый однородный груз в количестве а1,а2 …, аn единиц. Указанный груз необходимо доставить в m пунктов назначения. Заявки на доставку груза составляют b1, b2, …, bm единиц. Стоимость перевозки единицы продукции с i-го пункта производства в j-й центр распределения сij приведена в таблице, где под строкой понимается пункт производства, а под столбцом - пункт распределения. Кроме того, в этой таблице в i-й строке указан объем производства в i-м пункте производства, а в j-м столбце указан спрос в j-м центре распределения.

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



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

^ Математическая формулировка задачи.

Обозначим xij – количество груза доставляемое из i - того пункта отправления в j-тый пункт назначения. Необходимо найти вектор X=(x11, X12, … , X1m, X21, X22, … X2m, , Xnm), удовлетворяющий условиям:





(1) (2)

… … … … … … … … … …




xij0 i=1,2,3, …, n j=1,2,3, … m

Минимизируется целевая функция:

Z=C11X11+C12X12+C1nX1n+C21X21+C22X22+…+C2nX2n+…+CnmXnm

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

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

^ УСЛОВИЕ ЗАДАЧИ

Фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Харькове, Одессе, Донецке, Луцке с производственными возможностями 200, 150, 225 и 175 единиц продукции ежедневно, соответственно. Центры распределения товаров фирмы располагаются в Киеве, Ровно, Львове, Суммах и Днепропетровске с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в табл.1.

Таблица 1. Транспортные расходы

^ Транспортные расходы

Киев

Ровно

Львов

Суммы

Днепропетровск

Харьков

1,5

2

1,75

2,25

2,25

Одесса

2,5

2

1,75

1

1,5

Донецк

2

1,5

1,5

1,75

1,75

Луцк

2

0,5

1,75

1,75

1,75


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

^ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

  1. Запустить программу Microsoft Excel (ПускВсе программыMicrosoft OfficeMicrosoft Excel).

  2. Создать новую рабочую книгу средствами MS Excel (меню ФайлСоздатьЧистая книга).

  3. Сохранить рабочую книгу на диске (меню ФайлСохранить…).

  4. Оформить исходные данные (рис.1). Ввести стоимости перевозок в ячейки В2:F5.



^ Рис.1 Исходные данные


  1. Оформить необходимые формулы (рис.2). Ячейки B8:F11 отведены под значения неизвестных (объёмы перевозок). В ячейки G2:G5 введены объемы производства на фабриках. В ячейки В6:F6 введена потребность в продукции в пунктах распределения. В ячейки В12:F12 введены формулы =СУММ(B8:B11), =СУММ(C8:C11), =СУММ(D8:D11), =СУММ(F8:F11) определяющие объем продукции, ввозимой в центры распределения. В ячейки G8:G11 введены формулы =СУММ(B8:F8), =СУММ(B9:F9), =СУММ(B10:F10), =СУММ(B11:F11) вычисляющие объем продукции, вывозимой с фабрик. В ячейку G12 введена формула целевой функции =СУММПРОИЗВ(B2:F5;B8:F11).



^ Рис.2 Формулы

В результате выполненных действий рабочий лист будет иметь вид (рис.3).




^ Рис.3 Исходные данные, формулы

  1. Оптимизировать задачу. Для решения задачи воспользуемся надстройкой Поиск решения программы Microsoft Excel (меню СервисПоиск решения).

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



^ Рис.4 Поиск решения


    1. В диалоговом окне Параметри поиска решения (рис.5) установить параметры решения задачи.



^ Рис.5 Параметры поиск решения


    1. После нажатия кнопки Выполнить в диалоговому окне Поиск решения, выбрать формат вывода в диалоговом окне ^ Результати поиска решений (рис.6).



Рис.6 Результати поиска решений


  1. Далее средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортне расходы (рис.7).



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


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

  2. Добавим в условие задачи следующие данные: хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $0,75 в день, а штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день.


Учтём издержки по условию задачи и введем следующие данные:

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

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


Условия к задачам с неправильным балансом:

  1. Открытая модель ТЗ с избытком запасов

  1. Открытая модель ТЗ с избытком заявок




  1. Табличная модель решения ТЗ с избытком запасов средствами ПОИСК РЕШЕНИЯ.




Рис.8 Табличная модель решения ТЗ с избытком запасов

  1. Табличная модель решения ТЗ с избытком заявок средствами ПОИСК РЕШЕНИЯ.




Рис.9 Табличная модель решения ТЗ с избытком заявок

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

Задача Некоторая компания имеет четыре сбытовые базы и четыре заказа, которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих заказов. В таблице 1 содержится информация о расстоянии между каждой базой и каждым потребителем. Как следует распределить заказы по сбытовым базам, чтобы общая дальность транспортировки была минимальной

Решение:

Решение можно найти ,используя встроенную программу ^ Поиск решения, так как это задача линейного программирования. Сформируем для выходных данных таблицу2, указав в ячейках G16:I19 и C20:F22 ограничения, а в ячейку H14 введем формулу функции цели


^ Сбытовая база

Расстояние, в км. Потребители.










1

2

3

4

Целевая функция




А

68

72

75

83

F

208




Б

56

60

58

63










С

38

40

35

45










Д

47

42

40

45





































1

2

3

4










А

0

1

0

0

1

<=

1




Б

1

0

0

0

1

<=

1




С

0

0

1

0

1

<=

1




Д

0

0

0

1

1

<=

1







1

1

1

1
















<=

<=

<=

<=
















1

1

1

1












































^ ПОСЛЕ ВЫПОЛНЕНИЯ РАБОТЫ СТУДЕНТЫ ДОЛЖНЫ

Знать:

Уметь:

  • Технологию электронных таблиц. Постановку транспортной задачи. Типы транспортных задач. Решение транспортных задач с правильным балансом. Решение транспортных задач с неправильным балансом при различных соотношениях между объёмами запасов и потребления

  • Работать в диалоговом окне Поиск решения.

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

  • Алгоритм ввода формул.




  • Выполнять анализ оптимального решения







Похожие:

Задача о назначениях. Линейное программирование iconЗадача о назначениях. Линейное программирование
Тема занятия: транспортные задачи. Задача о назначениях. Линейное программирование
Задача о назначениях. Линейное программирование iconПрактичне заняття тема занятия: основные этапы принятия решений. Линейное программирование. Задача распределения ресурсов. Цель занятия
Тема занятия: основные этапы принятия решений. Линейное программирование. Задача распределения ресурсов
Задача о назначениях. Линейное программирование iconПрограмма дисциплины "Программирование на языке высокого уровня" 1 семестр
Введение. Введение в программирование. Понятия программа, программирование, программист. Природа программного продукта. Программирование...
Задача о назначениях. Линейное программирование iconЗадача Источник: О. П. Егоров, О. Л. Казаков Линейная алгебра и математическое программирование для экономистов, Ч. 2 Математическое программирование/Учебное пособие- м., 2004 г., стр. 37
Источник: О. П. Егоров, О. Л. Казаков Линейная алгебра и математическое программирование для экономистов, Ч. 2 Математическое программирование/Учебное...
Задача о назначениях. Линейное программирование iconЗадача на расчёт средней скорости. Задача на расчёт ускорения. Задача на свободное падение тела. Задача на применение закона всемирного тяготения
Равноускоренное движение. Ускорение. Перемещение и скорость при прямолинейном равноускоренном движении
Задача о назначениях. Линейное программирование iconЗадача 1 стр. 3 Задача 2 стр. 7 Задача 3 стр. 11
Используя графический метод решения линейных программ, найти максимальное и минимальное значение линейной функции на одном и том...
Задача о назначениях. Линейное программирование iconРодительское программирование Не живи Не будь ребенком

Задача о назначениях. Линейное программирование iconИмеются следующие данные о реализации мясных продуктов на городских рынках
Рассчитайте характеристики ряда распределения банков по размеру прибыли: среднюю арифметическую, среднее линейное отклонение, среднее...
Задача о назначениях. Линейное программирование iconЗадание по данным пре-ий концерна
По грузообороту за 2010г рассчитать показатели описательной статистики: среднее значение, размах вариации, среднее линейное отклонение,...
Задача о назначениях. Линейное программирование iconДоктор фаустус
Иными словами, посильна ли человеку моего склада эта задача, задача, на выполнение которой меня подвигло скорее сердце, нежели право...
Задача о назначениях. Линейное программирование iconТомас манн доктор фаустус
Иными словами, посильна ли человеку моего склада эта задача, задача, на выполнение которой меня подвигло скорее сердце, нежели право...
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы