Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Задача линейного программирования. Модифицирован симплекс-метод.

Изложение модифицированного симплекс-метода.

Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенаправленное перебирание ДБР, к множеству которых принадлежит оптимальное решение, если он существует; или определяет, что ЗЛП не имеет оптимального решения.

В МСМ в отличие от СМ симплекс-превращение применяются только к базисной части матрицы условий А.

Признак оптимума и условия отсутствия оптимального решения ЗЛП для МСМ и СМ одинаковые.

Алгоритм модифицированного симплекс-метода.

На s-у шаге МСМ выполняются такие действия:

1. Вычисляются относительные оценки (симплекс - разницы)

j[s]= cj (u[s], Aj)

где u[s]=cб[s]Воб[s] — вектор симплекс - множителей, Воб[s] — матрица, обратная к базисной, cб[s] — базисная часть вектора c. Если j[s]0 для всех j=1...,n, то конец: текущее базисное решение оптимальное. Если существует j такое, что j[s]<0, то перейти к пункту 2.

2. Выбирается k за формулой

k=argminj[s].

j: j[s]<0

Вычисляются векторы Ak[s]= Воб[s] Ak и A0[s]= Воб[s] A0.

Если Ak[s]0, то конец: целевая функция неограниченна снизу на допустимом множестве. Если существуют и такие, что aik[s]>0, то перейти к пункту 3.

3. Вычисляются отношения и[s]=ai0[s]/aik[s] для всех aik[s]>0 но выбирается l так, что

l=argminи[s].

и: aik[s]>0

Вектор Akпринадлежит ввести к базису, а вектор, что является базисным в lму непрямом ограничении, должен быть выведенным из базиса.

4. Матрица Воб[s+1] вычисляется за матрицей Воб[s]с помощью обычных симплекс - превращений с использованием ведущего элементаalk[s].Подобным образом может быть определен и векторA0[s+1]. Для КЗЛПВоб[0] — единичная матрица размерности mm.

Программное обеспечение.

Обучающий модуль, с помощью которого ЗЛП решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.

Задание.

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

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые.

1)

x1 x2 + 3x4 + x5  min

2)

3 x1 + x2 + x4 + x5  min

x1 + 2x2 + 3x3 + 3x4 + x5 = 15

2 x1 x2 + x4 x5 = 9

2 x1 x2 3x3 + x4 x5 = 4

4 x1 x2 x3 x5 = 4

2 x1 2x2 x3 + 2x5 = 8;

x1 x2 x3 x5 = 6;

3)

x1 2x2 + 2x3 + x4 + 2x5  max

4)

x1 + 2x2 + x3 x4  min

x1 + x2 2x3 + 3x4 + x5 = 2

x1 + 5x2 + x3 + x4 + x5 = 10

x1 + 2x2 x3 + 2x4 = 3

2x1 x2 + x3 3x4 = 6

2x1 + 3x2 + x4 x5 = 6;

10x2 + x3 + 2x4 + 3x5 = 25;

5)

x1 x2 + x3 + x4 x5  min

6))

x1 x2 + x3 + 2x4  max

x1 + x4 + 6 x5 = 9

x1 + x2 + x3 + 2x4 + 3x5 = 7

3 x1 + x2 4 x3 + 2 x5 = 2

x1 + 2x2 + 2x3 + 3x4 + 2x5 = 12

x1 + 2 x2 + 2 x5 = 6;

2x1 + 3x2 + 4x3 + 4x4 x5 = 22;

7)

x1 + 2 x2 x3 x4  min

8)

x1 x2 + x3 + x4 + x5 x6  min

x1 + x2 + 2 x3 x4 = 2

4x1 + x2 4x3 + x4 + 8x6 = 15

x1 + 2 x2 3 x3 + x4 = 6

4x1 + x2 2x3 + x5 + 4x6 = 8

x1 + x2 + x3 + x4 = 7;

5x1 + x2 2x3 + x4 + x5 + 10x6 = 21;

9)

x1 + 2x2 + 3x3 + x4 + x5  max

10))

x1 x2 + x3 3x4 + 2x5  min

x1 + x2 + 4x3 x4 + x5 = 1

x1 +2x2 x3 + 2x4 + x5 8

x1 + x2 2x3 + x4 + x5 = 1

x1 x2 + x3 3x4 2x5 = 10

x1 + x2 6x3 + x4 + x5 = 1;

2x1 x2 + 3x3 x4 + 2x5 4.

Ответы:

1) x* = (5.11; 3.67; 0; 0; 2.56), L(x*)= 4.

2) Решения нет ( D =  ).

3) Решения нет (целевая функция неограниченна сверху на допустимом множестве).

4) x* = (1; 0; 4; 0; 7), L(x*)= 5.

5) x* = (0; 1.5; 0.63; 0; 1.5), L(x*)= 2.38.

6) x* = (1; 0; 4; 1; 0), L(x*)= 7.

7) x* = (4.13; 0; 1.25; 2.62), L(x*)= 1.25.

8) x* = (0; 1; 0.83; 0; 0; 2.17), L(x*)= 2.33.

9) x* = (0; 1; 0; 0; 0), L(x*)= 2.

10) Решения нет ( D =  ).

Лабораторная работа 4.