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



 

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

33477. Виправні роботи 26 KB
  57 КК застосовуються до особи за місцем роботи на строк визначений за вироком суду з відрахуванням у доход держави відповідного відсотка її заробітку. Виправні роботи призначаються на строк від шести місяців до двох років і обов'язково супроводжуються відрахуванням із суми заробітку засудженого у доход держави в розмірі встановленому вироком суду в межах від десяти до двадцяти відсотків заробітку засудженого. Виправні роботи це покарання яке широко застосовується на практиці.
33478. Громадські роботи 24.5 KB
  56 КК полягають у виконанні засудженим у вільний від роботи чи навчання час безоплатних суспільне корисних робіт вид яких визначають органи місцевого самоврядування. Громадські роботи встановлюються на строк від шістдесяти до двохсот сорока годин і відбуваються не більш як чотири години на день.
33479. Звільнення від кримінальної відповідальності 26 KB
  Перебіг давності переривається в разі ухилення особи від органу досудового розслідування або суду або в разі вчинення іншого злочину середньої тяжкості тяжкого чи особливо тяжкого. Давність не застосовується в разі вчинення таких злочинів: ст.
33480. Територія України 29.5 KB
  6 КК де зазначено що особи які вчинили злочини на території України підлягають кримінальній відповідальності за цим Кодексом. б КК злочин визнається вчиненим на території України якщо його було почато продовжено закінчено або припинено на території України незалежно від того де особу було віддано до суду в зв'язку з його вчиненням. Зазначене положення охоплює як випадки вчинення всього діяння на території України так і випадки вчинення діяння як на території України так і на території інших держав. Поняттям територія України...
33481. Принципи чинності кримінального закону у часі 30.5 KB
  За загальним правилом закон про кримінальну відповідальність набирає чинності через десять днів з дня його офіційного оприлюднення. При цьому під опублікуванням закону про кримінальну відповідальність треба розуміти опублікування його в офіційному друкованому виданні.Зворотна дія закону про кримінальну відповідальність. Закон про кримінальну відповідальність який скасовує злочинність діяння або помякшує кримінальну відповідальність має зворотну дію у часі тобто поширюється на осіб що вчинили відповідні діяння до набрання таким законом...
33482. Ексцес виконавця 26 KB
  Ексцес виконавця вчинення виконавцем злочину дій які не охоплюються умислом інших співучасників якщо його дії утворюють самостійний склад злочину або його дії суттєво відрізняються від дій запланованих іншими учасниками. Кількісний ексцес має місце там де виконавець учинив однорідний злочин але більш тяжкий ніж було заплановано співучасниками наприклад вчинив розбій замість крадіжки. В цьому разі виконавець несе відповідальність за статтею що передбачає покарання за фактично вчинений ним злочин а співучасники несуть...
33483. Загальні засади призначення покарання 28 KB
  Інакше кажучи яка б кримінальна справа не розглядалася яке б покарання не призначалося винному суд зобов'язаний виходити з цих загальних критеріїв. 65 загальні засади призначення покарання складаються з таких трьох критеріїв. Суд призначає покарання: 1 у межах встановлених у санкції статті Особливої частини КК що передбачає відповідальність за вчинений злочин; 2 відповідно до положень Загальної частини КК; 3 враховуючи ступінь тяжкості вчиненого злочину особу винного та обставини що пом'якшують та обтяжують покарання.
33484. Звільнення від відбування покарання з випробуваннями 41.5 KB
  Відомий багато років нашому праву інститут засудження з випробуванням умовне засудження і відстрочка виконання вироку трансформований новим КК в один із видів звільнення від відбування покарання звільнення від відбування покарання з випробуванням. 75 КК зазначено якщо суд при призначенні покарання у виді виправних робіт службових обмежень для військовослужбовців обмеження волі а також позбавлення волі на строк не більше п'яти років враховуючи тяжкість злочину особу винного та інші обставини справи дійде висновку про можливість...
33485. правових відносин між особою яка вчинила злочин і державою. 27.5 KB
  Прийняття судом рішення про звільнення особи від кримінальної відповідальності є актом що свідчить про припинення кримінальноправових відносин між особою яка вчинила злочин і державою. Тобто вчинене раніше нею діяння визнається юридичне незначним підлягає забуттю залежно від того правом чи обов'язком суду є звільнення особи від кримінальної відповідальності виділяють два види такого звільнення: обов'язкове і. Факультативним є звільнення передбачене ст. Звільнення особи від кримінальної відповідальності може бути безумовним і умовним.