2 Симплекс-метод и его модификации 2 Симплекс-метод



Скачать 123.29 Kb.
Дата08.10.2012
Размер123.29 Kb.
ТипРешение
2.2. Симплекс-метод и его модификации

2.2.1. Симплекс-метод

Решение задачи ЛП (3) , согласно теоремам 2, 3, 4, достигается в вершине многогранного множества. Теорема 2 дает простое описание вершин и способ их определения при известном базисе. Число вершин конечно. Минимум задачи может быть найден за конечное число шагов посредством перебора вершин.

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

(c Rn, A Rm x n). (4)

Пусть на k-ом шаге получена точка , являющаяся вершиной множества F, и пусть Ik = { i: xik > 0 }.

Назовем x невырожденной вершиной множества F, если число положительных компонент в ней равно m .

Предположим, что все вершины множества F невырождены. В силу невырожденности множество Ik содержит m элементов. Разобьем вектор x Rn на две группы x = {u,v}, где u Rm отвечает компонентам из , v Rn-m - компонентам, не принадлежащим Ik. Тогда система Ax = b может быть записана в виде :

A1u + A2v = b, (5)

где A1 Rm x m , столбцы которой являются столбцами A с индексами из , A2 Rm x (n-m) -матрица, составленная из оставшихся столбцов. Отсюда, в силу невырожденности матрицы A1,

(6)

Целевая функция приобретает вид :

(c,x) = (c1,u) + (c2,v) , (7)

где c1 Rm- вектор с компонентами , gif" name="object9" align=absmiddle width=31 height=21>, c2 Rn-m -вектор с компонентами cj, j Ik. С учетом (6) целевая функция может быть выражена только через v.



Следовательно, исходная задача эквивалентна следующей

, (8)

При этом точке xk соответствует вектор (uk,vk), где uk > 0, vk = 0. Точка vk = 0 является допустимой для задачи (8) при ограничении удовлетворяется как строгое неравенство . Поэтому оно может быть отброшено (как неактивное) при анализе точки vk на оптимальность.

В задаче

min( d, v ), v 0 (9)

минимум достигается в 0 тогда и только тогда, когда d 0.

Итак, если

(10)

то точка v = 0 является решением (3) и одновременно (8), а тем самым xk является решением (4). Если же среди компонент d есть отрицательные (например, dj < 0 ), то v = 0 не является решением (9), и, увеличивая vj, можно уменьшить значение целевой функции в (9).

Итак, сделаем шаг

Vk+1 = vk + k ej j: dj < 0 ej - j-й орт. (11)

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

(12)

Если при этом k = , то задача не имеет решения в силу бесконечного убывания функции. Если же k < , то получаем новую точку xk+1 = {uk+1,vk+1}, где vk+1 = vk + k ej. Эта точка вновь является вершиной (она допустима и имеет m положительных компонент, так как j-я компонента стала положительной, а одна из компонент uk+1 обратилась в 0).

Поэтому в ней можно повторить всю процедуру заново. При этом значение целевой функции уменьшилось. Следовательно, возврат в одну из точек невозможен. В силу конечности общего числа вершин метод конечен.

Условия (10) являются условием оптимальности в симплекс-методе.

2.2.2. Симплекс- метод при заданном начальном БДР

Пусть БДР задачи (4) соответствует переменным x1,…,xm. Тогда ограничения задачи (4) могут быть преобразованы к виду



(13)

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



Тогда векторы u и v предыдущего параграфа можно выразить через x следующим образом :

u = (x1,…,xm), v = (xm+1,…,xn)

Согласно (10), вектор критерия оптимальности d может быть получен посредством преобразования первоначальной целевой функции, записанной в виде уравнения

c1x1 + c2x2 + … + cnxn = Z.

Из этого уравнения вычитаются уравнения ограничений, умноженные соответственно на c1,c2,…,cm . В результате будет получено новое уравнение

(14)

где . Эта процедура соответствует исключению переменных x1,x2,…,xmиз целевой функции посредством равенств ограничений. Коэффициенты левой части полученного уравнения - это компоненты вектора критерия оптимальности

Пример. Решить задачу (4).

Набор x1 = x2 = 0, x3 =1700, x4 =1600 является БДР. Функция Z, имеющая нулевое значение, выражена через небазисные переменные. Коэффициенты при x1 и x2 отрицательные. Так как коэффициент при x2 больше по модулю, выберем переменную x2 для изменения. Существует предел изменения переменной x2 поскольку ограничения (4) должны выполняться, и переменные x3,x4 оставаться неотрицательными.

Поскольку 3x1 + 4x2 + x3 = 1700, то x3=0 при x2=1700/4=425.

Поскольку 2x1 + 5x2 + x4 = 1600, то x4=0 при x2=1600/5=320.

Поэтому x2 = 320 = min { 425, 320 }.

Этот итерационный процесс удобно представить в симплекс- таблицах

итерация


базис











операции над строками

0


-z

0

-2

-4

0

0







1700

3

4

1

0







1600

2

5 *

0

1



























1

-z

1280

-2/5

0

0

4/5







420

7/5 *

0

1

-4/5








320

2/5

1

0

-1/5




























2

-z

1400

0

0

2/7

4/7








300

1

0

5/7

-4/7








200

0

1

-2/7

3/7






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

Рассмотрим симплекс-метод в таблицах. Предположим, что на некоторой произвольной итерации задача ЛП представлена в форме (14), (13), а коэффициенты внесены в таблицу:

базис

значение





...



...





...



...



-z



0

0

0

0

0

0















1

0

0

0

0

0

0















0

1

0

0

0

0

0















0

0

1

0

0

0

0






















































0

0

0

0

0

0

1














Итерационный процесс состоит из трех шагов.

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

Переменные xm+1,…,xn небазисные. Находим наименьший из коэффициентов . Пусть это коэффициент . Если , то увеличение xs приведет к убыванию функции z. Будем выбирать столбец с наименьшими значениями . Если все , то значение функции не может быть уменьшено, решение найдено.

2. Найти переменную для исключения из базиса. Следует найти для каждой базисной переменной величину, на которую можно увеличить xs не нарушая условия неотрицательности Чтобы не нарушалось условие неотрицательности ни для одной базисной переменной следует выбрать



Если этот минимум достигается в строке r , то xr обращается в 0. Другие базисные переменные останутся неотрицательными. Элемент называется ведущим элементом, строка r - ведущей строкой, столбец s - ведущим столбцом.

3. Построить новую форму задачи типа (14), (13) для базисных переменных.

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

2.2.3. Двухэтапный симплекс-метод.

Точку, являющуюся вершиной допустимого множества F, можно найти с помощью метода искусственного базиса. Введем дополнительные переменные zi , играющие роль невязок в ограничениях, и рассмотрим задачу их минимизации

(14)

В этой задаче искомым является вектор {x,z} Rn+m, а точка {0,b} Rn+m является вершиной. При этом предполагается, что сменой знака ограничений достигнуто неравенство b 0. Для (14) можно применять симплекс-метод. В результате получим точку {x0,z0} где z0 = 0 либо z0 0. Если z0 = 0, то решение получено. Если z0 0, то не имеется БДР исходной задачи.

При решении может возникнуть ситуация z0 = 0, но некоторые из переменных zi не выведены из базиса. В этом случае следует:

1) выбрать в строке, соответствующей нулевой искусственной переменной, ненулевой элемент, а соответствующий ему столбец объявить базисным.

2) повторить процедуру вывода искусственных переменных пока не будут удалены из базиса все переменные z.

При решении задачи двухэтапным симплекс-методом образуется две нулевые строки. Одна из них получается преобразованием коэффициентов искусственной целевой функции W, которая минимизируется на I-ом этапе. Вторая - создается на основе целевой функции Z, подлежит преобразованию на всех этапах и используется для выбора базисной переменной на втором этапе.

Похожие:

2 Симплекс-метод и его модификации 2 Симплекс-метод icon«Линейное программирование и симплекс метод»

2 Симплекс-метод и его модификации 2 Симплекс-метод iconСимплекс-метод – группа Р443 – задания 1-10

2 Симплекс-метод и его модификации 2 Симплекс-метод iconСимплекс-метод – группа Р442 – задания 1-10

2 Симплекс-метод и его модификации 2 Симплекс-метод iconСимплекс-метод – группа Р441 – задания 1-10

2 Симплекс-метод и его модификации 2 Симплекс-метод iconЗадачи линейного программирования большой размерности Симплекс метод

2 Симплекс-метод и его модификации 2 Симплекс-метод iconДвойственный симплекс-метод
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
2 Симплекс-метод и его модификации 2 Симплекс-метод iconДвойственный симплекс-метод
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
2 Симплекс-метод и его модификации 2 Симплекс-метод iconДвойственный симплекс-метод
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
2 Симплекс-метод и его модификации 2 Симплекс-метод iconЛинейное программирование и симплекс метод
...
2 Симплекс-метод и его модификации 2 Симплекс-метод iconУравнений (5) линейно независима, т е. что r = m
Симплекс-метод доставляет вычислительную схему перехода от вершины к вершине (от одного базисного решения к другому) в нап­равлении...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org