Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Обращенный базис и симплекс-множители




Читайте также:
  1. БАЗИС И НАДСТРОЙКА
  2. Базис і надбудова та їх діалектичний зв'язок.
  3. Базисная стратегия предприятия
  4. Базисно-индексный метод расчета
  5. Базисное (недифференцированное) лечение мозгового инсульта
  6. Базисные средства манипулирования реляционными данными
  7. Базисные условия договора поставки.
  8. Базисные условия поставки
  9. Деревья. Остов графа. Цикловой базис графа
  10. Егер , , векторлары кеңістіктегі базис болса, онда кез келген векторын бір ғана жолмен былай жіктеп жазуға болады

Рассмотрим решение ЗЛП с точки зрения линейной алгебры. В матричном виде каноническая форма ЗЛП имеет вид:

, где ,

.

Представим матрицу A в виде «склеенных» двух матриц . Здесь матрица – матрица, состоящая из столбцов матрицы A, соответствующих переменным, которые в оптимальной таблице являются базисными. Матрица состоит из всех оставшихся столбцов. Предположим, известна матрица B–1. Умножим слева ограничения ЗЛП на матрицу B–1:

, здесь , следовательно,

, следовательно, , .

В невырожденном допустимом базисном решении (НДБР) базисным переменным соответствует единичная матрица, то есть . Так как A умножается на B–1, то , что соответствует матрице коэффициентов оптимальной таблицы. Следовательно, в оптимальной таблице в столбцах тех переменных, которые были базисными в НДБР находится матрица B–1.

Определение 4.1. Матрица, находящаяся в оптимальной таблице среди коэффициентов ограничений, стоящих в столбцах тех переменных, которые были базисными в исходной таблице, называется обращенным базисом и обозначается B–1.

Запишем ЗЛП в канонической форме с предпочтительными переменными:

.

Умножим каждое ограничение на некоторое число соответственно и сложим с выражением целевой функции, тогда получим:

. (4.1)

Значения можно подобрать таким образом, чтобы коэффициенты перед базисными переменными равнялись нулю. Без ограничения общности, например, первые m переменных являются базисными, тогда можно определить из системы:

.

Если предположить, что подобрали таким образом, что перед базисными переменными коэффициенты равны 0, а перед свободными – неотрицательны, то вид (4.1) будет соответствовать оптимальному виду таблицы. Следовательно, в оптимальной таблице коэффициенты в выражении целевой функции перед переменными, которые были базисными в исходной таблице, есть , при этом .

Определение 4.2. Симплекс-множители – это такие числа , при умножении на которые каждого ограничения соответственно и сложении с выражением целевой функции будет получен такой вид целевой функции, что перед базисными переменными коэффициенты равны нулю, а перед свободными – неотрицательны.

Замечание 4.1. Если не все коэффициенты свободных переменных в выражении целевой функции неотрицательны, то это симплекс-множители промежуточного решения.


Дата добавления: 2014-12-03; просмотров: 21; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.004 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты