Оптимальные решения и их свойства. Экономико-математическая модель оптимизационной задачи. Критерии оптимальности. Основные требования к локальному критерию оптимальности, страница 6

Находим в таблице клетку с минимальным стоимостным показателем. Это клетка (3,4), где  С₃₄=2. Назначаем в эту клетку максимально возможную корреспонденцию (х₃₄ =5), так как а₃ = 5.

Вычеркиваем строку 3 из рассмотрения. В оставшейся части матрицы отыскиваем вновь клетку с мин-ным стоимостным показателем – клетку (9,8). Назначаем в эту клетку корреспонденцию (х₉₈ =12) и т.д. Число корреспонденции равно m + n – 1=5+4-1=8, т.е. получили базисное решение.

3-й способ: метод двойного предпочтения дает возможность получения начального плана сравнительного близкого к оптимальному.

Находим в каждой из строк клетки с мини-ным значением критерия (*), затем тоже самое проделываем в каждом столбце (*). Отдельные клетки имеют миним-ое значение критерия как по строке, так и по столбцу (**). В нашем случае это клетки (3,4), (7,6), (9,8). Назначаем в эти клетки макси-но возможные корреспонденции: в клетку (3,4)–5; (7,6)–15; (9,8)–12. В оставшейся части матрицы корреспонденции распределяем по способу наименьшего значения критерия, заполняя сначала клетки, отмеченные знаком (*). Число корреспонденций равно m+n-1 (базисное решение).

12  Оптимизация плана обеспечения депо объектами ремонта

После построения начального плана производится его улучшение до оптимального.

Одним из наиболее распространенных методов является метод потенциалов, который применяется для решения задач в матричной и сетевой формах.

Условие оптимальности следующее:

Рассматриваемый план явл-ся оптимальным тогда, когда каждому отправителю i и получателю j могут быть приписаны числа (потенциалы) U_i и V_j, которые отвечают след. условиям:                          

V_j – U_i ≤ C_ij , если х_ij=0

V_j – U_i = C_ij , если х_ij>0.                            (1)

Для решения задачи необходимо знать хотя бы один потенциал (столбца или строки).

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

Условие оптимальности плана для сетевой задачи определяется след. образом. План оптимален тогда, когда:

V_s – U_r ≤ C _rs , если х_rs=0;

V_s – U_r = C_rs , если х_rs>0                          (2)

где rs –  вершины, ограничивающие звено;

C_rs – значение показателя оптимальности на звене rs;

х_rs – корреспонденция на звене rs от вершины r к s.

13 Нетранспортные линейные модели, их классификация

Для оптимизации текущего планирования применяется ряд линейных экономико-математических моделей, которые не сводятся к транспортной задаче. Эти модели классифицируются по следующим признакам:

- По математическому типу модели различают задачи:

а) распределительные линейные, в которых подобно транспортным задачам каждая переменная входит лишь в два ограничения и имеет коэффициенты при неизвестных отличные от1.

б) линейные общего вида, когда все или часть переменных входит более чем 2 ограничения.

в) с дискретными переменными, принимающими, например, только целые значения. Если влияние дискретности на целевую функцию незначительно, им пренебрегают и сводят задачу к типу а) или б). При значительном влиянии используются методы оптимизации в задачах перспективного планирования.

- В зависимости от технико-экономической тематики различают следующие задачи:

а) оптимального использования стационарного оборудования;