Файл: Содержание Теоретический раздел 4.doc

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 28.04.2024

Просмотров: 25

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.


Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

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

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

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

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

Из приведенного определения вытекает важное свойство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей.

((D*)*, (f*)*)≡(D, f),

Основные теоремы:

Теорема 1. Если одна из двойственных задач имеет конечный оптимум, то другая также имеет конечный оптимум, причем экстремальные значения целевых функций совпадают

Теорема 2 ( о дополняющей нежесткости). Для того чтобы план х* и у* являлись оптимальными решениями соответственно задач линейного программирования и двойственной к ним необходимо и достаточно, чтобы выполнялись следующие соотношения:





Теорема 3 (об оценках). Значение переменных в оптимальном решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)



2. Практический раздел

2.1 Решение транспортной задачи



На три базы: А1, А2, А3 поступил однородный груз в количествах : 120,150,100, соответственно. Груз требуется перевезти в пять пунктов:85 в пункт B1, 65 в пункт В2, 90 в пункт В3, 60 в пункт В4, 70 в пункт В5.

Спланировать перевозки так, чтобы общая их стоимость была минимальной.

Пункт отправления

В1

В2

В3

В4

В5

Запасы, аi

A1

7

4

15

9

14

120

A2

11

2

7

3

10

150

A3

4

5

12

8

17

100

Потребности,bj

85

65

90

60

70

370


Решение:

Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов




1

2

3

4

5

Запасы

1

7

4

15

9

14

120

2

11

2

7

2

10

150

3

4

5

12

8

17

100

Потребности

85

65

90

60

70






Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 120 + 150 + 100 = 370

∑b = 85 + 65 + 90 + 60 + 70 = 370

Занесем исходные данные в распределительную таблицу.




1

2

3

4

5

Запасы

1

7

4

15

9

14

120

2

11

2

7

2

10

150

3

4

5

12

8

17

100

Потребности

85

65

90

60

70




Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.




1

2

3

4

5

Запасы

1

7

4

15[50]

9

14[70]

120

2

11

2[65]

7[25]

2[60]

10

150

3

4[85]

5

12[15]

8

17

100

Потребности

85

65

90

60

70





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

2. Подсчитаем число занятых клеток таблицы
, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.




v1=7

v2=10

v3=15

v4=10

v5=14

u1=0

7

4

15[50]

9

14[70]

u2=-8

11

2[65]

7[25]

2[60]

10

u3=-3

4[85]

5

12[15]

8

17


Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (1;2): 4

Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».




1

2

3

4

5

Запасы

1

7

4[+]

15[50][-]

9

14[70]

120

2

11

2[65][-]

7[25][+]

2[60]

10

150

3

4[85]

5

12[15]

8

17

100

Потребности

85

65

90

60

70





Цикл приведен в таблице (1,2; 1,3; 2,3; 2,2; ).


Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.




1

2

3

4

5

Запасы

1

7

4[50]

15

9

14[70]

120

2

11

2[15]

7[75]

2[60]

10

150

3

4[85]

5

12[15]

8

17

100

Потребности

85

65

90

60

70





Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.




v1=1

v2=4

v3=9

v4=4

v5=14

u1=0

7

4[50]

15

9

14[70]

u2=-2

11

2[15]

7[75]

2[60]

10

u3=3

4[85]

5

12[15]

8

17


Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (2;5): 10

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».




1

2

3

4

5

Запасы

1

7

4[50][+]

15

9

14[70][-]

120

2

11

2[15][-]

7[75]

2[60]

10[+]

150

3

4[85]

5

12[15]

8

17

100

Потребности

85

65

90

60

70