3. Транспортная задача. Нахождение базового решения транспортной задачи методом минимального элемента. Нахождение базового решения транспортной задачи методом северо-западного угла.

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

ТЗ называется закрытой (сбалансированной), если суммарные запасы на складе = суммарным потребностям, иначе задача называется открытой (несбалансированной). Общая постановка ТЗ: пусть имеется m - складов, n – пунктов назначения, ai – кол-во товаров на i-складе, bj – потребности в j – магазине. Балансовое уравнение: = . Стоимость перевозки из i – склада в j – магазин => Cij. Xij – кол-во товара перевезенного с i – склада в j – магазин.

Метод min элемента: самая дешевая доставка осущ-ся первой. Находится ячейка с наименьшим значением тарифа на перевозку груза. В эту ячейку выписывается объем груза (Xij), который можно доставить с соответствующего этой ячейке склада на соответствующий завод. Объемы запасов и потребностей уменьшаются на величину груза. Если запасы склада исчерпаны, то полностью вычеркивается эта строка. Если потребности завода полностью удовлетворены – полностью вычеркивается этот столбец.

Метод северо – западного угла: поставки осущ.-ся с ячейки A₁B₁ по строкам слева на право, сверху вниз.

4. Нахождение базового решения транспортной задачи методом Фогеля. Осложнения транспортной задачи. Классические задачи линейного программирования (задачи о назначениях, раскрое, рюкзаке и т.Д.)

Метод Фогеля: состоит в вычислении для каждой строки таблицы разницы между двумя наименьшими тарифами. 1) в строке вычисляется разница между двумя наименьшими тарифами ( тоже самое в столбцах ) 2) наибольшая разница является предпочтительной 3) пишем отгрузку в ячейку с минимальным тарифом 4) строки и столбцы которые исчерпали свои возможности вычеркиваются .Осложнения ТЗ: избыток запасов, дефицит запасов, запрещенный маршрут.

5. Многокритериальный выбор. Требования к набору критериев. Метод оценочных баллов. Метод сворачивания многокритериального критерия – метод аддитивной оптимизации. Определение весов критериев.

Многокритериальный выбор: если критерий один, то показатель скалярный, иначе – векторный. Если критериев много: можно получить более качественное решение, но труднее сделать выбор. Иногда вводят обобщающий (интеграционный) критерий – такой критерий можно разложить на ряд иерархических подчиненных критериев.

Требования к набору критериев: А) Полнота – набор критериев должен обеспечивать оценку объекта экспертизы. Б) Действенность – критерии должны однозначно пониматься экспертами. В) Разложимость – удобно работать с небольшими числами критериев (не >7), иначе должна быть возможность разложить на группы критериев. Г) Не избыточность – критерии не должны дублировать друг друга. Д) Минимальная размерность – должны быть лишь те критерии, без которых оценка невозможна.

Метод оценочных баллов: А) Имеется В_i вариантов решений Б) Каждый вариант оценивается К_j наборов частных критериев В) Известны значения критериев для каждой пары В_i К_j Г) На субъективной основе устанавливаются коэффициенты значимости (веса) частных критериев. Вес – позволяет определить степень предпочтения критерия по отношению к другим критериям. Д) Для каждого варианта определяют сумму В_i =∑ V_i *A_ji , В₁=V₁*A₁₁+V₂*A₁₂+V₃*A₁₃+V₄*A₁₄ Е) В зависимости от цели выбирают max или min В_i

Недостатки метода: а) субъективность назначения V_ij весов; б) не учитывается, что одни частные критерии нужно максимизировать, другие минимизировать; в) А_ij для разных критериев могут существенно отличаться.

Метод аддитивной оптимизации

Цель: привести частные критерии к одному аддитивному критерию F(a_ij)

Fa_ij= ∑ⁿ_j=1 λ_j*A_ij, где n- кол-во частных критериев, λ_j- весовые коэффициенты частных критериев, A_ij – конкретное значение частых критериев. ∑ⁿ_j=1 λ_j =1

Требования к весовым коэффициентам: а) должны быть количественно соизмеримы, б) частные критерии должны иметь одинаковую размерность (руб.).

На практике это редкий случай, поэтому значения по частным критериям нормализуют.

Нормализация: А) Определяют max и min каждого частного критерия: a⁺ _j = max a_ij, a^- _j= min a_ij Б) Выделяют группы критериев, которые надо максимизировать и минимизировать

В) Определяют значение аддитивного критерия по формуле Fa_ij= ∑ⁿ_j=1 λ_j*A_ij Г) Найти min/max F_j

Определение весов критериев: А) Простое ранжирование – имеется j частных критериев, их ранжируют по важности. (j j-1 j-2 … 1) j – самый важный критерий, 1 – наименее важный. Все веса нормируют – делят на их сумму. Если два или более критерия одинаковы по важности, то и веса должны быть одинаковы и равны среднему значению. Б) Пропорциональный метод – выбирают наименее важный критерии, его вес = 1. Их может быть несколько. Все остальные критерии имеют вес по отношению к наихудшему – во сколько раз >. Определяют сумму всех весов. Все веса делят на сумму.