Методы решения задач транспортного типа. Методы решения задач линейного и целочисленного программирования

Страницы работы

37 страниц (Word-файл)

Фрагмент текста работы

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

Таблица 2.1 - Симплекс – таблица для прямой задачи

Базисные переменные

Свободный член

Свободные переменные

X1

X2

Y1

88

8

11

8

8/11

1/11

Y2

88

11

8

-64

-64/11

-8/11

L

0

8

8

-64

-64/11

-8/11

Чертим новую таблицу (Таблица 2.2)с новым набором свободных переменных. Меняем местами x1 и y2. Элементы разрешающих строки и столбца заменяем элементами, стоящими в нижних частях тех же клеток предыдущей таблицы. В остальных клетках новой таблицы записываем алгебраическую сумму элементов, стоящих в верхних и нижних частях соответствующих клеток прежней таблицы.

Таблица 2.2 - Симплекс – таблица для прямой задачи


Базисные переменные

Свободный член

Свободные переменные

Y1

X2

Y1

42

-  7/10

78/10

420/78

-  7/78

10/78

X1

6

1/10

6/10

-252/78

  42/780

-  6/78

L

-42

-  7/10

18/10

-756/78

 126/780

-  18/78

Чертим новую таблицу (Таблица 2.3)  с новым набором свободных переменных. Меняем местами x2 и y1. Элементы разрешающих строки и столбца заменяем элементами, стоящими в нижних частях тех же клеток предыдущей таблицы. В остальных клетках новой таблицы записываем алгебраическую сумму элементов, стоящих в верхних и нижних частях соответствующих клеток прежней таблицы.

Таблица 2.3 - Симплекс – таблица для прямой задачи


Базисные переменные

Свободный член

Свободные переменные

Y1

Y2

Х1

264/57

-8/57

121/627

Х2

264/57

11/57

-8/57

L

-4224/57

-24/57

-264/627

Все элементы нижней строки новой таблицы отрицательны, значит оптимальное решение найдено. X1=264/57=4,6; X2=264/57=4,6; L=4224/57=74,1.

Результаты, полученные симплекс - методом и графически – близки.

Двойственный метод (Таблицы 2.4 – 2.6):

Решим задачу симплекс-методом. Для этого строим симплекс-таблицу и заполняем ее аналогично прямому методу, только работаем с уравнениями (5) – (7).

Таблица 2.4 - Симплекс – таблица для двойственной задачи

Базисные переменные

Свободный член

Свободные переменные

Y1

Y2

X1

8

8

11

8/11

8/11

1/11

X2

8

11

8

-64/11

-64/11

-8/11

L

0

88

88

-64

-64

-8

Таблица 2.5 - Симплекс – таблица для двойственной задачи

Базисные переменные

Свободный член

Свободные переменные

Y1

X1

Y2

8/11

8/11

1/11

   -192/627

-8/57

64/627

X2

24/11

57/11

-8/11

24/57

11/57

-8/57

L

-64

24

-8

  -6336/627

   -264/57

   2112/627

Таблица 2.6 - Симплекс – таблица для двойственной задачи

Базисные переменные

Свободный член

Свободные переменные

X2

X1

Y2

264/627

-8/57

121/627

Y1

24/57

11/57

-8/57

L

-4224/57

-264/57

-264/57

Y1=264/627=0,42; Y2=24/57=0,42; L=46464/627=74,1.

Результаты, полученные симплекс - методом и результаты, полученные графически – близки.

2.6 Математическая постановка задачи линейного целочисленного программирования (ЛЦП)

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

Таким образом, математическая модель задачи ЛЦП имеет следующий вид.

Найти минимальное значение линейной функции  ,

при ограничениях:

 где  – целые.

Задание для ЛЦП:

2.7 Графическая интерпретация задачи ЛЦП. Графический способ решения задачи ЛЦП

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

1.  Новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка является целой;

2.  Так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.

График 2.3 – Графический способ решения задачи ЛЦП

Так как мы решаем задачу максимизации, значит, оптимум находится в точке, при которой значение целевой функции максимально. Оптимальной является точка                 А (4,6; 4,6), .  

2.8 Решение задачи ЛЦП с помощью алгоритма Гомори

Находим опорное решение (п.2.5):

Таблица 2.7 - Симплекс – таблица для прямой задачи

Базисные переменные

Свободный член

Свободные переменные

X1

X2

Y1

264/57

-8/57

121/627

Y2

264/57

11/57

-8/57

L

-4224/57

-24/57

-264/627

X1=264/57=4,6

X2=264/57=4,6

L=4224/57=74,1

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

Решаем задачу линейного программирования с дополнительным условием. Составляем симплекс-таблицу.

Таблица 2.8 - Симплекс – таблица для метода Гомори


Базисные переменные

Свободный член

Свободные переменные

Y2

Y1

X2

264/57

-8/57

121/627

288/627

8/11

-67/627

X1

264/57

11/57

-8/57

-36/57

-1

8/57

Y3

36/57

11/57

-8/57

36/11

57/11

-8/11

L

-4224/57

-24/57

-264/627

864/627

24/11

-192/627

Таблица 2.9 - Симплекс – таблица для метода Гомори

Базисные переменные

Свободный член

Свободные переменные

Y3

Y1

X2

3192/627

8/11

57/627

X1

4

-1

0

Y2

36/11

57/11

-8/11

L

-45600/627

24/11

-456/627

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

Таблица 2.10 - Симплекс – таблица для метода Гомори


Базисные переменные

Свободный член

Свободные переменные

Y3

Y1

X2

3192/627

8/11

1/11

-1/11

-8/11

-1

X1

4

-1

0

0

0

0

Y2

36/11

57/11

-8/11

8/11

64/11

8

Y4

1/11

8/11

1/11

1

8

11

L

-45600/627

24/11

-456/627

8/11

64/11

8

Таблица 2.11 - Симплекс – таблица для метода Гомори

Базисные переменные

Свободный член

Свободные переменные

Y3

Y4

X2

5

0

-1

X1

4

-1

0

Y2

4

11

8

Y1

1

8

11

L

-72

8

8

Целочисленное решение найдено:

.

2.9. Найти решение задачи ЛЦП с помощью алгоритма ветвей и границ (алгоритм Ленг и Дойг).

Метод ветвей и границ:

Итерация 1:  , т.к. при условии  условия (2) выполняются. Основной список на 1 итерацию содержит одну задачу ЛП:

Задача 1 состоит из формул (1), (2) и (3).

Шаг 1: Выбираем первую задачу из основного списка.

Шаг 2: Решаем выбранную задачу и ищем оптимальное решение.

Базисные переменные

Свободные члены

Свободные переменные

Y1

Y2

X1

264/57

-8/57

121/627

X2

264/57

11/57

-8/57

L

-4224/57

-24/57

-264/627

X1=264/57=4,6

X2=264/57=4,6

L=4224/57=74,1

Так как полученное оптимальное решение нецелочисленное, то выбираем произвольно переменную – х1 и вносим в основной список 2 задачи  ЛП.

Задача 2: (1), (2),  

Задача 3: (1), (2),  

Принимаем целевую функцию в итерации 2 равной нулю и возвращаемся к шагу 1: .

Итерация 2:

Шаг 1: выбираем задачу №2.

Шаг 2: решаем задачу №2:

Она не имеет допустимого решения

Итерация 3:

Шаг 1: выбираем задачу №3.

Шаг 2: решаем задачу №3:

Базисные переменные

Свободные члены

Свободные переменные

Х1

X2

Y1

88

-32

8

-8

11

0

Y2

88

-44

11

-11

8

0

Y3

4

4

1

1

0

0

L

0

-32

8

-8

8

0

Базисные переменные

Свободные члены

Свободные переменные

Y3

X2

Y1

56

56/11

-8

-8/11

11

1/11

Y2

44

-448/11

-11

64/11

8

-8/11

Х1

4

0

1

0

0

0

L

-32

-448/11

-8

64/11

8

-8/11

Базисные переменные

Свободные члены

Свободные переменные

Y3

Y1

X2

56/11

-8/11

1/11

Y2

36/11

-57/11

-8/11

Х1

4

1

0

L

-800/11

-24/11

-8/11

X1=4

X2=56/11=5.09

W=800/11=72.72

Так как решение нецелочисленное, то выбираем переменную х2 , и вносим в основной список 2 задачи  ЛП.

Задача 4: (1), (2),  

Задача 5: (1), (2),  

Итерация 4:

Принимаем целевую функцию   и возвращаемся к шагу 1.

Шаг 1: выбираем задачу №4:

Шаг 2:  решаем выбранную задачу

Базисные переменные

Свободные члены

Свободные переменные

Х1

X2

Y1

88

-32

8

-8

11

0

Y2

88

-44

11

-11

8

0

Y3

4

4

1

1

0

0

Y4

5

0

0

0

1

0

L

0

-32

8

-8

8

0

Базисные переменные

Свободные члены

Свободные переменные

Y3

X2

Y1

56

-55

-8

0

11

-11

Y2

44

-40

-11

0

8

-8

Х1

4

0

1

0

0

0

Y4

5

5

0

0

1

1

L

-32

-40

-8

0

8

-8

Базисные переменные

Свободные члены

Свободные переменные

Y3

Y4

Y1

1

-8

-11

Y2

4

-11

-8

Х1

4

1

0

X2

5

0

1

L

-72

-8

-8

X1=4

X2=5

W=72

Найденное  оптимальное решение  является целочисленным, значит

Похожие материалы

Информация о работе