Анализ расходов

    qi(X) Ј bi  (I = 1,M),

    X і 0.

    Критерии в свертке могут быть нормированы. Решение, полученное в результате оптимизации скаляризованного критерия эффективно.

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

    Направление методов, использующих ограничения на критерии включает два подхода:

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

    В методе ведущего критерия все целевые функции кроме одной переводятся в разряд ограничений. Пусть g = (g2, g3,…, gк-1) - вектор, компоненты которого представляют собой нижние границы соответствующих критериев. Задача будет иметь вид

    F = f1 (max)

    fr і gr (r = 2,K),

    qi (X) Ј bi (I = 1,M),

    X і 0.

    Полученное этим методом решение может не быть эффективным, поэтому необходимо проверить его принадлежность области компромиссов.

    Метод ведущего критерия применяется в таких задачах, как минимизация полных затрат при условии выполнения плана по производству различных видов продукции, максимизация выпуска комплектных наборов при ограничении на потребляемые ресурсы. 

    Алгоритм метода последовательных уступок:

1. Критерии нумеруются в порядке убывания важности.
2. Определяется значение f*1. Лицом, принимающим решение, устанавливается величина уступки D1 по этому критерию.
3. Решается  задача по критерию f2 с дополнительным ограничением f1(X) і f*1 - D1.

    Далее  пункты 2 и 3 повторяются для критерия f2,…, fk.

    Полученное решение не всегда принадлежит области компромиссов.

                    

    При решении задач методами целевого программирования предполагается приближение значения каждого критерия к определенной величине fr, т.е. достижение определенной цели. В самом общем виде задача целевого программирования формулируется как задача минимизации сумм отклонений целевых функций от целевых значений с нормированными весами. 

    d(F(X), F) = ( е w_R кf_R (X) - f _R к^p) (min),

    где F =  {f₁,...., f_R} - вектор целевых значений,

    W = {w₁,..., w_R} - вектор весов, обычно е w_R = 1_,  w_R і 0

    (r = 1, K), значения p находятся  в пределах 1 Ј p Ј Ґ,

    d(.) - расстояние (мера отклонения) между F(X) и F. 

    Во многих случаях применения целевого программирования полагают p = 1. Например, в линейном  целевом программировании функции f_R (X) (r=1, K) и          q_i (X) (i = 1,M) линейны и нет целочисленных переменных.

    В задачах лексикографического программирования критерии строго упорядочены по важности, так что при сравнении пары решений в первую очередь используется критерий f₁ и лучшим считается то решение, для которого значение этого критерия больше, если значения первого критерия для обоих решений оказываются равными, то применяется критерий f₂ и предпочтение отдается тому решению, для которого значение f₂ больше, ели и второй критерий не позволяет определить лучшее решение, то привлекается f₃ и т.д. Учет информации о важности критериев осуществляется путем поэтапного решения задачи минимизации отклонений критериев от целевых значений. Часто в лексикографическом программировании F = F, p = 1  .

    Точка F обычно не принадлежит области допустимых значений и поэтому ее иногда называют идеальной или утопической точкой. В некоторых методах целевого программирования допускается задание утопического множества, как пример при построении архимедовой задачи. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Глава 2. Практическая часть

Задача 1. 

Max Z= x₁+x₂+x₃

6X₁+12x₂+3x₃ <=21

4X₁+3x₂+8x₃ <=15

3x₁+4x₂+8x₃<=15

Решение. 

 
 
 
 
 
 
 
 

Задача 2.

Min Z= 7x1+6x2+3x3+4х4+ х5 

2х1+6x2+3x3+х4+х5<=26 

x1+4x3+5х4<=20 

Решение.

 
 
 
 
 
 

Задача 3.

Составим транспортную таблицу задачи.

В данном случае, имеем задачу закрытого типа, так как

.

При построении плана мы должны учитывать, что сумма перевозок в столбце должна оказаться равной потребностям в данном пункте, а сумма перевозок в строке - запасу в пункте, соответствующем данной строке. Заполнение начинается с верхнего левого угла таблицы. Величина перевозки устанавливается равной минимальной из величин: величине остатка запасов в пункте i или величине еще неудовлетворенного спроса в пункте j.

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

.

Естественно, что найденный план далек от оптимального плана относительно предложенных затрат.

Еще одним распространенным методом решения транспортной задачи является метод минимального элемента. В таблице отыскиваем и в первую очередь заполняем соответствующую клетку: . Затем вычеркиваем остаток соответствующей строки, если , или столбца, если , и корректируем остатки запасов и неудовлетворенного спроса. В оставшихся клетках таблицы снова отыскиваем минимальную стоимость перевозки и заполняем соответствующую клетку и т. д.