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



 

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

31703. Класифікація конфліктів, причини їх виникнення. Методи вирішення конфліктів 80 KB
  Цей стиль полягає в тому що людина намагається відійти від конфлікту. Цей стиль характерний такою поведінкою яка диктується переконанням що не варто злитися. Цей стиль є ефективним у ситуаціях коли керівник має велику владу над підлеглими. Цей стиль характеризується прийняттям погляду але тільки до певної межі.
31704. Авторитет вчителя 80.5 KB
  Досвід переконує що вплив вчителя на учня успішна його педагогічна діяльність залежить від авторитету вчителя. Авторитет сам приходить чи за нього треба боротись Якщо треба боротися то кому Авторитет не дається звичайно разом з дипломом про закінчення інституту. Одне з найважливіших значень в оцінці педагога має авторитет викладача як одне із складових ознак професійного педагога. Авторитет викладача це інтегральна характеристика його професійної педагогічної та особистісної значущості в колективі яка виявляється через взаємини з...
31705. СТРУКТУРА ПЕДАГОГІЧНОГО СПІЛКУВАННЯ 42.5 KB
  Моделювання педагогом майбутнього спілкування прогностичний етап. У цей час окреслюються контури майбутньої взаємодії: планування і прогнозування змісту структури засобів спілкування. Зміст спілкування формування мети взаємодії для чого аналіз стану співрозмовника чому він такий і ситуації що сталося.
31706. Учнівський колектив 30 KB
  Ціль колективу обов'язково повинна збігатися з суспільними цілями не суперечити пануючій ідеології конституції і законам держави. Єдиний шкільний колектив складається з колективу педагогів і загального колективу учнів. Учнівський колектив має органи управління: загальні збори учнівський комітет і рада колективу комісії штаби; у первинних колективах також працюють загальні збори та інші органи самоуправління обираються уповноважені особи та ін. Наявність у відносинах між членами колективу певної моральнопсихологічної єдності яка терпима...
31708. Складові психології спілкування 47 KB
  Складові психології спілкуванняСпілкування завжди займало важливе значення в житті людини. Хоч людське спілкування належить до основи соціального буття безпосереднім обєктом психологічного та соціальнопсихологічного аналізу воно постало лише в ХХ столітті. Спілкування дуже складний та многогранний процес. Паригіна “Основи соціально психологічної теоріїâ€ автор відзначив що процес спілкування може виступати як процес взаємодії людей як інформаційний процес як відношення людини до оточуючих як процес впливу один на одного а...
31710. Основні види діяльності 59 KB
  У дошкільному віці провідним різновидом діяльності є гра у шкільному навчання а в зрілому праця. Гра та навчання властиві і людям і тваринам. Але вона відрізняється від навчання та праці.
31711. Колектив як соціокультурне середовище виховання і розвитку 52.5 KB
  Емоціональний рівень ввзаємодії в колективі відображає домінуючі емоціональні стани дітей їх спільні переживання стосунки симпатій чи антипатій між членами колективу гуманістичні та суспільно значимі мотиви. Ініціатива творча позиція особистості зростання самостійності і самоуправління дітей ціннісний зміст їх спільної діяльності є індикаторами виховного потенціалу дитячого колективу. Підходи до розробки колективу та індивідуальності. Погляди на проблеми колективу відобразили сутність суспільних культурноісторичних процесів розвитку...