Курс лекций по линейному программированию

где S_j – неотрицательная добавочная переменная, которая по определению должна принимать целое значение, но для данной системы ограничений =>, что если

x_j=0, то S_j=-q_j,

т.е. она принимает  отрицательное значение => не является допустимой. Т.о. полученное ранее решение  не удовлетворяет новому ограничению  и в этой ситуации используется М-метод. 
 

2.Комбинаторный  метод

Идеи: Пусть решение задачи без ограничений целочисленности х* - целочисленная переменная, значение которой в оптимальном плане является дробным, то интервал

{x*]≤x_r<[x_r^*]+1 не содержит допустимых решений с целочисленной координатой х_r => допустимое значение х_r должно удовлетворять одному из следующих неравенств:

х_r≤[x_r^*],

x_r≥[x_r^*]+1

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

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

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

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

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

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

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

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

Лекция № 4: «Транспортная  задача».

Пусть имеется  m пунктов производства (складирования) однородной продукции, запасы которой = А₁, … , А_n. Имеется n пунктов потребления этого же продукта с потребностями В₁, … , В_n; известны тарифы (транспортные расходы, связанные с доставкой единицей продукта из заданного пункта отправления в пункт потребления. {C_ij} i= j= /

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

Формально требуется  указать вектор х={x_ij}  поставок (х_ij≥0 – ограничения, где х_ij количество единиц продукта, направленный из i-ого пункта отправления в j-ый пункт назначения), который удовлетворяет следующим условиям:

1. условие полного удовлетворения потребления для всех пунктов потребления
2. Весь продукт, хранимый в пункте отправления должен быть вывезен ∑х_ij=A_i
3. достовляющ. минимум целевой функции

транспортная  задача исследуется только на минимум.

ТЗ называется закрытой (сбалансированной), если выполняется  условие:

В противном  случае ТЗ называется открытой. 

Теорема: необходимое  условие разрешимости ТЗ.

ТЗ разрешима  тогда и только тогда, когда она  сбалансирована. Если задача открыта, то для преобразования её в закрытую следует сделать:

а.) в случае дефицита (суммарное потребление > суммарных запасов) вводится пункт потребления с запасами равными

Из которого перевозку во все пункты назначения осуществляют по нулевым тарифам

б.) в случае избытка  продукции вводится фиктивный пункт  потребления с потреблением равным: в который перевозки осуществляются по нулевым тарифам.

Метод решения  ТЗ.

Пусть имеется  ТЗ:

х_ij≥0

Общее число  уравнений m+n.

Это каноническая форма линейной задачи, но т.к. присутствует условие сбалансированности

Которое «связывает»  некоторые из этих m+n уравнений, то число линейных независимых уравнений (переменных) = n+m-1. Т.к. известны в задаче т. n, то в невырожденном опорном плане должно быть n+m-1 положительная компонента с остальными нулевыми.

Содержательно: имеем n+m-1 ненулевую поставку, которые образуют суммарный объем перевозок из всех пунктов отправления во все пункты потребления.

Опорный план вырожденный, если число положительных компонент строго меньше n+m-1

Т.к. ТЗ является задачей линейного программирования, то её можно решать симплекс-методом, при специальном представлении  данных, называемой транспортной таблицей.

В таблицу заносят  значения ненулевых поставок (x_ij>0) и такие клетки называются «занятыми» остальные – свободными. 

Сопоставление исходного опорного плана:

Метод наименьших переменных.

Выбираем клетки с наименьшим тарифом и в эту  клетку помещаем поставку x_ij=min(A_i,B_j) по минимальному тарифу перевозится максимальное количество продукта.

Получился вырожденный  опорный план. Прежде, чем переходить к проверке плана на оптимальность  следует сделать его невырожденным. Для этого обычно в свободной  клетке ставят 0 и эта клетка считается  занятой и таких нулей должно быть столько, сколько не хватает занятых клеток до невырожденного опорного плана. Но при этом формировать занятые клетки необходимо так, чтобы не образовалось цикла. 

Проверка плана  на оптимальность.

Определение: циклом называют замкнутую ломаную линию, звенья которой взаимно перпендикулярны и проходят только вдоль строк и столбцов и удовлетворяют условиям:

1. две и только две занятые клетки должны находится в одной строке и одном столбце, в котором данная линя осуществляет поворот на 90^о
2. последняя занятая клетка находится в одной строке или одном столбце с первой. Клетки в которых цикл осуществляет поворот, называется клеткой цикла или вершиной. Т.к. цикл строится для каждой свободной плоскости, то он единственный и клетками цикла будет одна свободная, а остальные занятые.
3. если ломаная линия, образующая цикл пересекается, то клетки самопересечений не являются клетками цикла, если же она проходит через занятую клетку, но в ней нет поворота, то она не является клеткой цикла.

 

При построении цикла руководствуются следующими правилами:

1. никакая последовательность занятых клеток не образует цикл (необходимое условие существования цикла).
2. в каждой свободной клетке цикл единственный
3. виды циклов:

 

Каждой клетке цикла соответствует коэффициент целевой  функции с_ij.

Пусть для свободной  клетки ij построен цикл. Расставим чередующиеся знаки + и – начиная с – свободной клетки на которой цикл строится и осуществляется обход цикла. Подсчитаем сумму тарифов клеток цикла, который назовём оценкой свободных клеток ij. Свободные клетки – аналог небазисных векторов. 

Первая транспортная теорема.

Для любой ТЗ оценка свободных клеток ij- элементов индексной строки симплекс-таблицы (соотв. ij небазисному вектору) и численно = z_ij-c_ij.

Опираясь на эту теорему рассчитаем индекс стока, т.к. ТЗ – задача на минимум, то критерий отрицательный:

- план оптимальный,  если все оценки свободных  клеток не положительны

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

Вторая транспортная теорема.

Для построения нового опорного лана ТЗ необходимо:

1. определить свободную клетку с максимальной положительной оценкй.
2. для данной клетки строится цикл и расставляются знаки – и +
3. среди поставок положительных клеток цикла выбираются минимальные из поставок положительных клеток.

 

Такое перераспределение  приводит к новому основному плану.

Замечание: если минимальная поставка положительной клетки находится в двух или более клетках, то при перераспределении и получается вырожденный опорный план и в этом случае прежде чем переходить, следует сделать его невырожденным. 

Метод потенциалов

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

Определение: числа  называются потенциалами если выполняются условия:

х*={x_ij}-оптимальный план, то для занятых клеток выполняется

х_ij>0 V_j-U_i=C_ij (*)

x_ij=0 V_j-U_i=C_ij (**)

(c ij-тариф)

В этом случае Δ_ij=V_j-U_i-C_ij

Алгоритм:

1. находит базисное решение
2. из условия (*) вычисляем все потенциалы, но т.к. потенциалов m+n, а значений m+n-1, то система неопределенна и для получения единственного рения обычно полагают U₁=0.
3. после определения потенциалов проверяют условие (**) для свободных клеток, если оно выполняется, то план оптимален, иначе вычисляют оценку Δ_ij среди них выбирают наибольшую положительную и переходят к новому опорному плану, согласно второй транспортной теореме.

 
 

Лекция № 5: «  Теория игр».

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

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

Ситуация называется конфликтной, если в ней участвуют  стороны, интересы которых противоположны.

Игра – это  реальный или формальный конфликт, в котором есть 2 участника, каждый из которых стремится к достижению своих целей.

Допустимые действия игроков – правила игры.

Количественная  оценка результатов игры – платеж.

Игра парная, если участвуют две стороны и  множественная в противном случае.

Под ходом в  игре понимается выбор одного из предложенных правилами игры действий и его реализация.

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