9903

Симплекс-метод решения задач ЛП

Реферат

Информатика, кибернетика и программирование

Симплекс-метод решения задач ЛП Симплекс-метод предложен Дж. Данцигом в 1947 г. непосредственно применяется к общей задаче ЛП в канонической форме: Z = CTX min, при ограничениях X0, AX = B, B > 0, Любое неотрицательное решение...

Русский

2013-03-18

86.5 KB

20 чел.

Симплекс-метод решения задач ЛП

Симплекс-метод предложен Дж. Данцигом в 1947 г. непосредственно применяется к общей задаче ЛП в канонической форме:

Z = CTX  min,

при ограничениях

X  0, AX = B, B > 0,

Любое неотрицательное решение системы AX=B называется допустимым решением

Система AX=B может быть решена, если n-m неизвестных приравнять к нулю и разрешить ее относительно оставшихся

Если полученное решение единственно, то оно называется базисным решением

Если базисное решение допустимо, то оно называется базисным допустимым решением

Переменные, равные нулю в базисном решении, называются небазисными переменными. Остальные называются базисными и образуют базис.

Утверждение 2.1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Утверждение 2.2. Допустимая область является выпуклым множеством.

Утверждение 2.3.  Базисные  допустимые  решения  соответствуют вершинам допустимого множества.

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

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

Общая схема симплекс-метода

Z = CTX  min,

X  0, AX = B, B > 0,

А = ER

E - единичная матрица, размерности m,

R - матрица-остаток

c1, c2, ... , cn,   x1, x2, ..., xm 

, > 0   

x1, x2,..., xm - базисные переменные

xm+1, xm+2,..., xn - небазисные

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

1. Найти переменную для включения в базис.

xm+1, xm+2, ..., xn - небазисные

< 0  ( xs   Z )

0    0 i   Z не может быть уменьшено решение найдено

2. Найти переменную для исключения из базиса. 

Пусть > 0.

Пока xs = 0 ограничение имеет вид: xi = b .

xs > 0    ограничение принимает вид: xi + a'isxs = b .

xi 0  max xs= b /a'is (или xi, станет отрицательным)

Если a'is < 0, то xs  xi, т.е. xi 0 всегда.

Рассматривая все i = 1, ..., m, имеем

   xs = min(b /a'is).

Пусть xs = xr  xr = 0, xs = b /a'rs

Другие базисные переменные останутся положительными (неотрицательными).

Элемент a'rs - ведущий элемент, строка r - ведущая строка, столбец s - ведущий столбец.


3. Записать задачу в новой форме.

Переменная xs стала базисной.  

Новый базис имеет вид: x1, x2, ..., xr-1, xs, xr+1, ..., xm

а. Коэффициент при xs в ведущей строке надо сделать равным единице (ведущую строку разделить на a'rs).

б. Необходимо исключить xs из других ограничений (из i-й строки, имеющей коэффициент a'is при xs вычесть ведущую строку (с коэффициентом 1 при xs) умноженную на a'is , i=1, ..., m, ir).

в. Преобразовать целевую функцию (коэффициент c's<0 при xs), вычитая из нее новую ведущую строку, умноженную на c's.

Построив новую задачу (эквивалентную исходной), необходимо вернуться к шагу 1.

Если все коэффициенты целевой функции неотрицательны, то задача решена.

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


Порождение начального допустимого базиса

Пусть исходная задача имеет вид:

z = c1x1 + c2x2 + ... + cnxn  min

при ограничениях:

xi  0, i = 1, ..., n,

В первые m1 ограничений ввести дополнительные переменные xn+1, . . . , с коэффициентом -1.

В последние m3 ограничений ввести дополнительные переменные с коэффициентом +1.

В первые m1+m2 ограничений ввести искусственные переменные с коэффициентом +1.

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

В целевую функцию Z дополнительные переменные входят с нулевым коэффициентом, а искусственные с коэффициентом, равным "очень большому" числу М.

Двойственность в линейном программировании

Прямая задача:

Сколько изделий и какой конструкции xj (j = 1, …, n) необходимо произвести, чтобы при заданных стоимостях                    cj (j = 1, …, n) единицы продукции и размерах имеющихся ресурсов bi (i = 1, …, m) максимизировать выпуск продукции в стоимостном выражении?

z = c1x1 + c2x2 + … + cnxn  max

xj  0, j = 1, …, n

Двойственная задача:

Какова должна быть цена yi единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости продукции cj минимизировать общую стоимость затрат?

f = b1y1 + b2y2  + … + bmym  min

yi  0, i = 1, …, m,


  

Пары двойственных задач

Прямая задача:                    Двойственная задача:

                 

              

                 

               


Основные теоремы двойственности

(для задач вида 3)

Теорема 1. Двойственная задача с двойственной есть исходная задача.

Теорема 2. Значение функции Z, соответствующее любому допустимому решению прямой задачи, не меньше значения функции f, соответствующего допустимому решению двойственной задачи.

Теорема 3. Если исходная задача имеет конечной решение z=zmin, то и двойственная задача имеет конечное решение f=fmax, причем zmin=fmax. При этом вектор-решение двойственной задачи может быть определен из симплекс-таблицы последней итерации исходной задачи.

Теорема 4. Если двойственная задача имеет конечное решение f=fmax, то исходная задача имеет конечное решение z=zmin, причем fmax=zmin. При этом вектор-решение исходной задачи может быть определен из симплекс-таблицы последней итерации двойственной задачи.


Использование двойственности при решении задач ЛП

Теория двойственности позволила усовершенствовать симплекс-метод и создать улучшенный (или исправленный) симплекс-метод, который позволяет получать сразу решение и исходной и двойственной задач. Поэтому можно выбирать, решать ли задачу в том виде, в котором она поставлена, или решать двойственную задачу. Так как объем вычислений в задаче ЛП связан скорее с количеством ограничений, чем с количеством переменных, то можно порекомендовать переходить к двойственной задаче в случае, когда ограничений больше, чем переменных.

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

Теория двойственности создана Дж. Фон Нейманом и Л.В. Канторовичем.


Транспортная задача ЛП

Имеется m пунктов производства с объемами производства ai, i=1,..., m и n пунктов потребления с объемами потребления bj, j=1,..., n, cij - стоимость транспортировки одного изделия (единицы продукции) из пункта производства i в пункт потребления j. Задача заключается в планировании перевозок от поставщиков к потребителям, минимизирующих стоимость транспортировки.

xij - объем планируемой перевозки продукции от поставщика i к потребителю j

z = c11x11+ c12x12+ . . . + cmnx1  min,

x11 + x12 + . . . + x1n                        = a1,

                               x21 + x22 + . . . + x2n                                = a2,

.   .         .       .         .        .       .     .          .

                                                         xm1 + xm2 + ... + xmn     = am,

x11                           + x21                             + xm1                                 = b1,

     x12                             + x22                               + xm2                       = b2,

.         .         .        .         .          .           .            .            .

             x1n                                       + x2n                             + xmn      = bn,

xij  0, i = 1, . . . , m,  j = 1, . . . , n,


xij  0, i = 1, . . . , m,  j = 1, . . . , n,

Если в транспортной задаче выполняется условие

   

то она называется задачей закрытого типа. Транспортная задача закрытого типа всегда имеет решение.

Если в транспортной задаче суммарные запасы не совпадают с суммарными потребностями, то есть

                         

то она называется задачей открытого типа.

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

                       .

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

                       

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

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

Матрица планирования:           

Потреб                 ности

Поставщики

b1

b2

-

bn

а1

c11

c12

-

c1n

а2

аm

Cm1

Cm2

-

Cmn

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


Задача о назначениях

Имеется n работ (заданий) T1, T2, …, Tn и n человек M1, M2, … , Mn, каждый из которых способен выполнить любую работу. В силу различной квалификации на выполнение этих заданий им требуется различное время. Если cij - время, затрачиваемое i-м человеком на j-е задание, то как следует распределить людей по заданиям, чтобы минимизировать время выполнения?

Пусть xij - время участия i-го человека в выполнении j-го задания. Все xij  0.

Так как каждый человек должен быть задействован, a каждое задание полностью выполнено, то xij, i = 1, . . . , n,  j = 1, . . . , m,  должны удовлетворять следующим ограничениям:

x11 + x12 + . .. + x1n                                       = 1

                                   x21 + x22 + ...+ x2n                            = 1

. . . . . . . .   . . . .

                                                                    xn1 + xn2 + . . . + xnn   = 1

x11                             + x21      . . .              + xn1                             = 1

        x12                           + x22    . . .         + xn1                             = 1

. . . . . . . . . . .

                          x1n                          + x2n      . . .                 + xnn  = 1

z = c11x11+c12x12+ ... +cnnxnn  min



 

А также другие работы, которые могут Вас заинтересовать

30882. Эмоции 39 KB
  Эмоции ЭМОЦИИ чувства с лат. ЭМОЦИИ – проявление подсознательной деятельности. Эмоции выполняют две функции : сигнальную и регуляторную. Сигнальная функция – эмоции сигнализируют о полезности или вредности данного воздействия об успешности или не успешности выполняемого действия.
30883. Память 36 KB
  Память ПАМЯТЬ – это свойство ЦНС воспринимать фиксировать сохранять и воспроизводить полученную информацию А Наследуемая генетическая врожденная память 1. Другие наследуемые процессы Б Ненаследуемая индивидуальная приобретенная приобретенная память можно разделить по времени формирования: Мгновенная иконическая сенсорная Краткосрочная оперативная Долгосрочная долговременная МГНОВЕННАЯ иконическая сенсорная – объем ее большой срок хранения информации до 010050 секунд формируемый образ сенсорного происхождения представлен...
30884. Функциональная система 130 KB
  Афферентный синтез Принятие решения Акцептор результата действия Эфферентный синтез Целенаправленное действие Полезный приспособительный результат Обратная афферентация В центральной архитектонике функциональной системы условно выделяют несколько стадий: 1. Формирование акцептора результата действия и программы действия. Роль памяти проявляется в извлечении из нее наших знаний врожденных наследуемых и приобретенных о данном факте и варианты действия и прогноза формы способы достижения цели на основе имеющегося опыта...
30885. Звуковые проявления сердечной деятельности 22 KB
  Тоны. Ухом как правило выслушиваются I и II тоны. I тон систолический протяжный 007013 сек низкий в начале фазы изометрического сокращения. Компоненты тона звук захлопывающихся а в клапанов вибрация стенок желудочков и папиллярных мышц.
30886. Электрические проявления сердечной деятельности 45 KB
  Электрические проявления сердечной деятельности Деятельность сердца сопровождается рядом внешних проявлений: Механические 2. Векторкардиография метод регистрации направления электрической оси сердца в ходе сердечного цикла. В 1901 году Эйнтховен с помощью струнного гальванометра впервые зарегистрировал биотоки сердца. Кривая которую Эйнтховен назвал электрокардиограммой регистрировалась с поверхности сердца Тело человека является проводником 2го порядка ионная проводимость следовательно всякое биополе в т.
30887. Функциональная классификация кровеносных сосудов 30.5 KB
  Сердценасос ритмически выбрасывающий кровь в сосуды генератор давления и регулятор расхода крови 2. Сосуды эластического типа принимающие порцию крови за счет растяжения стенок обеспечивают непрерывный пульсирующий ток крови формируют в динамике систолическое и пульсовое давление в большом и малом кругах кровообращения определяют характер пульсовой волны. Сосуды мышечного типа вносят основной вклад в формирования сопротивлению тока крови существенно изменяют свой просвет под действием нервных и гуморальных влияний. Они краны ССС...
30888. Сосудистый тонус 47 KB
  Сосудорасширяющие: а неспецифические метаболиты непрерывно образуются в тканях и в месте образования они всегда препятствуют сужению сосудов а также вызывают их расширение метаболическая регуляция. Сосудосуживающие БАВ при действии в месте выделения образуются специализированными клетками которые входят в состав сосудистого окружения катехоламины серотонин некоторые простагландины эндотелии 1пептид 21на аминокислота продукт инкреции эндотелия сосудов а также тромбоксан А2 выделяемый тромбоцитами при...
30889. Системная гемодинамика 54.5 KB
  Венозный возврат крови к сердцу. Объем циркулирующей крови. Согласно законам гемодинамики количество жидкости Q протекающее через трубку прямо пропорционально разности давлений в начале P1 и в конце Р2 трубы и обратно пропорционально сопротивлению R току жидкости: Если учесть что давление в конце системы Р2 в устьях полых вен в правом предсердии центральное венозное давление близко к нулю то можно записать: где Q количество крови изгнанное сердцем за 1 мин; Ρ величина среднего давления в аорте; R величина общего...
30890. Методы оценки основных показателей гемодинамики 24 KB
  Методы оценки основных показателей гемодинамики Артериальное давление. Боковое измеряется некровавым косвенным методом: а пальпаторный метод РиваРоччи; б аускультативный метод Короткова; в осциллографический метод определяется количественно среднее давление а также систолическое и диастолическое давление. Метод позволяет оценить риск развития гипертонии ее тяжесть дать более точный прогноз развития болезни. Метод разведения красителя.