Линейное программирование



страница4/10
Дата02.01.2013
Размер0.83 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8   9   10

.

Таблица-3.2

Базис

пер





A'0

с1

с2

.

cp



cm

cm+1



ck

.

cn










A1

A2

.

Ap



Am

Am+1



Ak

.

An

x1

c1

b'1

1

0



a'1,p



0

a'1,m+1



0

.


a'1,n

x2

c2

b2

0

1



a'2,p0



0

a'2,m+1



0k

.

a'2,n

























.



xk

ck

b'p

0

0



a'p,p



0

a'p,m+1



1

.

a'p,n

























.



xm

cm

b'm

0

0



a'm,p



0

a'm,m+1



0

.

a'm,n




Δ'0

0

0



Δ'p



0

Δ'm+1



0

.

Δ'n

3. j < 0 для некоторых индексов , и для каждого такого по крайней мере одно из чисел положительно.

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

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

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

После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения новых базисных переменных через новые свободные переменные. Это легко реализовать, если воспользоваться методом Гаусса. Положительные компоненты нового опорного плана вычисляются по формулам

(3.11)

Новые элементы , соответствующие новому опорному плану, вычисляются по формулам

(3.12)

После вычисления и по формулам (3.11)-(3.12) их значения заносят в таблицу 3.2. Элементы индексной строки этой таблицы могут быть вычислены либо по формулам

, (3.13)

либо на основании их определения.

Из формул (3.13) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис такую переменную , для которой максимальным (по абсолютной величине) является число . На практике направляющий столбец определяют, исходя из максимальной абсолютной величины отрицательных оценок . Если же таких чисел несколько, то в базис следует вводить переменную с таким номером , для которого значение коэффициента (при ) максимально.

Таким образом, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислять как с помощью рекуррентных формул (3.11)-(3.13), так и по правилам, непосредственно вытекающим из них. Эти правила можно найти, например в [4].

Итак, нахождение оптимального опорного плана симплексным методом включает следующие этапы:

  1. находят начальный опорный план;

  2. составляют симплекс-таблицу;

  3. выясняют, существует ли хотя бы одно отрицательное число .

Если нет, то найденный опорный план оптимален. Если же среди чисел есть отрицательные, то либо устанавливают неразреши-

мость задачи, либо переходят к новому опорному плану;

4) находят направляющий столбец и строку. Направляющий столбец определяется наибольшим по модулю отрицательным числом , а направляющая строка – минимальным из отношений компонент столбца к положительным компонентам направляющего столбца;

5) по формулам (3.11)-(3.13) определяют положительные компоненты нового опорного плана, новые компоненты столбцов и оценки и . Все эти числа записывают в новую симплекс-таблицу;

6) проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к пункту 4. Если же найденный опорный план оптимален или установлено, что задача неразрешима, то процесс решения задачи заканчивают.

4 Симплекс- метод решения ЗЛП с искусственным базисом

(М-метод)
Литература: [3], гл. 1, § 1.5; [4], гл. I, § 1.4.

Студент должен

знать:

  • алгоритм приведения ЗЛП к задаче с искусственным базисом;

уметь:

  • приводить ЗЛП к задаче с искусственным базисом;

  • решать ЗЛП симплекс- методом с использованием симплекс-таблицы.

Основные теоретические сведения
Выше было показано, что если ЗЛП записана в симметричной форме, то ее не трудно привести к предпочтительному виду и затем указать начальный опорный план задачи. Однако для многих задач, записанных в канонической форме, система ограничений не имеет предпочтительного вида, и непосредственно указать начальный опорный план не представляется возможным.

Пусть, например, в ЗЛП на максимум система ограничений имеет вид:

. (4.1)

Чтобы привести ее к каноническому виду, из левой части каждого неравенства системы (3.9) вычитают дополнительные переменные . В результате получится система ограничений вида:

. (4.2)

Эта система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть уравнений с коэффициентами, равными (-1).

Рассмотрим теперь каноническую задачу ЛП на максимум, в которой система ограничений не имеет предпочтительного вида.

(4.3)

Чтобы привести систему (4.3) к предпочтительному виду, к левым частям уравнений добавляют искусственные переменные . В целевую функцию переменные вводят с коэффициентом в случае решения задачи на минимум и с коэффициентом для задачи на максимум, где – большое положительное число. В результате исходная ЗЛП примет предпочтительный вид:

, (4.4)

(4.5)

, , , . (4.6)

Задача (4.4)-(4.6) называется расширенной по отношению к исходной задаче. Ее начальный опорный план можно выбрать в виде:

. (4.7)

Решение расширенной задачи может быть найдено симплексным методом. Если некоторые из уравнений исходной ЗЛП имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Справедливы теоремы.

Теорема 4.1. Если в оптимальном плане

(4.8)

расширенной задачи (4.4)-(4.6) все искусственные переменные , то план является оптимальным планом исходной задачи ЛП.

Теорема 4.2. Если в оптимальном плане расширенной задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Рассмотрим подробнее процесс решения расширенной задачи.

Для опорного плана расширенной задачи значения целевой функции и оценок равны

, . (4.9)

Таким образом, и состоят из двух независимых частей, одна из которых зависит от , другая – нет.

После вычисления и их значения, а также исходные данные расширенной задачи заносят в таблицу, которая содержит на одну строку больше, чем обычная симплекс-таблица. При этом в -ю строку помещают коэффициенты при из (4.9), а в -ю – слагаемые, не содержащие .

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

Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс в -ой строке продолжают до тех пор, пока не будет выполнено одно из следующих условий:

  1. все искусственные переменные исключены из базиса;

  2. среди базисных переменных есть искусственные, но в -ой

строке отсутствуют отрицательные значения, кроме, быть может, значения в столбце .

В первом случае базис отвечает некоторому опорному плану исходной задачи и поиск ее оптимального плана продолжают по -ой строке.

Во втором случае исходная задача не имеет решения, если значение, стоящее в -ой строке столбца отрицательно.

Таким образом, процесс нахождения решения канонической задачи ЛП методом искусственного базиса включает следующие основные этапы:

  1. составляют расширенную задачу (4.4)-(4.:6);

  2. находят начальный опорный план расширенной задачи;

  3. используя симплекс-метод, исключают искусственные переменные

из числа базисных. В результате, либо получают опорный план исходной задачи (4.3), либо устанавливают ее неразрешимость;

4) используя найденный опорный план задачи (4.3), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.
1   2   3   4   5   6   7   8   9   10

Похожие:

Линейное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Линейное программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование iconМатематическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Линейное программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Линейное программирование iconПараметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых...
Линейное программирование icon«Линейное программирование и симплекс метод»

Линейное программирование iconВопросы экзамена Методы оптимизации Раздел Линейное программирование
Алгоритм симплекс-метода без корректного вида базиса с искусственными переменными
Линейное программирование iconЛинейное программирование и симплекс метод
...
Линейное программирование iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Разместите кнопку на своём сайте:
ru.convdocs.org


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