25. Анализ чувствительности при изменении вектора ограничений. Физический смысл двойственных переменных.

Анализом чувствительности называется исследование влияния параметров задачи на изменение оптимальных значений целевой ф-ции.

(1)

(2)

-базисный план, - вектор потенциалов, -оптимальный план, соотв вектору b

Лемма: Пусть (b) – оптимальный невырожденный базисный план задачи (1) соотв вектору b. Тогда двойственная задача (2) имеет единственный оптимальный план y⁰ , удовл равенству

Вывод: является мерой чувствительности max прибыли к изменению i-го ресурса. Увеличение i-го ресурса ведет к увеличению i-ой прибыли.

26 Сетевая тз: постановка задачи, основные определения, леммы 1,2.

Транспортными задачами называют модели разнообразных прикладных задач по оптимизации перевозок грузов, к ним же сводятся и физические задачи, имеющие другую математическую природу. Отметим, что транспортные задачи являются задачами ЛП, но имеют очень специфичную матрицу условий, поэтому применение симплекс-метода не рационально. Будем рассматривать метод потенциалов, т.е. реализацию СМ, где учтены особенности матрицы условий.

Сетевая транспортная задача.

Сеть.поток. сетевая транспортная задача.

Рассм 2 множества:

1. . элем этого множ назовем узлами или вершинами.

. элем U называют дугами.

Для наглядности элементы U можно интерпретировать как населенные пункты.

Элементы 2-го множества будем обозначать (i,j).

i-начало дуги

j-конец дуги.

G={I,U} называется ориентированным графом.

i I, a_i – интенсивность вершин.

Если: a_i > 0 -источник

a_i <0 – сток

a_i =0 – промежуточная или транзитная

A_i, a_i >0 – можно трактовать как: в этом населенном пункте А_i производится некоторый продукт в объеме a_i.

Граф, дугам которого приписаны числовые характеристики называются сетью.

Каждой дуге (i,j) U припишем неотрицательное число , которое означает кол-во продукции, которая перевозится по дуге (i,j).

Для каждой вершины i можно определить множество вершин смежных с ней.

Множество всех вершин смежных с i разобьем на 2 подмножества:

Говорят, что в вершине i выполнено условие баланса, если равны 2 величины:

1.общее кол-во продукции поступившей в пункт a_i + произведенное в a_i.

2.кол-во продукции вывозимое из a_i в соседние справа + потребленное в a_i.

, (1)

x - дуговой поток.

Совокупность всех дуговых потоков называется потоком на сети и обозначается

(2)

С x - стоимость перевозки дугового потока

С x - стоимость транспортировки потока (i,j) U.

Модель задачи:

(3)

Обозначим число вершин в сети m, а кол-во дуг n.

|I|=m |U|=n

Строки матрицы соответствуют вершинам сети, а столбцы матрицы - дугам. Рассмотрим структуру матрицы. x присутствуют только в 2 уравнениях. Каждый столбец матрицы содержит ровно 2 ненулевых элемента (-1,1), а ост 0. Такие матрицы называют в программировании малозаполненными.В дальнейшем будем рассматривать метод потенциалов, который является реализацией симплекс-метода, где учитывается структура матрицы условий.

x⁰=( x ,(i,j) U) назовём оптимальным потоком, если он является решением (3).

Х- множество всех сетевых потоков.

Пусть . Тогда просуммируем все уравнения баланса. Необходимое условие того, что 3 имеет решение: -условие общего баланса.

Физический смысл: суммарное произведение равно суммарному спросу.

Ранг матрицы условий <m. Можно доказ, что он равен m-1.

Базисный поток.

i и j – граничные вершины. Висячая вершина, висячая дуга.

Цепь в неориентированном графе –последовательность ребер, где 2 соседних ребра имеют общую вершину.

Если все вершины различны то цепь простая. А если и ребра различны то элементарная.

В ориентированном графе: ориентированная цепь и путь.

Если совпадают начало и конец получаем цикл.

Если существует цепь соединяющая любую пару вершин. то граф является связным.

В ориентированном графе рассматривают некоторую последовательность вершин, которая соответствует некоторым вершинам пути.

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

Дерево - связный граф без циклов.

Если S={I,U}-дерево, то m=n+1.

-частичная сеть

Лемма 1: Сеть без циклов содержит висячее ребро.

Лемма 2: Удаление висячей вершины вместе с висячим ребром или удаление ребра из цикла не нарушает связности сети.