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



 

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

50174. Захист проти швидкого розгортання нападу, поступового розгортання нападу 24 KB
  Командна тактика в захисті зводиться до організації колективної взаємодії котра дає змогу успішно відбивати атаки суперника і після цього переходити в наступ. Якщо суперник починає активне маневрування потрібно щільно закрити своїх підопічних або протидіяти розвитку атаки в зонах. Якщо ж напад ведеться по флангу вони переміщуються в бік напрямку атаки. Гравці оборони концентруються в напрямку атаки чи розосередження нападників по фронту й активно беруть участь у боротьбі за мяч з неодмінною організацією страховки.
50176. Национальная экономика 474.07 KB
  Национальная экономика — саморегулирующаяся система, состоящая из большого числа взаимосвязанных различных видов деятельности. Следовательно, она должна давать возможность участия людей в этом производстве и получения каждым человеком, соответствующего его вкладу, доле национального продукта и дохода.
50177. Нечеткая логика 67 KB
  Согласно заданным вариантам разработать программу на любом алгоритмическом языке, способную: А. Различать степени изменения лингвистической переменной в трех степенях – «Очень – Нормально – Слабо» Б. Изменять порог чувствительности. 1. Пояс – мини – миди (женские юбки)
50178. Программирование задач с использованием структур 38 KB
  Создать и ввести массив из структур типа student размер массива произвольный и выполнить задание согласно варианту: Распечатать анкетные данные студентов отличников. Распечатать анкетные данные студентов успевающих на 4 и 5. Распечатать анкетные данные студентов имеющих одну 3. Распечатать анкетные данные студентов имеющих двойки.
50179. Дослідження власних коливань у коливальному контурі 82 KB
  Мета роботи: дослідити залежність періоду коливань у коливальному контурі від ємності конденсатора й індуктивності котушки а також залежність логарифмічного декременту згасання від величини активного опору. Змінюючи частоту генератора розгортки обертанням ручок діапазони частот частота плавно й амплітуда синхронізації домогтися на екрані осцилографа стійкої осцилограми зображення одного цугу згасаючих коливань див. Змінюючи L C і R простежити за характером зміни згасаючих коливань.
50180. Обонятельный анализатор – периферический и центральный отделы. Причины нарушения функции. Профилактика нарушений 15.44 KB
  Проводниковый отдел обонятельного анализатора представлен обонятельным нервом, волокна которого проходят через отверстия решетчатой кости в полость черепа, где они заканчиваются на клетках обонятельной луковицы.
50181. Персональний захист. Зонний захист. Комбінований захист. Тактична підготовка футболіста 27 KB
  Під теоретичною підготовкою футболістів слід розуміти навчання системи знань необхідних для ведення гри. При підготовці до проведення теоретичних занять з юними футболістами вчителю рекомендується: а визначити методичну форму проведення теоретичного заняття бесіда опитування розбір гри чи настанови; б визначити кількість часу для даної теми; в підготуватися до проведення заняття склавши короткий конспект. Учням пояснюють окремі компоненти гри дії футболіста в атаці обороні взаємодії в різних ситуаціях. Особливе місце в...
50182. Программирование задач с использованием структур в функциях, работа с файлами и структурами 63 KB
  Приобрести практические навыки в проектировании структуры файла а также закрепить навыки по вводу данных в файл и их обработке с помощью подпрограмм пользователя.y; } В программе которая выполняет операции чтения из файла или запись в файл должна быть объявлена переменнаяуказатель на тип FILE: FILE file_pointer; Для того чтобы файл был доступен его надо открыть указав для выполнения какого действия открывается файл: чтения записи или обновления данных а также тип двоичный или текстовый: Возможные режимы открытия файлов...