Файл: Задача об использовании ресурсов. Для изготовления двух видов продукции р 1, р 2 используются три вида ресурсов S.docx
Добавлен: 04.12.2023
Просмотров: 172
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы – пунктам назначения. Особенность лишь в том, что все переменные решения принимают только значения 0 или 1 (двоичные переменные) и в каждом столбце и строке может быть только одно ненулевое значение.
Точно так же, как и транспортная модель, задача назначений может быть несбалансированной, содержать недопустимые назначения, иметь альтернативные решения при одном и том же значении целевой функции. Эти варианты моделей назначения строятся в полной аналогии с соответствующими транспортными моделями.
Для решения задачи о назначениях в Excel с использованием надстройки Поиск решения на рабочем листе следует выделить ячейки назначений и подсчитать для них суммы по столбцам и по строкам. В ячейку целевой функции следует ввести формулу, вычисляющую сумму произведений затрат работ на план назначений.
В диалоговом окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения: суммы значений изменяемых ячеек для каждой строки и столбца должны быть равны 1; переменные должны бть двоичными.
Пример 1. Администрация предприятия приняла на работу пять человек. Каждый из них затрачивает различное время на выполнение определенной работы. Необходимо выполнить пять видов работ. Время выполнения работы (с)ij каждым работником приведено в следующей таблице
Требуется назначить на каждый вид работы одного из работников, чтобы общее время, необходимое для завершения всех видов работ, было минимальным.
▼ Экономико-математическая модель задачи
Переменные:
.
Ограничения:
по работам:
;
по работникам:
.
Целевая функция: суммарное время, необходимое для завершения всех видов работ, которое необходимо минимизировать:
Рабочий лист Excel имеет следующий вид
Значения матрицы переменных xij располагаются в ячейках B10:F14. В ячейку С17 введена формула для вычисления значения целевой функции. В ячейках B15:F15 и G10:G14 рассчитываются суммы по строкам и столбцам матрицы переменных.
Заполненное диалоговое окно Поиск решения имеют следующий вид
После выполнения программы работы «Поиск решения» получим
Таблица переменных состоит из единиц и нулей. По единицам определяем, что 1- ый работник должен работать на четвертом виде работы, 2- ой на первом, 3- ий на втором, 4- ый на пятом, 5- ый на третьем. Общее время завершения всех видов работ составляет 83 ч. ▲
Пример 2. На предприятии имеется 6 автомобилей разных моделей. Необходимо в разные районы области перевести 5 грузов. Затраты по перевозке каждого груза каждым автомобилем различны и приведены в следующей таблице
Выбрать автомобиль для каждого вида груза так, чтобы затраты на перевозку были минимальными. Определить эти затраты.
▼ В данном примере число автомобилей больше, чем грузов, т.е. один автомобиль окажется невостребованным.
Рабочий лист Excel и заполненное диалоговое окно имеют следующий вид
После выполнения программы работы «Поиск решения» получим следующее оптимальное решение
По единицам таблицы определяем закрепление автомобилей за грузами, при этом затраты по перевозке грузов составляют 125 усл. ед.
Задача о максимальном потоке
Рассмотрим сеть с одним узлом входа (источник) и одним узлом выхода (сток). Для наглядности будем представлять, что по дугам из источника в сток направляется некоторое вещество (количество машин, информации, жидкости и т.п.). Количество вещества, проходящего через дугу в единицу времени, называется потоком по дуге. Предполагается, что поток, вытекающий из узла, равен потоку, втекающему в узел.
Величина потока определяется как сумма потоков вдоль дуг, исходящих из источника, или, что то же самое, как сумма потоков вдоль дуг, заходящих в сток.
Максимум, или верхнее ограничение на поток в дуге сети будем рассматривать как пропускную способность, или мощность дуги. Мощность потока может зависеть от его направления. Условное изображение в сети
означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность от 2 к 1 равна 4.
Задача о максимальном потоке заключается в нахождении максимальной величины потока, который может войти в систему и выйти из неё в заданный период времени.
При этом должны соблюдаться следующие ограничения:
поток по каждой дуге не должен превышать ее пропускной способности;
общий поток из источника равен общему потоку, приходящему в сток;
для промежуточных вершин количество единиц потока, попавшего в данный узел, должно в точности равняться количеству единиц потока, вышедшего из этого узла.
величина потока по каждой дуге была целым неотрицательным числом.
Задача о максимальном потоке решается как задача линейного программирования.
Пример 1. Система автодорог, проходящих через Псковскую область, может обеспечить пропускные способности, показанные на рисунке (тыс. автомашин в час).
Определим максимальный поток через эту систему.
▼ Расчетные показатели, сформированные на рабочем листе Excel и в режиме просмотра формул показаны на следующих рисунках
Заполненное диалоговое окно Поиск решения имеет следующий вид
После выполнения программы работы «Поиск решения» получим
следующее оптимальное решение:
Вывод. Максимальный поток через сеть равен 9 тыс. Конечная модель потоков показана на следующем рисунке.
▲
Задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы – пунктам назначения. Особенность лишь в том, что все переменные решения принимают только значения 0 или 1 (двоичные переменные) и в каждом столбце и строке может быть только одно ненулевое значение.
Точно так же, как и транспортная модель, задача назначений может быть несбалансированной, содержать недопустимые назначения, иметь альтернативные решения при одном и том же значении целевой функции. Эти варианты моделей назначения строятся в полной аналогии с соответствующими транспортными моделями.
Для решения задачи о назначениях в Excel с использованием надстройки Поиск решения на рабочем листе следует выделить ячейки назначений и подсчитать для них суммы по столбцам и по строкам. В ячейку целевой функции следует ввести формулу, вычисляющую сумму произведений затрат работ на план назначений.
В диалоговом окне Поиск решения выбрать целевую ячейку, изменяемые ячейки и добавить ограничения: суммы значений изменяемых ячеек для каждой строки и столбца должны быть равны 1; переменные должны бть двоичными.
Пример 1. Администрация предприятия приняла на работу пять человек. Каждый из них затрачивает различное время на выполнение определенной работы. Необходимо выполнить пять видов работ. Время выполнения работы (с)ij каждым работником приведено в следующей таблице
| Работник | Время выполнение работы, ч | ||||
| 1 | 2 | 3 | 4 | 5 | |
| А1 | 25 | 16 | 15 | 14 | 13 |
| А2 | 25 | 17 | 18 | 23 | 15 |
| А3 | 30 | 15 | 20 | 19 | 14 |
| А4 | 27 | 20 | 22 | 25 | 12 |
| А5 | 29 | 19 | 17 | 32 | 10 |
Требуется назначить на каждый вид работы одного из работников, чтобы общее время, необходимое для завершения всех видов работ, было минимальным.
▼ Экономико-математическая модель задачи
Переменные:
.Ограничения:
по работам:
; по работникам:
.Целевая функция: суммарное время, необходимое для завершения всех видов работ, которое необходимо минимизировать:
Рабочий лист Excel имеет следующий вид
Значения матрицы переменных xij располагаются в ячейках B10:F14. В ячейку С17 введена формула для вычисления значения целевой функции. В ячейках B15:F15 и G10:G14 рассчитываются суммы по строкам и столбцам матрицы переменных.
Заполненное диалоговое окно Поиск решения имеют следующий вид
После выполнения программы работы «Поиск решения» получим
| | B1 | B2 | B3 | B4 | B5 | |
| А1 | 0 | 0 | 0 | 1 | 0 | 1 |
| А2 | 1 | 0 | 0 | 0 | 0 | 1 |
| А3 | 0 | 1 | 0 | 0 | 0 | 1 |
| А4 | 0 | 0 | 0 | 0 | 1 | 1 |
| А5 | 0 | 0 | 1 | 0 | 0 | 1 |
| | 1 | 1 | 1 | 1 | 1 | |
| | | | | | | |
| | L = | 83 | | | | |
Таблица переменных состоит из единиц и нулей. По единицам определяем, что 1- ый работник должен работать на четвертом виде работы, 2- ой на первом, 3- ий на втором, 4- ый на пятом, 5- ый на третьем. Общее время завершения всех видов работ составляет 83 ч. ▲
Пример 2. На предприятии имеется 6 автомобилей разных моделей. Необходимо в разные районы области перевести 5 грузов. Затраты по перевозке каждого груза каждым автомобилем различны и приведены в следующей таблице
| Автомобиль | Затраты по перевозке груза | ||||
| B1 | B2 | B3 | B4 | B5 | |
| А1 | 37 | 17 | 52 | 73 | 72 |
| А2 | 11 | 39 | 70 | 20 | 27 |
| А3 | 12 | 21 | 25 | 11 | 30 |
| А4 | 49 | 35 | 36 | 35 | 74 |
| А5 | 40 | 31 | 78 | 66 | 79 |
| А6 | 77 | 14 | 59 | 67 | 78 |
Выбрать автомобиль для каждого вида груза так, чтобы затраты на перевозку были минимальными. Определить эти затраты.
▼ В данном примере число автомобилей больше, чем грузов, т.е. один автомобиль окажется невостребованным.
Рабочий лист Excel и заполненное диалоговое окно имеют следующий вид
После выполнения программы работы «Поиск решения» получим следующее оптимальное решение
| | B1 | B2 | B3 | B4 | B5 | |
| А1 | 1 | 0 | 0 | 0 | 0 | 1 |
| А2 | 0 | 0 | 0 | 0 | 1 | 1 |
| А3 | 0 | 0 | 0 | 1 | 0 | 1 |
| А4 | 0 | 0 | 1 | 0 | 0 | 1 |
| А5 | 0 | 0 | 0 | 0 | 0 | 0 |
| А6 | 0 | 1 | 0 | 0 | 0 | 1 |
| | 1 | 1 | 1 | 1 | 1 | |
| | | | | | | |
| | L = | 125 | | | | |
По единицам таблицы определяем закрепление автомобилей за грузами, при этом затраты по перевозке грузов составляют 125 усл. ед.
Задача о максимальном потоке
Рассмотрим сеть с одним узлом входа (источник) и одним узлом выхода (сток). Для наглядности будем представлять, что по дугам из источника в сток направляется некоторое вещество (количество машин, информации, жидкости и т.п.). Количество вещества, проходящего через дугу в единицу времени, называется потоком по дуге. Предполагается, что поток, вытекающий из узла, равен потоку, втекающему в узел.
Величина потока определяется как сумма потоков вдоль дуг, исходящих из источника, или, что то же самое, как сумма потоков вдоль дуг, заходящих в сток.
Максимум, или верхнее ограничение на поток в дуге сети будем рассматривать как пропускную способность, или мощность дуги. Мощность потока может зависеть от его направления. Условное изображение в сети
означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность от 2 к 1 равна 4.
Задача о максимальном потоке заключается в нахождении максимальной величины потока, который может войти в систему и выйти из неё в заданный период времени.
При этом должны соблюдаться следующие ограничения:
поток по каждой дуге не должен превышать ее пропускной способности;
общий поток из источника равен общему потоку, приходящему в сток;
для промежуточных вершин количество единиц потока, попавшего в данный узел, должно в точности равняться количеству единиц потока, вышедшего из этого узла.
величина потока по каждой дуге была целым неотрицательным числом.
Задача о максимальном потоке решается как задача линейного программирования.
Пример 1. Система автодорог, проходящих через Псковскую область, может обеспечить пропускные способности, показанные на рисунке (тыс. автомашин в час).
Определим максимальный поток через эту систему.
▼ Расчетные показатели, сформированные на рабочем листе Excel и в режиме просмотра формул показаны на следующих рисунках
Заполненное диалоговое окно Поиск решения имеет следующий вид
После выполнения программы работы «Поиск решения» получим
следующее оптимальное решение:
Вывод. Максимальный поток через сеть равен 9 тыс. Конечная модель потоков показана на следующем рисунке.
▲