- •3. Математические методы принятия решений.
- •Задание 3.1. Задача линейного программирования о смесях
- •Задание 3.2. Транспортная задача
- •Задание 3.3. Задача целочисленного программирования
- •4. Задачи для самостоятельного решения Задание 4.1.
- •Задание 4.2.
- •Задание 4.3.
- •Задание 4.4.
- •Задание 4.5.
- •Задание 4.6.
- •Задание 4.7.
- •Задание 4.8.
- •Задание 4.9.
- •Задание 4.10.
- •Задание 4.11.
- •Задание 4.12.
- •Задание 4.13.
- •Задание 4.14.
- •Задание 4.15.
- •Задание 4.16.
- •Задание 4.17.
- •Задание 4.18.
- •Задание 4.19.
- •Задание 4.20.
- •Задание 4.21.
- •Литература
Задание 3.2. Транспортная задача
Компания имеет два товарных склада и двоих оптовых покупателей. Известно, что общий объем запасов на складах составляет 30 единиц продукции и совпадает с общим объемом заказов покупателей. Конкретные данные о загруженности каждого из складов (в тыс. ед.), потребности каждого покупателя (в тыс. ед.) и стоимости перевозки (тыс. руб.) приведены в таблице.
На пересечении столбцов и строк цифры указывают стоимость перевозок с соответствующего склада соответствующему потребителю. Графа «Наличие» означает емкость склада, а графа «Запрос» – заказ каждого потребителя.
|
Bl |
B2 |
Наличие |
Al |
1 |
2 |
20 |
А2 |
2 |
1 |
10 |
Запрос |
16 |
14 |
30 |
Отметим, что сумма данных в строке «Запрос» и «Наличие» совпадает.
Указания:
Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводится именно к этой задаче. Иногда она называется также задачей о перевозках, так как цель этой задачи заключается в минимизации полной стоимости перевозок известного количества товаров со складов к потребителям.
По критерию стоимости эта задача формулируется следующим образом.
В пунктах отправления находится определенное количество единиц некоторого однородного продукта. Данный продукт потребляется в пунктах, объем потребления –. Расходы на перевозку единицы продукта из пункта в пункт равныи приведены в матрице транспортных расходов. Требуется составить такой план перевозок, при котором весь продукт вывозится из пунктов в пункты в соответствии с потребностью и общая величина транспортных издержек будет минимальной. Количество продукта, перевозимого из пунктов в пункты , обозначается .
Целевая функция задачи будет иметь вид
а ограничения выглядят следующим образом:
, ,
Эти условия означают полное удовлетворение спроса во всех пунктах потребления, и определяют полный вывоз продукции от всех поставщиков. Необходимым и достаточным условием разрешимости задачи является условие баланса:
,
при котором транспортная задача называется закрытой.
Выбор переменных. Обозначим количество единиц товара перевезенных со склада номерi к покупателю с номером k. Таким образом, имеем четыре неизвестных величины: .
Составим целевую функцию стоимости перевозок с обоих складов к обоим покупателям в соответствии с коэффициентами таблицы
Составим систему ограничений.
ограничение на наличие товара:
ограничение на запрос покупателей:
ограничение не отрицательности
Далее задача решается средствами Excel аналогично решению Задания 3.1. Оптимальное решение задачи имеет вид:
.
Задание 3.3. Задача целочисленного программирования
Пятерым следователям нужно поручить расследование пяти уголовных дел. В силу разной квалификации на завершение расследования им потребуется различное время. Время выполнения (в сутках) приведено в таблице. Как следует распределить следователей прокуратуры по заданиям, чтобы минимизировать время выполнения?
Люди |
Задания | ||||||||
10 |
5 |
9 |
18 |
11 | |||||
13 |
19 |
6 |
12 |
14 | |||||
3 |
2 |
4 |
4 |
5 | |||||
18 |
9 |
12 |
17 |
15 | |||||
11 |
6 |
14 |
19 |
10 |
Указания:
К задачам целочисленного (дискретного) программированием относятся задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Это продиктовано физической неделимостью многих элементов расчета (например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д.). В таких задачах переменные могут принимать только два значения – единица и нуль.
Пусть – время участия i человека в выполнении j-го задания. Все величины – неотрицательны, и, поскольку каждый человек должен быть полностью задействован, а каждое задание полностью выполнено, величины должны удовлетворять следующим ограничениям:
При этих ограничениях минимизируется полное время
Таким образом, получилась задача линейного программирования транспортного типа. Все суммы по строкам и по столбцам равны 1. Поскольку задача транспортная, в ее оптимальном решении (целочисленном) пять из величин будут равны 1, а остальные – 0. Далее задача решается стандартными средствами Excel.