Найти графически максимум и минимум целевой функции

  • ID: 11373 
  • 22 страницы

Фрагмент работы:

ЗАДАНИЕ 2.2

Найти графически максимум и минимум целевой функции.

Условие.

Решение.

Найдем графический максимум и минимум целевой функции следующей ЗЛП:

Выберем в качестве свободных переменных и и выразим через них базисные пере-менные, и (целевая функция уже выражена через и ):

(2.1)

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

Из рисунка (2.1) следует, что точкой максимума будет точка С, а точкой минимума точка Е.

Запишем решение:

Max:…

Min:…

Рис. 2.1

ЗАДАНИЕ 2.54

Решить задачу симплекс-методом.

Условие.

Решение. Приведем математическую модель исходной задачи к каноническому виду, выбрав в качестве свободных переменные и, а введенные переменные в ка-честве базисных.

По полученным уравнениям составим симплекс-таблицу.

Базисные переменные Свободный член Свободные переменные

Базисные переменные Свободный член Свободные переменные

Базисные переменные Свободный член Свободные переменные

Ответ.…

ЗАДАНИЕ 2.103

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

Условие.

25 1 22 19 1 20

21 28 11 4 3 20

26 29 33 26 24 20

21 10 3 29 27 20

19 19 19 19 4 80

Решение. Составим опорный план диагональным методом

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Опорный допустимый план, полученный с помощью диагонального метода:

Составим опорный план методом наименьшей стоимости

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Опорный допустимый план, полученный с помощью метода наименьшей стоимости:…

Составим опорный план модифицированным диагональным методом:

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Опорный допустимый план, полученный с помощью модифицированного диагонального метода:

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

…принимаем

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Определим для всех свободных клеток величину - цену цикла пере-счета.

…...

Так как имеются отрицательные величины, то полученный план не является оптималь-ным. Выполним перераспределение груза. Для этого заполним клетку (4, 2).

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Получим новый опорный план.

Определим для всех свободных клеток…- цену цикла пересчета.

Так как имеются отрицательные величины, то полученный план не является оптималь-ным. Выполним перераспределение груза. Для этого заполним клетку (3,5).

Получим новый опорный план.

Определим для всех свободных клеток…- цену цикла пересчета.

Так как отрицательных величин нет, то полученное решение оптимально:

Найдем оптимальный план транспортной задачи по критерию стоимости с помощью распределительного метода. Для этого проверим цены циклов.

так как цена цикла отрицательна, то по выбранному циклу передвигаем наименьшую перевозку. Получаем новый опорный план

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Проверяем цены циклов:

цена цикла

ПН

ПО B1 B2 B3 B4 B5 Запасы аi

Проверяем цены циклов:

Таким образом, цены всех оставшихся циклов все положительны. Следовательно, полученное решение является оптимальным:

ЗАДАНИЕ 2. 154

Решить задачу о назначениях на максимум и на минимум венгерским методом.

Условие.

5 13 6 10 13 8 9

10 9 7 11 8 12 11

11 5 8 12 4 18 4

12 6 9 8 5 8 5

9 4 4 5 6 6 7

11 8 7 4 7 3 8

6 5 8 12 13 9 14

Решение. Решим задачу о назначениях на максимум венгерским методом.

5 13 6 10 13 8 9

7 0 3 2 0 10 5

10 9 7 11 8 12 11 2 4 2 1 5 6 3

11 5 8 12 4 18 4 1 8 1 0 9 0 10

12 6 9 8 5 8 5

0 7 0 4 8 10 9

9 4 4 5 6 6 7 3 9 5 7 7 12 7

11 8 7 4 7 3 8 1 5 2 8 6 15 6

6 5 8 12 13 9 14 6 8 1 0 0 9 0

Подготовительный этап Подготовительный этап

Число независимых нулей равно семи, т.е оптимальное решение задачи о назна-чениях на максимум:

Решим задачу о назначениях на минимум венгерским методом.

Число независимых нулей равно семи, т.е оптимальное решение задачи о назна-чениях на минимум:

ЗАДАНИЕ 3.2

Решить задачу методом целочисленных форм и методом ветвей и границ.

- целые числа.

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

Получено оптимальное решение задачи без условия целочисленности:

Решим задачу с помощью метода ветвей и границ. Для этого обозначим исходную задачу №1, внесем ее в основной список и примем в качестве верхней границы.

Итерация 1.

Шаг 1. Просматриваем основной список, выбираем из него задачу №1 и вычеркиваем ее из списка.

Шаг 2. Решаем задачу №1.

Так как значение целевой функции лучше, чем верхняя граница, то переходим к шагу 3.

Шаг 3. Полученное значение нецелочисленное, поэтому переходим к шагу 4.

Шаг 4. Выберем нецелочисленную переменную и внесем в основной спи-сок две задачи

Разобьем множество планов решения задачи на 2 множества и найдем решение двух за-дач:

задача 2 Задача 3

Сохраним значение верхней границы целевой функции на прежнем уровне и вернемся к шагу 1.

Итерация 2.

Шаг 1. Просматриваем основной список, он содержит задачи №2 и №3. Выбираем №3 и вычеркиваем ее из списка.

Шаг 2. Решаем задачу №3.

Результат решения:. Так как значение целевой функции лучше, чем верхняя граница, то переходим к шагу 3.

Шаг 3. Полученное решение целочисленное, поэтому решение закончено.

Ответ:...

ЗАДАНИЕ 3.53

Решить задачу коммивояжера методом исключения подциклов.

Условие.

16 13 35 41 52

19

29 31 26 18

57 51

44 51 7

5 40 32

14 16

33 41 28 3

53

19 54 24 10 41

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

В основной список внесем задачу о назначениях №1 с матрицей из исходной задачи ком-мивояжера.