Рис. 3

При классической постановке ТЗ предполагается выполнение условия

Σ S_i -Σ D_j =0 (3)

то есть, суммарная мощность всех источников равна суммарной мощности всех стоков (закрытая форма ТЗ). Однако, это условие не является принципиальным, так как при его нарушении можно ввести фиктивный источник, если Σ S_i -Σ D_j <0, (или фиктивный сток, если Σ S_i -Σ D_j >0), мощность которого равна величине невязки, положив тарифы на перевозку в этот фиктивный узел равными нулю.

Стратегия и методы решения ТЗ

Задача (1),(2) есть задача линейного программирования с ограничениями – равенствами. Число переменных в задаче равно nm. Система ограничений состоит из m+n уравнений, ранг системы равен m+n-1, то есть, любое допустимое базисное решение ТЗ будет содержать m+n-1 базисных переменных.

1. Находится начальный план перевозок.

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

Методы нахождения начального плана перевозок.

Метод северо-западного угла.

Пользуясь таблицей (1), распределяем груз, начиная с загрузки левой верхней (северо-западной) клетки (1,1), двигаясь из нее по строке вправо или по столбцу вниз. В клетку (1,1) заносим x₁₁=min (S₁,D₁). При S₁<D₁ запас первого поставщика будет исчерпан и в дальнейшем первая строка не рассматривается и x_1k=0, k=2,...,n. На следующих шагах последовательно распределяются запасы второго, …, n-го поставщиков, пока не будет полностью удовлетворен спрос первого потребителя.

При S₁>D₁спрос первого потребителя будет полностью удовлетворен и в дальнейшем первый столбец не рассматривается и x_k1=0, k=2,...,n.. На следующих шагах последовательно удовлетворяется спрос второго, …, m-го потребителя.

Если S₁=D_1, то в одну из клеток выбывающих первой строки и первого столбца (лучше в клетку с наименьшим тарифом) заносится так называемый базисный нуль, и x_k1=x_1k=0, k=2,...,n. В оставшейся таблице распределение ресурсов начинается с северо-западного угла, то есть, с клетки (2,2).

Все нулевые клетки таблицы, кроме (1,1) и клетки с базисным нулем, оставляются пустыми или отмечаются точкой.

Последней будет заполнена клетка (m,n).

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

Метод минимальной стоимости.

Метод аналогичен предыдущему, но на каждом шаге заполнение клеток начинается с клетки, которой соответствует наименьшее значение тарифа c_ij; при наличии нескольких клеток с одинаковым тарифом заполняется любая из них. В клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключается строка. соответствующая поставщику, запасы которого исчерпаны, либо столбец. соответствующий потребителю, спрос которого удовлетворен полностью. Если в процессе заполнения таблицы одновременно исключаются строка и столбец (это происходит при полном исчерпывании запаса и полном удовлетворении спроса), то в одну из свободных клеток записывается базисный нуль. Клетка с базисным нулем не должна образовывать цикл с ранее занятыми клетками.

Метод потенциалов

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

Введем следующие понятия:

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

2. Означенный цикл – цикл, одной из вершин которого приписан знак »+» и при обходе цикла в каком-либо направлении знаки вершин чередуются.

3. Сдвиг по циклу на величину Q≥0. При этом значения x_k1, стоящие в положительных вершинах цикла. увеличиваются на Q, а стоящие в отрицательных вершинах цикла уменьшаются на Q.

Задача, двойственная к ТЗ (1),(2), запишется в виде:

F(u₁,...,u_m,v₁,...,v_n)= Σ S_i u_i+Σ D_jv_j→ max; (4)

u_i+ v_j≤c_ij; i=1,...,m, j=1,..., n (5)

где двойственные переменные u_i и v_j свободные по знаку.

При этом, по теореме о дополняющей нежесткости, для того, чтобы планы пары двойственных задач х_ij⁰ и u_i⁰, v_j⁰, удовлетворяющие ограничениям (2),(3) и (4), были оптимальными необходимо и достаточно, чтобы выполнялись условия

х_ij⁰(c_ij- u_i⁰- v_j⁰₎=0, i=1,...,m, j=1,..., n (6)

Числа u_i и v_j, i=1,...,m, j=1,..., n, будем называть потенциалами источников и стоков, соответственно

То есть, для оптимального плана ТЗ необходимо выполнение условий:

1. каждой базисной клетке в транспортной таблице соответствует сумма потенциалов. равная тарифу этой клетки.

2. каждой свободной клетке соответствует сумма потенциалов, не превышающая тарифа этой клетки.

Алгоритм метода потенциалов

1. Найти начальный план перевозок методом северо-западного угла или методом минимальной стоимости.

2. Для каждой из m+n-1 базисных клеток составить уравнение u_i+ v_j= c_ij. Решить полученную систему (m+n-1) уравнений с (m+n) неизвестными, для определенности приравняв одну из переменных, например. u₁, нулю. Остальные потенциалы при этом определятся однозначно.

3. Для каждой свободной клетки вычислить относительные оценки ∆_ij= c_ij-(u_i+ v_j).

4. проанализировать относительные оценки:

• если все относительные оценки неотрицательны, то задача решена и получен оптимальный план перевозки;

• если среди оценок есть отрицательные, найти наименьшую отрицательную и пометить соответствующую клетку транспортной таблицы знаком «*».

5. Для свободной клетки (i,j) с выбранной оценкой, помеченной «*», построить означенный цикл, взяв эту клетку со знаком “+”. Все остальные вершины цикла должны располагаться в базисных клетках.

6. Выполнить сдвиг по построенному циклу на величину Q, равную наименьшему из тарифов в отрицательных вершинах цикла. Если наименьшее значение достигается в нескольких отрицательных вершинах, то во всех таких вершинах. кроме одной, при сдвиге следует поставить базисный нуль для сохранения числа базисных клеток равным (m+n-1)..Элементы матрицы, не входящие в цикл. остаются без изменений.

7. Перейти на шаг 2.

Замечание 1. В задачах открытого типа (не выполняется условие (3)) предварительно следует ввести фиктивные пункты, а затем решать полученную закрытую ТЗ методом потенциалов.

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

Замечание 3. Введение дополнительных ограничений может привести к невозможности найти оптимальный план перевозок.

Контрольные задания

Задания 1-6 содержат параметр V, который определяет вариант заданий. Число V является порядковым номером студента в группе.

В заданиях 7-10 вариант определяется также порядковым номером студента в группе по циклу.

Задание 1. Линии уровня

1.1. Приведите определение и свойства линии уровня функции нескольких переменных.

1.2. Укажите связь между линиями уровня и градиентами.

1.3. Постройте линии уровня U_α для функции

y = -V*x₁ + 2V*x₂

при α=0, α=1, α=2.

1.4. Постройте линию уровня U_α при α=3 для функции

y = x₁^2 –V*x₁*x₂ +2*x₂^2 + V*x₁.

Вычислите и нарисуйте градиент этой функции в точке (1; 1).

Задание 2. Числовые характеристики симметричной квадратной матрицы.

2.1. Приведите определения и геометрическую интерпретацию числовых характеристик квадратной матрицы:

• определитель,

• число обусловленности,

• собственные числа,

• собственные векторы,

• сингулярные числа.

2.2. Найдите гессиан H функции f(x, y) = Vx^2 +4xy+5y^2 в точке (1; 0).

Постройте множество точек, в которое оператор с матрицей H отображает единичную окружность S₁ с центром в точке (0; 0). Этот образ является эллипсом. Полуоси являются собственными векторами матрицы H, а длины полуосей – собственными числами _i.

2.3. Постройте линию уровня U_α=1 функции f(x, y) в точке (1, 0). Линия уровня также является эллипсом, полуоси которого – собственные векторы, а длин полуосей являются сингулярными числами матрицы и обратно пропорциональны квадратному корню из соответствующего собственного числа, то есть равны 1/_i^0,5. В некотором смысле, два эллипса из пунктов 5.2 и 5.3 являются ортогональными и взаимно-обратными.

Задание 3. Формула Тейлора для функции нескольких переменных

3.1. Приведите формулу Тейлора для функций одной и нескольких переменных

3.2. Проведите квадратичную аппроксимацию в точке (1; 1) для функции

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

Задание 4. Нахождение локальных экстремумов

4.1. Используя критерии оптимальности, найдите экстремумы для функции

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

4.2. Проверьте правильность нахождения точек экстремума двумя свойствами:

• с помощью графика этой функции,

• путем случайного перебора точек в малой окрестности точки локального экстремума.

Задание 5. Одномерная оптимизация

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

F(x) = x⁶ – Vx⁵ + Vx³ – 10x² + x.

Задание 6. Многомерная оптимизация по направлению

Найти точку локального минимума функции

F(x) = x₁² +Vx₂² + x₃² +3x₁x₂ – Vx₁x₃ – x₂x₃ + x₁ – Vx₂ + x₃

Задание 7. Методы безусловной оптимизации

1. Аналитически найти стационарные точки заданной функции, области выпуклости/вогнутости функции. Найти точку глобального минимума. Оценить «овражность» исследуемой функции в окрестности точки минимума.

2. Построить график функции, используя средства EXCEL или MATLAB.

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

4. При выполнении задания на языке СИ написать классы для работы с векторами и матрицами.

Задание выбирать в соответствии с порядковым номером фамилии студента в списке группы.

1. , метод Хука-Дживса.

2. , метод наискорейшего спуска.

3. , метод Хука-Дживса.

4. , метод сопряженных направлений.

5. , метод Нелдера-Мида.

6. , метод Ньютона.

7. exp[1- ], метод Нелдера-Мида.

8. exp[1- ], метод наискорейшего спуска.

9. exp[1-], метод сопряженных направлений.

10. exp[1-], метод Хука-Дживса.

11. exp[1-], метод Ньютона.

12. exp[1-], метод дробления шага.

13. exp[1-], метод наискорейшего спуска.

14. exp[1-], метод Нелдера-Мида.

15. , метод дробления шага.

16. , метод Ньютона.

17. , метод Нелдера-Мида.

18. , метод сопряженных направлений.

19. , метод наискорейшего спуска.

20. , метод Ньютона.

21. метод Ньютона.

22. 

метод дробления шага.

23. метод наискорейшего спуска

24. метод Нелдера-Мида.

25. , метод Ньютона.

26. , метод наискорейшего спуска

27. exp[1- ], метод дробления шага.

28. exp[1- ], метод Нелдера-Мида.

29. exp[1- ], метод сопряженных направлений.

30. exp[1- ], метод Ньютона.

Контрольные вопросы

Объяснить алгоритмы следующих методов

1. Метод конфигураций (Хука-Дживса).

2. Метод деформируемого многогранника (Нелдера Мида).

3. Метод наискорейшего спуска.

4. Метод сопряженных направлений и его модификации.

5. Метод Ньютона и его модификации.

6. Метод дробления шага.

Задание 8. Методы условной оптимизации

1. Решить задачу минимизации функции методом множителей Лагранжа.

2. Решить ЗНП методом седловой точки. Промежуточную задачу решения СЛАУ решить, используя EXCEL.

3. Решить задачу численным методом [8]. Метод условной минимизации выбрать самостоятельно (см. 1.4.-1.6). Сравнить результат с теоретическим решением.

Задания выбирать в соответствии с порядковым номером студента в журнале.

1. ,

2. .

3.

4.

5.

6.

7.

8.

Ограничения (для всех вариантов):

.

Контрольные вопросы

1. Активные и пассивные ограничения. Регулярная задача.

2. Теорема Куна-Такера.

3. Достаточные условия минимума в задачах математического программирования.

4. Седловая точка.

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

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

Вариант 1. Для изготовления четырёх видов продукции (А, Б, В и Г) используется три вида сырья (I, II и III). Ресурсы сырья, нормы его расхода на единицу продукции и получаемая прибыль от единицы продукции заданы в следующей таблице:

Определить оптимальный план выпуска продукции из условия максимизации прибыли.

Вариант 2. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятий позволяют обеспечить выпуск продукции каждого вида 50, 70, 100 и 30 тыс. шт., а плановое задание составляет соответственно 30, 80, 20 и 100 тыс. шт. Матрица

характеризует себестоимость единицы k-го вида продукции при производстве его на i-ом предприятии.

Найти оптимальное распределение планового задания между предприятиями.

Вариант 3. Для контроля за работой космической ракеты используются четыре вида датчиков (А, Б, В и Г), которые помещены на ракете и результаты измерений которых регистрируются тремя типами наземных регистраторов (I, II, и III). Каждый датчик определяет одну из характеристик (температуру, давление и т.д.) и передаёт результаты по отдельному каналу связи на любой регистратор. В следующей таблице указаны численности датчиков и регистраторов, а также время, затрачиваемое на включение соответствующего канала связи

Определить оптимальное закрепление датчиков к регистраторам, при котором достигается минимум суммарных затрат на переключение каналов.

Вариант 4. Поверхность ювелирного изделия составляет 400 см². Основной узор занимает 100 см², а площадь не украшенных полей – тоже 100 см². На оставшуюся часть поверхности необходимо нанести инкрустацию топазами, сапфирами, золотой протяжкой и серебряной чеканкой. При этом топазы должны занимать площадь не менее 80 см² и не более 100 см². Сапфиры должны по эстетическим соображениям занимать площадь не более 25% от площади, занимаемой топазами, но и не менее 10 см². Площадь золотой инкрустации не должна быть более 10 см², а площадь серебряной чеканки не менее площади, занимаемой сапфирами и не менее удвоенной площади золотой чеканки, но в то же время и не более 50 см².

Необходимо определить минимальное время, необходимое для инкрустации изделия, если известны затраты времени на каждую операцию: на установку топазов – 20 мин/см², установку сапфиров – 25 мин/см², на покрытие золотом – 120 мин/см², на покрытие серебром – 100 мин/ см².