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

Приведение задачи к канонической форме

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. 1.1. Пример разработки модели задачи технического контроля
  3. I. 1.2. Общая постановка задачи линейного программирования
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  6. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  7. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  8. I. Ситуационные задачи и тестовые задания.
  9. I. Цель и задачи дисциплины
  10. I.5.3. Подготовка данных для задачи линейного программирования
  11. I.5.4. Решение задачи линейного программирования
  12. I.5.5. Просмотр и анализ результатов решения задачи

Задача линейного программирования записана в канонической форме, если она формулируется следующим образом.

Требуется найти вектор , доставляющий максимум линейной форме

(2.5)

при условиях

(2.6)   (2.7)

где .

То есть, в канонической форме ЗЛП обязательным является требование максимизации целевой функции (2.5), ограничения задачи должны быть записаны в виде системы линейных алгебраических уравнений (2.6) с неотрицательными правыми частями, а на искомые переменные должны быть наложены условия неотрицательности (2.7).

Нами сформулирована исходная ЗЛП (2.1) - (2.4):

(2.8)  
(2.9)   (2.10)

Для приведения поставленной нами ЗЛП (2.8)-(2.10) к канонической форме необходимо все ограничения (2.9)-(2.10) преобразовать к виду равенств с помощью введения дополнительных неотрицательных переменных.

Число ограничений задачи, приводящих к уравнениям вида (2.6) в нашем случае можно уменьшить, если преобразовать неравенства (2.10) к виду (2.7) используя замену переменных. Для этого перенесем свободные члены правых частей неравенств (2.10) в левые части и введём новые переменные

Выразим теперь старые переменные через новые

и подставим их в линейную форму (2.8) и систему неравенств (2.9). Получим

Раскрывая скобки и учитывая, что

(2.11)

запишем исходную задачу так:

(2.12)
(2.13)
(2.14)

Для записи неравенств (2.13) в виде уравнений введем неотрицательные переменные , добавляя их в левые части первых трёх неравенств со знаком плюс, а в левую часть последнего неравенства со знаком минус. Тогда задача (2.12) - (2.14) запишется в следующей эквивалентной форме:

 

(2.15)
. (2.16)

Задача (2.15), (2.16) и есть исходная ЗЛП в канонической форме.

 

Нахождение начального опорного плана

Метод последовательного улучшения плана (так называемый симплекс-метод), который применяется для решения сформулированной ЗЛП (2.15)-(2.16), предполагает знание некоторого исходного опорного плана. Однако, далеко не всегда такой начальный опорный план может быть указан без каких-либо вычислений. Это возможно лишь в случае, когда среди столбцов матрицы условий найдётся достаточное количество таких столбцов, из которых составится единичная матрица и эта матрица будет являться базисом искомого начального плана.

Если же такой возможности нет, то для построения начального опорного плана исходной ЗЛП (2.5)-(2.7) решается вспомогательная ЗЛП (так называемая задача) с расширенным вектором , состоящим из вектора исходной ЗЛП, дополненного искусственными неотрицательными компонентами Последние вводятся в систему ограничений (2.16) так, чтобы сформировался искусственный единичный базис.

Итак, начальный опорный план задачи (2.5) - (2.7) может быть найден с помощью следующей вспомогательной ЗЛП (L - задачи):

(2.17)
(2.18)
(2.19)

Так как матрица условий ЗЛП (2.17)-(2.19) уже содержит единичную подматрицу которая может быть взята в качестве базиса опорного плана, то начальным опорным планом этой задачи будет являться вектор

,

у которого небазисные компоненты а базисные

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

Пуст - оптимальный опорный план задачи, у которого все искусственные компоненты равны нулю. Тогда вектор является опорным планом исходной задачи. Действительно, все дополнительные переменные . Значит, компоненты вектора удовлетворяют ограничениям исходной задачи, т.е. вектор является некоторым планом задачи (2.5) - (2.7). По построению план является также опорным.

 

Постановка L - задачи

В нашем случае ЗЛП (2.15)-(2.16) имеет матрицу условий

Она уже содержит три столбца которые можно использовать для построения единичного базиса. Недостаёт лишь одного столбца. Поэтому в нашем случае следует ввести только одну неотрицательную искусственную переменную в левую часть четвёртого уравнения системы ограничений (2.16). Тогда вспомогательная задача для нахождения начального опорного плана задачи (2.15) - (2.16) запишется так:

(2.20)
(2.21)

Определим начальный опорный план полученной задачи. При постановке этой задачи сформирован единичный базис искомого начального опорного плана задачи. Его компоненты являются небазисными и поэтому приравниваются нулю. Тогда из системы ограничений (2.21) найдутся значения базисных компонент

Итак, в качестве начального опорного плана задачи может быть взят вектор

Решение L - задачи

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

Для заполнения -й строки симплекс-таблицы вычислим значения линейной формы и оценок , векторов условий по приведённым в описании первого алгоритма формулам (см. раздел 4) следующим образом:

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

Заполняем таблицу 0-й итерации.

Среди оценок имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису путём операции однократного замещения. В базис будет введён вектор с наименьшей оценкой . Значения вычисляются для всех позиций столбца (так как все элементы разрешающего столбца положительны). Наименьший элемент достигается на четвертой позиции базиса. Значит, четвертая строка является разрешающей строкой, и вектор подлежит исключению из базиса.

Составим таблицу, отвечающую первой итерации.

В столбце , в четвертой позиции место вектора займёт вектор . Соответствующий ему коэффициент линейной формы помещаем в четвертой позиции столбца . Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как после завершения первой итерации все оценки , то полученный опорный план является оптимальным опорным планом L - задачи. Максимальное значение линейной формы задачи равно нулю .


Таблица 2.1

0 итерация

                  -1  
                        12 3/4
                        8 4/15
                        6 5/8
  -1                 -1   1 2/3
m+1 - - -50 -22 -14 -18 -30            

1 итерация

    44 1/3 1/15 3 2/15 -2/5         2/15 -2/15  
                      -1  
    79 1/3 -1 11/15 6 8/15 -1 3/5         8/15 -8/15  
    1 2/3 11/15 7/15 3/5         -1/30 1/30  
m+1 - -                      

Формирование начального опорного плана исходной ЗЛП

Искусственная компонента найденного в п.3.2 оптимального опорного плана задачи равна нулю =0. Поэтому, как видно из сравнения ограничений (2.21) и (2.16), компоненты удовлетворяют ограничениям исходной ЗЛП. Следовательно вектор является планом исходной задачи (2.15) – (2.16). Кроме того, он является также опорным планом. Поэтому он может быть выбран в качестве начального опорного плана задачи (2.15) – (2.16).

Таким образом найден начальный опорный план исходной ЗЛП: .

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)