Задачи по теории принятия решений

5 задач по линейному программированию ...

2. Решите задачу линейного программирования:
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в таблице 1.
3. Транспортная сеть (с указанием расстояний) приведена на рис 1. Найдите кратчайший путь из пункта 1 в пункт 4.4. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 2.) ограничена (табл. 2)?5. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл 3.

Контрольная работа по основам теории принятия решений
1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:

Количество единиц питательных веществ на 1 кгХимические веществаКорма 1Корма 2белки31углеводы12протеин16Стоимость 1 кг46Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость.РЕШЕНИЕ:Количество единиц питательных веществ на 1 кгОграниченияХимические веществакорма 1корма 2белки316углеводы128протеин1611Стоимость 1 кг46Экономико-математическая модель задачи:Пусть Х1 – количество корма 1 , X2 – количество корма 2, тогда суммарная стоимость будет равна:F = 4x1+6x2 → min Составим систему ограничений:3х1+х2≥6х1+2х2≥8х1+6х2≥11x1, x2 ≥ 0Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).Границы области допустимых решений.Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений.Рассмотрим целевую функцию задачи F = 4x1+6x2 → min. Построим прямую, отвечающую значению функции F = 0: F = 4x1+6x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:3x1+x2=6x1+2x2=8Решив систему уравнений, получим: x1 = 0,8, x2 = 3,6Откуда найдем минимальное значение целевой функции:F(X) = 4*0,8 + 6*3,6 = 24,83. Транспортная сеть (с указанием расстояний) приведена на рис 1. Найдите кратчайший путь из пункта 1 в пункт 4.Рис. 1. Исходные данные к задаче о кратчайшем путиРЕШЕНИЕ:Начало дугиКонец дугиВремя в пути125134246233322348Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.Очевидно, что С(1)=0.В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 5, либо из вершины 3, пройдя путь, равный 2. Поэтому справедливо соотношение:С(2)=min С(1)+5; С(3)+2В вершину 3 можно попасть либо из вершины 1, пройдя путь, равный 4, либо из вершины 2, пройдя путь, равный 3. Поэтому справедливо соотношение:С(3)=min С(1)+4; С(2)+3В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 6, либо из вершины 3, пройдя путь, равный 8. Поэтому справедливо соотношение:С(4)=min С(2)+6; С(3)+8Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(3).Мы знаем, что С(1)=0. Поэтому:С(3)=min 4; С(2)+3Поскольку очевидно, что С(2) - положительное число, то из последнего соотношения вытекает, что С(3) = 4.С(2)=min 5; 4+2 = 5С(4)=min 5+6; 4+8 = 11Таким образом, длина кратчайшего пути равна 11. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 2. 1→2→44. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 2.) ограничена (табл. 2)?Рис. 2. Транспортная сеть к задаче о максимальном потокеТаблица 2. Исходные данные к задаче о максимальном потокеПункт отправленияПункт назначенияПропускная способность1211321432523223423614745836526716817832РЕШЕНИЕ:311232412231Решение задачи о максимальном потоке может быть получено из следующих соображений. Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 1, а именно, 1 единица в пункт 2, 2 единицы в пункт 3 и 3 единицы в пункт 4. Далее надо добиться, чтобы все 6 вышедших из пункта 1 единиц груза достигли конечного пункта 8. Очевидно, 1 единица груза, пришедшая в пункт 2, можно непосредственно направить в пункт 5 и оттуда в пункт 8.Пришедшие в пункт 3 грузы придется разделить: 1 единицу сразу направить в промежуточный пункт 2, а 1 единицу - в пункт 6 и оттуда в пункт 8. В пункт 4 доставлены 3 единицы из пункта 1 и через пункт 7 их направляем в пункт 8.Решение можно представить в виде таблицы (табл.3).Таблица 3.Решение задачи о максимальном потокеПункт отправленияПункт назначения План перевозокПропускная способность12111322143325223212340236114734582365026701681178335. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл 3.Таблица 3. Исходные данные к задаче коммивояжераГород отправленияГород назначенияЗатраты на проездАБ2АВ1АД5БА3БВ2БД1ВА4ВБ1ВД2ДА5ДБ3ДВ3РЕШЕНИЕ:АБВДАМ215Б3М21В41М2Д533МВозьмем в качестве произвольного маршрута:X0 = (1,2);(2,3);(3,4);(4,1)Тогда F(X0) = 2 + 2 + 2 + 5 = 11Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.di = min(j) dijАБВДdiАМ2151Б3М211В41М21Д533М3Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.АБВДАM104Б2M10В30M1Д200MТакую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:dj = min(i) dijАБВДАM104Б2M10В30M1Д200Mdj2000После вычитания минимальных элементов получаем полностью редуцированную матрицу.АБВДАM104Б0M10В10M1Д000MСумма констант приведения определяет нижнюю границу H:H = ∑di + ∑djH = 1+1+1+3+2+0+0+0 = 8Длина маршрута определяется выражением:F(Mk) = ∑dijПричем каждая строка и столбец входят в маршрут только один раз с элементом dij.Определяем ребро ветвления и разобьем все множество маршрутов.С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.АБВДdiАM10(1)41Б0(0)M10(1)0В10(1)M11Д0(0)0(0)0(0)M0dj00010d(1,3) = 1 + 0 = 1; d(2,1) = 0 + 0 = 0; d(2,4) = 0 + 1 = 1; d(3,2) = 1 + 0 = 1; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (1,3), следовательно, множество разбивается на два подмножества (1,3) и (1*,3*).Исключение ребра (1,3) проводим путем замены элемента d13 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,3*), в результате получим редуцированную матрицу.АБВДdiАM1M41Б0M100В10M10Д000M0dj00001Нижняя граница гамильтоновых циклов этого подмножества:H(1*,3*) = 8 + 1 = 9Включение ребра (1,3) проводится путем исключения всех элементов 1-ой строки и 3-го столбца, в которой элемент d31 заменяем на М, для исключения образования негамильтонова цикла.В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.После операции приведения сокращенная матрица будет иметь вид:АБДdiБ0M00ВM010Д00M0dj0000Сумма констант приведения сокращенной матрицы:∑di + ∑dj = 0Нижняя граница подмножества (1,3) равна:H(1,3) = 8 + 0 = 8 ≤ 9Поскольку нижняя граница этого подмножества (1,3) меньше, чем подмножества (1*,3*), то ребро (1,3) включаем в маршрут с новой границей H = 8Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества.С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.