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



 

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

18716. Поясните структурные единицы ЭВМ – элементы, узлы, блоки, устройства 26.62 KB
  Поясните структурные единицы ЭВМ – элементы узлы блоки устройства. ЭВМ представляет собой некоторый комплекс взаимосвязанных устройств каждый из которых выполняет определенную функцию. Минимальная конфигурация компьютера т.е. такой набор элементов без которого ра...
18717. Учет финансовых результатов от реализации продукции (работ, услуг) 15.94 KB
  Учет финансовых результатов от реализации продукции работ услуг. Сводным интегрирующим показателем характеризующим фин. результат деятти предприятия является балансовая валовая прибыль или убыток. В современных условиях хоз. балансовая прибыль предприятия об
18718. Внешнее управление пакетом 15.48 KB
  Внешнее управление пакетом. Целью каждого применения ППП сеанса работы с пакетом является вычисление значений некоторых данных при условии что значения других данных известны. Для этого нужно привести модель в некоторое исходное состояние ввести или указать другим
18719. Информационные технологии обработки данных. Автоматизированный офис 14.71 KB
  Информационные технологии обработки данных. Автоматизированный офис. Информационная технология обработки данных предназначена для решения хорошо структурированных задач по которым имеются необходимые входные данные и известны алгоритмы и другие стандартные процед...
18720. Международное законодательство о защите прав и свобод 23.43 KB
  Международное законодательство о защите прав и свобод. Конвенция ООН о правах ребенка 1989. Конвенция о правах человека. Декларация тысячелетия ООН 08.09.2000 г.. Конституция РФ. Способы и технологии информирования молодежи о правах и свободах СМИ создание специальных цент
18721. Особенности организации работы с молодежью в развитых странах 23.99 KB
  Особенности организации работы с молодежью в развитых странах. Нормативноправое обеспечение. Специалисты осуществляющие работу с молодежью. Основные направления деятельности государственных и негосударственных структур реализующих молодежную политику. Рекоменда
18722. Специфика работы с молодежью в стране 18.96 KB
  Специфика работы с молодежью в стране по выбору. Основные проблемы и потребности молодежи. Особенности организации работы с молодежью. Основные приоритеты. Основные направления деятельности органов по делам молодежи. Разработка мероприятий соответствующих потребно
18723. Исторические этапы взаимодействия молодежи и общества 24.12 KB
  Исторические этапы взаимодействия молодежи и общества. Социальноисторические факторы влияющие на взаимоотношения молодежи и общества. Отношение к молодежи в традиционном индустриальном и постиндустриальном обществе объекты и субъекты взаимодействия сферы взаимо...
18724. Молодежь как социально-демографическая группа 27.13 KB
  Молодежь как социальнодемографическая группа. Индекс развития человеческого потенциала индекс развития молодёжи. Возрастные границы. Документы регламентирующие возрастные границы. Специфика социального статуса и социальноролевое поведение. Ценности и ценностные ...