Решение задач линейного программирования - файл n1.doc

приобрести
Решение задач линейного программирования
скачать (749 kb.)
Доступные файлы (1):
n1.doc749kb.01.06.2012 11:23скачать

n1.doc

  1   2   3   4   5   6



Содержание


1

1. Решение задачи ЛП 2

1.1 Геометрическая интерпретация двумерной задачи ЛП и ее решение 2

1.2 Решение задачи симплекс-методом 4

6

1.3 Двойственная задача ЛП 6

2. Экономическая интерпретация решения двойственной задачи 8

3 Транспортная задача 12

16

4 Задача целочисленного программирования 16

4.1 Метод ветвей и границ решения задачи о коммивояжере 16

4.2 Венгерский алгоритм решения задачи о назначениях 20

4.3 Метод Гомори 24

1. Решение задачи ЛП




1.1 Геометрическая интерпретация двумерной задачи ЛП и ее решение



Рассмотрим двумерную задачу:

а)





Каждое из ограничений представляет собой полуплоскость в системе координат Х1ОХ2, ограниченную соответствующей прямой. Множество всех точек плоскости, координаты которых удовлетворяют всем ограничениям, т.е. принадлежат сразу всем полуплоскостям, определяемым отдельными ограничениями, будет представлять собой допустимое множество. Изобразим допустимую область для данной задачи ЛП (рис. 1).

X2
8

3
2

1


X1

-8 6
-3


Рис. 1. Допустимая область задачи ЛП (1)
Мы хотим найти те точки допустимой области, координаты которых доставляют целевой функции наибольшее значение. Построим линию уровня целевой функции. Получим множество точек, в которых F принимает одно и то же значение a. Перемещая линию уровня в направлении вектора, нормального к линии уровня, будем получать в пересечении этой линии с допустимой областью точки, в которых целевая функция принимает новое значение, большее чем на предшествующих линиях уровня.

Пересечение допустимой области с линией уровня в том ее положении, когда дальнейшее перемещение дает пустое множество, и будет множеством точек максимума задачи линейного программирования. Перемещая линию уровня в направлении противоположном вектору n, найдем точки минимума (рис. 2).

X2


8

3




2

1
max




-8 min 6 X1
-3
Рис. 2. Решение задачи ЛП геометрически.

Таким образом получаем:






1.2 Решение задачи симплекс-методом


Для применения симплекс метода необходимо привести задачу (1) к каноническому виду:
(2)


В качестве базиса возьмем вектора А3 , А4 и А5.

Запишем первую симплекс-таблицу:


базис

Сбаз

В

5

4

0

0

0

A1

A2

A3

A4

A5

A3

0

6

1

-2

1

0

0

A4

0

8

-1

1

0

1

0

A5

0

10

1

1

0

0

1







0

-5

-4

0

0

0




хоп=(0; 0; 6; 8; 10).

Так как не все оценки , то опорный план не является оптимальным, критерий отсутствия решений также не выполняется.

Изменим базис: введем вектор А1, выведем вектор А5. Произведя перерасчеты, получим таблицу:


базис

Сбаз

В

5

4

0

0

0

A1

A2

A3

A4

A5

A3

5

6

1

-2

1

0

0

A4

0

14

0

-1

1

1

0

A1

0

4

0

3

-1

0

1







F=30

0

-14

5

0

0




хоп=(6; 0; 0; 14; 4).

Так как не все оценки , то опорный план не является оптимальным, критерий отсутствия решений также не выполняется.

Изменим базис: введем вектор А2, выведем вектор А1. Произведя перерасчеты, получим таблицу:


базис

Сбаз

В

5

4

0

0

0

A1

A2

A3

A4

A5

A3

5

8,66

1

0

0,33

0

0,66

A4

0

15,33

0

0

0,66

1

0,33

A1

4

1,33

0

1

-0,33

0

0,33







F=48,66

0

0

0,33

0

4,66


хоп=(8,66; 1,33; 0; 15,33; 0).

Так как все оценки , то данное опорное решение является оптимальным.

Окончательно, .

Используя программу «Симплекс-метод», получим аналогичный результат (рис. 3).



Рис. 3. Решение прямой задачи симплекс-методом
  1   2   3   4   5   6


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации