Математический аппарат линейного программирования

ГОУ ВПО ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО- ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

 

КАФЕДРА ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ И МОДЕЛЕЙ

 

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И ПРИКЛАДНЫЕ МОДЕЛИ

 

 

                                   

Тема 2. Методы получения оптимальных решений

6 часов.

 

Подготовила преподаватель кафедры

Горбатенко Е.Н.

 (филиал в г. Владимире)

 

 

2008

Тема: Методы получения оптимальных решений

План

2.1 Основы линейного программирования.

2.1.1 Математический аппарат линейного программирования.

2.1.2 Различные формы записи задачи линейного программирования.

2.1.3 Графическое решение задачи линейного программирования, исследование случаев неразрешимости задачи.

2.1.4 Основы симплекс-метода, процедуры решения с естественным и искусственным базисом.

2.1.5 Особые случаи решения ЗЛП.

2.1.6 Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана.

2.2 Специальные задачи линейного программирования.

2.2.1 Экономико-математическая модель транспортной задачи.

2.2.2 Модели целочисленного линейного программирования (задачи о назначениях, инвестициях и т.п.)

2.3 Основные понятия и общие сведения о методах реализации моделей нелинейного программирования.

 

 

Основы линейного программирования.

Математический аппарат линейного программирования.

Для изучения оптимизационных моделей необходимы знания основных понятий и элементов высшей математики[ 3].

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

К элементарным преобразованиям относятся следующие:

1. Перестановка любых двух уравнений

2. Умножение обеих частей одного из уравнений на любое, отличное от нуля число.

3. Прибавление к обеим частям одного уравнения соответствующих частей другого, умноженных на любое, отличное от нуля число.

4. Вычеркивание нулевой строки.

 

Пример 1.     Решить методом Жордана-Гаусса систему линейных уравнений:

 а) 

Х₁ + Х₂ + 2Х₃ = -1

2Х₁ - Х₂ + 2Х₃ = -4

4Х₁ + Х₂ + 4Х₃ = -2

 

Решение:  Составим расширенную матрицу

 

 

1.   Переменная х₁ исключается из всех уравнений кроме первого.

Преобразуем первый столбец в единичный.

Для этого ко второй и третьей строкам прибавляем первую строку, соответственно умноженную на -2 и -4. Получим матрицу:

 

2.   Переменная х₂ исключается из всех уравнений кроме второго.

 Делим вторую строку на -3. Затем умножаем вторую строку на -1 и 3 и складываем соответственно с первой и третьей строками. Получим матрицу:

 

3.   Переменная х₃ исключается из всех уравнений кроме третьего.

Делим третью строку на «-2». Преобразуем третий столбец в единичный. Для этого умножаем третью строку на «-4/3» и «-2/3» и складываем соответственно с первой и второй строками. Получим матрицу:

 

откуда Х₁ = 1, Х₂ = 2, Х₃ = -2.

Пример 2.  Решить методом Жордана - Гаусса систему линейных уравнений:

 

 Х₁ + 2Х₂ + 2Х₃ + 22Х₄  - 4Х₅ = 11

 Х₁ +2Х₂ +  Х₃   + 16Х₄ - 4Х₅ = 9

 Х₁ + Х₂  +  Х₃  + 12Х₄  - 2Х₅ = 6

 

Решение:

Составим расширенную матрицу

 

 

1. Преобразуем первый столбец в единичный. Для этого ко второй и третьей строкам прибавляем первую строку, соответственно умноженную на «-1». Получим матрицу:

 

2. Преобразуем второй столбец в единичный. Умножаем третью строку на «-1» и меняем местами со второй строкой.

 

К 1- ой строке прибавляем 2-ую, умноженную на «-2».

3. Преобразуем третий столбец в единичный. Третью строку умножаем на «-1».

Ко 2-ой строке прибавляем 3-ю, умноженную на «-1».

Исходная система эквивалентна следующей системе уравнений:

Х₁ + 2Х₄  = 1

Х₂ + 4Х₄  - 2Х₅ = 3

Х₃ + 6Х₄ =  2

Система уравнений имеет бесконечное множество решений.

Общее решение имеет вид:

Х₁ = 1-2Х₄

Х₂ = 3-4Х₄ +2Х₅

Х₃ = 2-6Х_4.

переменные Х₁, Х_2, Х₃ являются основными,

Х₁, Х₂ – свободными.

Если свободные переменные Х₄ и Х₅ положить равными нулю, то получим первое базисное решение Х₁ = 1, Х₂ = 3, Х₃ = 2, Х₄ = 0, Х₅=0.

    Первое базисное решение имеет вид: (1, 3, 2,0,0).     

 

Общее число групп основных переменных, т.е. базисных решений не более, чем число сочетаний из n по m (n – число неизвестных, m – число основных переменных)

= = .

Если все компоненты базисного решения неотрицательны, то такое решение называется опорным.