WEBVTT

00:00:03.992 --> 00:00:08.956
Лекция первая. Методы оптимизации — их
место в теории исследования операций.

00:00:09.396 --> 00:00:13.359
Метод оптимизации как дисциплина
представляет собой раздел теории

00:00:13.479 --> 00:00:19.004
исследования операций, задачей которой
является поиск в рамках принятой модели

00:00:19.164 --> 00:00:19.684
решений.

00:00:20.350 --> 00:00:24.073
Отвечающих экспериментальным значениям
критериям.

00:00:32.399 --> 00:00:35.441
Понятие лучшего что-либо означает, когда
определение

00:00:36.443 --> 00:00:40.880
Определён показатель или критерий качества
выбираемых решений.

00:00:41.240 --> 00:00:45.078
Любую операцию можно охарактеризовать
следующими составляющими.

00:00:47.277 --> 00:00:53.313
Стратегия, вариант решения называется
допустимый или возможный способ достижения

00:00:53.473 --> 00:00:53.873
цели.

00:00:55.849 --> 00:01:01.688
Действующими факторами операции называются
объективные условия, определяющие её

00:01:01.928 --> 00:01:04.968
особенности и влияющие на её исход.

00:01:09.608 --> 00:01:11.887
Критерием эффективности операций

00:01:12.545 --> 00:01:18.148
Или стратегией называется показатель
достигнутого соответствия между полученным

00:01:18.268 --> 00:01:20.990
результатом и целью операции.

00:01:21.790 --> 00:01:26.113
Состоянием операции в некоторый момент
времени называют совокупность её

00:01:26.393 --> 00:01:29.715
характеристик, проявляющихся в данный
момент.

00:01:30.993 --> 00:01:36.269
Под параметром стратегии понимается
локальное качество операции,

00:01:36.469 --> 00:01:42.823
обусловливаемое его действующими факторами
и учитываемое критерием эффективности

00:01:43.023 --> 00:01:49.377
стратегии. Под моделированием параметров
или, соответственно, моделирование системы

00:01:50.136 --> 00:01:55.497
Понимается определение зависимости
изменения локальных качеств или критериев

00:01:56.257 --> 00:02:00.378
оптимальности с учётом действующих
факторов операции.

00:02:01.619 --> 00:02:05.780
Математической моделью операции называется
формальное соотношение

00:02:06.471 --> 00:02:11.707
устанавливающие связь принятого критерия
эффективности с действующими факторами

00:02:11.907 --> 00:02:18.222
операции. Решением ограниченным множеством
решений, связанным с выбранной

00:02:18.302 --> 00:02:22.739
математической моделью, называется
конкретный набор значений параметров

00:02:23.409 --> 00:02:27.768
полученных в результате использования этой
математической модели.

00:02:28.648 --> 00:02:34.446
Схематично этапы исследования операций
можно представить следующим образом

00:02:36.685 --> 00:02:39.245
Итак содержание этапов, этапы

00:02:39.911 --> 00:02:44.786
Формулировка цели операции обусловленная
выбор критериев эффективности.

00:02:47.184 --> 00:02:53.297
Первый этап — анализ системы с целью,
выбор исходного множества стратегий.

00:02:53.873 --> 00:02:59.194
Обоснованный выбор множества исходных
параметров, описывающих стратегию с учётом

00:02:59.595 --> 00:03:02.475
сформулированной цели операции — второй
этап.

00:03:02.875 --> 00:03:06.637
Третий этап — при необходимости
моделирования параметров стратегии и

00:03:06.717 --> 00:03:08.997
построения математической модели
параметров.

00:03:10.394 --> 00:03:14.721
Четвёртый. Построение математической
модели операций, получение формальной

00:03:14.841 --> 00:03:20.730
зависимости, изменение критерия качества
от изменения параметров системы.

00:03:21.692 --> 00:03:22.293
И пятый —

00:03:23.130 --> 00:03:28.173
Заключительный этап — получение решения,
выбор оптимального набора параметров,

00:03:28.253 --> 00:03:34.057
соответственно оптимальной стратегии с
учётом сформулированной цели операции.

00:03:35.418 --> 00:03:40.542
Вместо методов оптимизации в общей теории
исследования операций оптимальным образом

00:03:40.702 --> 00:03:41.022
решения

00:03:42.220 --> 00:03:48.053
Формализованные задачи, методы оптимизации
используются на четвёртом-пятом, при

00:03:48.213 --> 00:03:50.930
необходимости, на третьем этапах.

00:03:58.163 --> 00:04:01.040
Система называется упорядоченная
совокупность.

00:04:01.379 --> 00:04:07.339
Материальных объектов, элементов,
объединённых-либо-либо связями, например,

00:04:07.379 --> 00:04:11.738
механическими, электрическими и так далее,
предназначенными для достижения

00:04:12.098 --> 00:04:13.338
определённой цели.

00:04:13.738 --> 00:04:18.258
Если исходить из понятия, что поведение
системы есть последовательный ряд

00:04:18.338 --> 00:04:22.138
операций, то систему можно
классифицировать следующим образом.

00:04:23.097 --> 00:04:28.653
Системы: детерминированные, вероятностные
и игровые.

00:04:30.371 --> 00:04:36.406
Детерминированной считается такая система,
в которой составные части взаимодействуют

00:04:36.526 --> 00:04:39.644
друг с другом точно предсказуемым образом.

00:04:40.033 --> 00:04:45.069
Её поведение предсказуемо, если известно
текущее состояние элементов и законы

00:04:45.228 --> 00:04:48.146
преобразования, циркулирующие между ними.

00:04:48.705 --> 00:04:54.180
Вероятностной называют систему, возможное
поведение которой её впоследствии

00:04:54.420 --> 00:04:57.057
описывается на языке теории вероятностей.

00:04:57.337 --> 00:05:01.013
Здесь знание текущего состояния и
особенности.

00:05:01.437 --> 00:05:08.040
Взаимной связи элементов недостаточно для
однозначного предсказания будущего, что

00:05:08.280 --> 00:05:11.481
обусловливает необходимость вероятностной
оценки.

00:05:12.041 --> 00:05:18.483
Игровой называется система, осуществляющая
разумный выбор своего поведения в будущем.

00:05:19.116 --> 00:05:25.038
В основе выбора лежит неформальные
соображения, руководствоваться которыми

00:05:25.198 --> 00:05:26.798
может лишь человек.

00:05:30.560 --> 00:05:36.401
Другим важным классификационным признаком
системы является её степень сложности.

00:05:36.561 --> 00:05:40.723
По этому признаку их разделяют на простые
состояния, которых

00:05:41.324 --> 00:05:44.646
Немногочисленны и легко поддаются
описанию.

00:05:45.047 --> 00:05:50.331
Сложные, отличающиеся разнообразием
внутренних связей, но допускающие их

00:05:50.451 --> 00:05:56.617
описание крупномасштабные, не поддающиеся
какому-либо описанию связи.

00:05:57.642 --> 00:06:03.240
Важное место в исследовании различного
характера является структура системы и

00:06:03.400 --> 00:06:10.078
возможность её расчленяемости на
подсистемы, каждая из которых может

00:06:10.278 --> 00:06:12.478
иметь свой критерий эффективности.

00:06:13.237 --> 00:06:16.197
Принцип расчленяемости системы находится в

00:06:17.014 --> 00:06:21.613
В основе так называемого системного
подхода, состоящего в том, что задачу

00:06:22.053 --> 00:06:29.012
оптимизации можно упростить, сформулировав
и решив её для отдельных подсистем с

00:06:29.052 --> 00:06:33.411
учётом того, в какой мере критерий
эффективности подсистемы влияет на

00:06:33.531 --> 00:06:35.811
критерий эффективности системы в целом?

00:06:41.645 --> 00:06:46.688
Эвристика оказывается полезной и
независимой при решении задач, имеющих не

00:06:46.769 --> 00:06:50.691
числовую природу или характеризуемых
сложностью определения каких-нибудь

00:06:50.971 --> 00:06:55.134
параметров, либо их формализованного
сравнения.

00:06:55.614 --> 00:06:58.736
Методы оптимизации классифицируются по
числу критериев

00:06:59.370 --> 00:07:01.609
оптимальности. Их подразделяют на

00:07:01.849 --> 00:07:07.287
однокрекритериальные либо

00:07:07.487 --> 00:07:09.246
многокритериальные.

00:07:09.566 --> 00:07:14.364
В последнем случае при выборе оптимального
решения необходимо учитывать уже не один

00:07:14.604 --> 00:07:15.084
критерий

00:07:15.564 --> 00:07:22.529
А их совокупность, как правило,
характеризуемых разнородными параметрами,

00:07:22.609 --> 00:07:25.290
что усложняет их сравнительную задачу.

00:07:25.531 --> 00:07:28.973
Здесь, как правило, не обойдётся без
ивристики.

00:07:34.216 --> 00:07:36.618
Однокреториальная оптимизация.

00:07:36.789 --> 00:07:42.911
Основные методы оптимизации, используемые
при синтезе детерминированных сложных

00:07:43.031 --> 00:07:44.472
технических систем.

00:07:46.272 --> 00:07:50.874
Первое: постановка и методы решения задач
математического программирования, линейное

00:07:51.034 --> 00:07:51.755
программирование.

00:07:52.915 --> 00:07:56.478
Формальной постановки задачи
математического программирования.

00:07:56.798 --> 00:08:01.282
Будем в дальнейшем обозначать MP
аббревиатурой.

00:08:04.885 --> 00:08:08.288
В рамках задач

00:08:09.682 --> 00:08:14.845
Однокритериальной оптимизации наибольший
интерес представляют методы, относящиеся к

00:08:14.885 --> 00:08:19.287
группе оптимального планирования при
ограниченных ресурсах.

00:08:19.807 --> 00:08:25.370
Данными методами учитываются разнообразные
задачи, создание новой техники.

00:08:25.950 --> 00:08:30.469
Множество задач в том или ином виде может
быть сведено к постановке задачи

00:08:30.669 --> 00:08:32.549
математического программирования.

00:08:33.189 --> 00:08:37.349
С формальной точки зрения данная задача
относится к задачам математического

00:08:37.509 --> 00:08:41.788
программирования. Термин
«программирование» здесь понимается в

00:08:41.828 --> 00:08:44.388
смысле составления плана либо программы
действий.

00:08:45.828 --> 00:08:49.031
Задача оптимизации состоит в выборе
наилучших планов.

00:08:49.311 --> 00:08:54.035
Несмотря на смысловое разнообразие задач,
все они формально сводятся к одной общей

00:08:54.195 --> 00:09:01.040
постановке: найти значение переменных,
образующих в максимум

00:09:01.160 --> 00:09:03.282
либо в минимум значение целевой функции.

00:09:05.399 --> 00:09:11.237
Минимум-максимум, к который стремится
целевая функция F от X1, X2 и так далее,

00:09:11.277 --> 00:09:17.354
X. Замечание.

00:09:17.434 --> 00:09:21.072
В случае, когда целевая функция из
множества действительных чисел,

00:09:21.192 --> 00:09:22.952
используемых на практике,

00:09:23.500 --> 00:09:30.339
то целевая функция называется скалярной и
условие J1 от X1x2 больше либо

00:09:30.379 --> 00:09:37.098
равно меньше либо равно B IT, где от
единицы до M, предположение, что в каждой

00:09:37.178 --> 00:09:39.458
из N строк может присутствовать в одной
раз

00:09:40.263 --> 00:09:46.461
рассмотренных ограничений, где функция G
либо больше либо равно Б ито, либо меньше,

00:09:46.461 --> 00:09:47.980
либо равно Бито.

00:09:48.500 --> 00:09:51.499
Называется областью определения задачи.

00:09:51.939 --> 00:09:56.857
Целевая функция называется целевой,
которая может представлять собой критерий

00:09:56.977 --> 00:09:59.577
оптимальности при синтезе какой-либо
системы.

00:10:00.372 --> 00:10:05.576
Таким образом, целевая функция Z достигает
экстремального значения в одной или

00:10:05.736 --> 00:10:11.021
нескольких точках области определения,
которые требуется отыскать.

00:10:12.102 --> 00:10:16.066
Обычно в постановке задачи выбора
оптимизации решений вид

00:10:17.076 --> 00:10:23.362
Целевой функции Z и Ж известны и константы
B ита, определены специально.

00:10:23.482 --> 00:10:28.928
Оговариваются ограничения, выраженные в
требуемых к неотрицательности либо к

00:10:29.008 --> 00:10:30.730
целочисленным переменным.

00:10:31.170 --> 00:10:34.774
Краткая запись условия задачи
математического программирования имеет

00:10:35.893 --> 00:10:40.534
Икс принадлежит области определения,
стремится к максимуму либо минимуму

00:10:40.694 --> 00:10:41.974
целевой функции.

00:10:43.575 --> 00:10:47.975
Два основных класса задачи математического
программирования — это задачи линейного и

00:10:48.055 --> 00:10:49.656
нелинейного программирования.

00:10:49.936 --> 00:10:54.656
К задачам линейного программирования
относятся те, к которым и целевая функция

00:10:54.776 --> 00:10:56.857
Z, и все функции J линейны.

00:10:57.645 --> 00:11:02.049
Задачи, к которым присутствуют как-либо
нелинейности, соответственно, называются

00:11:02.249 --> 00:11:04.771
задачами нелинейного программирования.

00:11:05.291 --> 00:11:09.214
В данном курсе лекции мы ограничимся
рассмотрением задач линейного

00:11:09.334 --> 00:11:13.057
программирования, которые наиболее часто
требуется решать.

00:11:13.514 --> 00:11:15.833
нашей предметной области знаний.

00:11:18.791 --> 00:11:21.870
Линейное программирование постановка
задачи.

00:11:22.190 --> 00:11:27.147
Задача линейного программирования в общей
постановке состоит в отыскании переменных

00:11:27.427 --> 00:11:30.305
X1 и так далее XN, образующих

00:11:31.237 --> 00:11:37.884
Экстримум функции Z при ограничениях дана

00:11:38.044 --> 00:11:44.490
системаx1 + A12x2 и так далее A1x

00:11:44.891 --> 00:11:46.452
меньше либо равно Б1-му.

00:11:47.022 --> 00:11:53.579
И так далее. Затем AM1x1 + AMX

00:11:53.979 --> 00:11:59.018
+ и так далее AMXN меньше либо равно Bn.

00:11:59.218 --> 00:12:02.457
Обычно, кроме того, на практике добавляют
требования

00:12:04.088 --> 00:12:08.884
Неотрицательности для любого X житого
больше.

00:12:09.643 --> 00:12:14.638
Пример постановки задачи: ферма производит
откорм скота.

00:12:14.838 --> 00:12:18.994
Допустим, что имеется четыре вида
продуктов: П-1, П2, П3, П-4

00:12:20.333 --> 00:12:25.052
Стоимость единицы каждого продукта C1, Ц2,
Ц3, Ц4.

00:12:25.492 --> 00:12:31.012
Из этих продуктов требуется составить
пищевой рацион, который должен содержать

00:12:31.452 --> 00:12:35.772
белков не менее B1, углеродов — не менее
B2 единицы.

00:12:36.522 --> 00:12:42.757
Жиров не менее Б3 единицы для продуктов
П1, П2, Б3, П4.

00:12:43.117 --> 00:12:48.993
Содержание белков, жиров и углеродов в
единицах на единицу продукции приведено в

00:12:49.033 --> 00:12:49.592
таблице.

00:12:57.346 --> 00:12:58.747
Смотрим на таблицу.

00:12:59.348 --> 00:13:05.752
Продукты: 1, P2, P3, P4, элементы, белки,
углероды, жиры.

00:13:06.072 --> 00:13:12.557
Ну и коэффициенты, соответственно, матрицы
данокоэффициентов A11, A1—2, A1—3

00:13:13.168 --> 00:13:19.970
Вторая строка: A21 A2 A3; третья — A31 A32
A33; и четвёртая:

00:13:20.050 --> 00:13:26.732
A41 A42 A43, где A и ЖТ — некоторые числа

00:13:27.012 --> 00:13:29.052
и продукт жилемент.

00:13:31.990 --> 00:13:37.594
Задача: составить такой пищевой рацион, то
есть определить количество продуктов П1,

00:13:37.674 --> 00:13:44.198
П2, П-3, П-4, входящих в рацион, что при
минимальной стоимости рациона при

00:13:44.318 --> 00:13:47.800
условии выполнения ограничений белков и
жиров и углеродов.

00:13:48.870 --> 00:13:55.425
Целевая функция будет равна C1 на X1 + C2
на X2 + C3 на X3

00:13:55.865 --> 00:13:59.062
+ C4 на X4 и стремится к минимуму.

00:13:59.502 --> 00:14:06.417
Здесь мы за X1 и так далее и так далее XN
обозначили количество

00:14:06.617 --> 00:14:08.216
продуктов, которые должны входить

00:14:10.549 --> 00:14:15.745
Соответственно, составили систему
ограничений линейных

00:14:17.224 --> 00:14:23.739
ограничений в данном случае: A11x1 + A12x2
+13-3 +

00:14:23.899 --> 00:14:26.657
A14 больше либо равно Б1.

00:14:27.604 --> 00:14:33.649
Второе ограничение A21x1 + A2X

00:14:34.450 --> 00:14:40.615
+ A23-3 + A24 больше либо равно

00:14:40.735 --> 00:14:43.938
Б2. И последнее ограничение

00:14:47.139 --> 00:14:53.903
A13, A32; A33-3, A43-4 больше либо

00:14:53.943 --> 00:14:55.184
равно B3.

00:14:55.864 --> 00:14:58.746
Любая переменная X больше либо равна нулю.

00:14:59.226 --> 00:15:04.709
Замечание. Измените физический смысл
параметров данной задаче, и вы получите

00:15:04.909 --> 00:15:04.949
задачу

00:15:06.005 --> 00:15:11.241
Оптимизация загрузки ресурсов,
планирование загрузки многомашинной

00:15:11.361 --> 00:15:16.357
вычислительной системы и множества иных
задач из нашей предметной области.

00:15:20.873 --> 00:15:26.429
Геометрическая интерпретация задачи,
обоснование подхода к решению.

00:15:28.044 --> 00:15:33.526
Все последующие рассуждения применимы к
формулированию задачи линейного

00:15:33.686 --> 00:15:38.287
программирования в стандартной форме,
имеющей следующее представление.

00:15:38.647 --> 00:15:42.728
Целевая функция равна сумме Цжит на X и

00:15:45.203 --> 00:15:47.041
изменяется от единицы до N.

00:15:47.161 --> 00:15:51.876
При этом целевая функция может стремиться
как к максимуму, так и к минимуму.

00:15:52.835 --> 00:15:58.749
Обратим внимание на систему равенств 1:
11x1 +

00:15:58.909 --> 00:16:03.425
A12x2 и так далее, +1x равно B1.

00:16:04.984 --> 00:16:11.829
AM1x1 + AMX 2, + и так далее AMXN равно
BM.

00:16:12.590 --> 00:16:16.994
Любую задачу линейного программирования
можно свести к подобному виду.

00:16:17.074 --> 00:16:20.317
В частности, можно изменить знак целевой
функции.

00:16:20.643 --> 00:16:22.164
...и минимизировать её.

00:16:22.484 --> 00:16:27.284
Перейти же от неравенства к равенству
можно введя дополнительные переменные.

00:16:28.404 --> 00:16:33.564
Ответить на вопрос, всегда ли задача имеет
решение, а также сформулировать требования

00:16:33.724 --> 00:16:38.445
к подходу решения можно на основании
геометрической интерпретации.

00:16:39.111 --> 00:16:44.152
Геометрическая интерпретация в постановке
решения задач наглядна при условии, что

00:16:44.352 --> 00:16:51.154
M- равно K либо равно двум.

00:16:51.234 --> 00:16:55.835
То есть число уравнений M на 2 меньше, чем
число переменных N.

00:16:55.955 --> 00:17:00.277
В этом случае интерпретация может быть
проиллюстрирована на плоскости.

00:17:01.859 --> 00:17:06.383
Известно, что M линейно независимых
уравнений всегда можно решить относительно

00:17:06.703 --> 00:17:10.626
N базисных переменных, выразив их через K.

00:17:10.867 --> 00:17:15.751
В нашем случае два.

00:17:16.432 --> 00:17:17.593
Свободные переменные

00:17:18.407 --> 00:17:19.969
То есть две переменных будет.

00:17:20.169 --> 00:17:25.936
Свободные переменные обозначим свободными
переменными X1.x2, базисные X3.

00:17:26.377 --> 00:17:30.261
4. Тогда из уравнения 1 можно получить
следующую систему.

00:17:32.224 --> 00:17:33.225
X 3 равно

00:17:33.729 --> 00:17:37.367
A31x1 + A32 X2 + B3.

00:17:37.527 --> 00:17:44.002
X4 равно A41x1 + A4X 2 + B4 и так далее.

00:17:44.162 --> 00:17:48.919
X N равно An1x1 + A N2X + BN

00:17:50.672 --> 00:17:54.510
Теперь будем изображать пару свободных
переменных в системе координат.

00:17:54.949 --> 00:17:59.667
Так как по определению переменные
неотрицательные, то первое условие

00:17:59.787 --> 00:18:04.624
допустимой области решения является первый
квадрат системы координат.

00:18:04.944 --> 00:18:07.663
Теперь уточним область допустимых решений.

00:18:08.150 --> 00:18:14.992
На плоскости X1 X2 с учётом заданных
ограничений приравняем

00:18:15.192 --> 00:18:21.994
значение переменной X3 к нулю и запишем
исходное уравнение в следующем виде: ноль

00:18:22.074 --> 00:18:23.435
равен X-3 и равно

00:18:23.814 --> 00:18:28.654
A31 X1 + A32 X2 + Betta 3.

00:18:29.294 --> 00:18:35.853
В системе координат X1x2 данное уравнение
отображают соответствующие

00:18:35.933 --> 00:18:39.133
прямой. Если её наклон

00:18:39.514 --> 00:18:43.113
И расположение определяется
соответствующими коэффициентами.

00:18:43.312 --> 00:18:49.750
Данная прямая характеризуется тем, что
любое на ней точка соответствует

00:18:49.870 --> 00:18:52.748
условию X-3, равное нулю.

00:18:52.868 --> 00:18:56.547
Соответственно, в зависимости от
коэффициентов значение X-3 будет больше

00:18:56.827 --> 00:18:57.147
нуля.

00:18:57.931 --> 00:19:02.967
Выше отсекающей прямой меньше нуля, ниже
отсекающей прямой.

00:19:04.127 --> 00:19:08.923
Обратите внимание на рисунок X3 равно
нулю.

00:19:09.882 --> 00:19:11.641
Начертили прямую.

00:19:12.041 --> 00:19:12.561
Если у нас

00:19:13.795 --> 00:19:17.675
Ограничение больше либо равно, то движение
пойдёт вверх к данной прямой.

00:19:17.795 --> 00:19:22.596
Если меньше либо равно нулю, то прямая
будет направлена вниз.

00:19:24.036 --> 00:19:28.557
Аналогичным образом можно построить
соответствующие прямые для переменных.

00:19:29.458 --> 00:19:32.579
X4 и так далее, X.

00:19:37.220 --> 00:19:41.822
Обратим внимание опять же на рисунок,
когда X3 равнялось нулю, прямая у нас

00:19:43.502 --> 00:19:44.783
располагалась таким образом

00:19:45.957 --> 00:19:52.873
При X4, равное нулю вот данная прямая; при

00:19:52.953 --> 00:19:59.709
X5, равная нулю, следующая прямая и при
X6, равная нулю данный вид

00:19:59.989 --> 00:20:06.705
прямой. Совокупность данных прямых при
условии неотрицательных переменных.

00:20:07.602 --> 00:20:11.485
Отсекает область допустимых решений, если
она не пуста.

00:20:12.285 --> 00:20:18.010
Проведём подобную операцию с целевой
функцией, выразим Zerevую функцию через

00:20:18.210 --> 00:20:25.055
свободные переменные и получим Z равно
гамма 1x1 + гамма 2.2 + гамма

00:20:25.176 --> 00:20:25.696
нулевое.

00:20:26.383 --> 00:20:32.218
Где гамма-1, гамма-2 коэффициенты гамма-ну
нулевое — свободный член, который для

00:20:32.737 --> 00:20:34.096
простоты опустим.

00:20:34.176 --> 00:20:36.973
Обратим данное уравнение в ноль.

00:20:37.413 --> 00:20:43.247
Тогда, соответственно для данного
уравнения в системе координат X1

00:20:43.967 --> 00:20:49.481
О X2 может быть построена прямая,
проходящая через систему координат.

00:20:49.881 --> 00:20:55.475
Данная прямая называется опорной прямой
либо прямой целевой функции, для любой

00:20:55.595 --> 00:20:58.872
точки, расположенная на ней, целевая
функция равна нулю.

00:20:59.191 --> 00:20:59.871
Обозначим

00:21:01.490 --> 00:21:05.888
Движение, в направлении которого целевая
функция возрастает или убывает.

00:21:06.528 --> 00:21:13.525
Итак, стрелочками показали мы вверх она
будет возрастать, целевая функция и вниз

00:21:13.965 --> 00:21:20.962
убывать. Из данной интерпретации видно,
что

00:21:22.206 --> 00:21:26.529
В общем случае максимальное значение
целевой функции достигается в некоторой

00:21:26.649 --> 00:21:32.413
точке — области допустимых решений, в
точке пересечения прямых, определяющих

00:21:32.533 --> 00:21:34.294
область допустимых решений.

00:21:34.695 --> 00:21:37.136
В данном случае, если прямая у нас пойдёт
вверх

00:21:38.058 --> 00:21:44.936
Посмотрите, то мы проводим параллельную
прямую при движении вверх и видим, что Z у

00:21:45.016 --> 00:21:47.736
нас вот точка в данном случае пересечения.

00:21:50.215 --> 00:21:55.374
Ответим на вопрос: всегда ли задача имеет
решение и всегда ли оно единственно?

00:21:55.770 --> 00:21:57.651
Для этого рассмотрим два случая.

00:21:58.651 --> 00:22:02.091
Показан рисунок: первый случай, второй
случай.

00:22:02.651 --> 00:22:06.012
Первое — область не ограничена сверху.

00:22:08.332 --> 00:22:13.333
Обратите внимание, не замкнутая фигура,
задача не имеет решения, так как всегда

00:22:13.613 --> 00:22:14.053
можно найти

00:22:15.172 --> 00:22:17.414
Значение лучше предыдущего.

00:22:17.614 --> 00:22:21.738
То есть, если мы будем двигать целевую
функцию по направлению вверх, она может

00:22:22.218 --> 00:22:24.100
возрастать до бесконечности.

00:22:24.620 --> 00:22:30.025
Второе — ограничение параллельно прямой,
отображающей целевую функцию.

00:22:30.668 --> 00:22:34.949
В этом случае имеется бесконечное
множество решений, каждое из которых

00:22:36.550 --> 00:22:41.071
отображается точкой на соответствующей
прямой области определения.

00:22:41.271 --> 00:22:43.071
И это оптимальное решение.

00:22:43.552 --> 00:22:47.513
То есть, если мы будем двигать данную
прямую, то у нас в каждой точке может быть

00:22:47.713 --> 00:22:48.233
решение.

00:22:48.606 --> 00:22:50.968
И мы будем искать наиболее оптимальные.

00:22:54.291 --> 00:23:00.096
Замечание. Важно то, что к оптимальным
относятся и краевые точки, задаваемые

00:23:00.257 --> 00:23:03.259
пересечением прямых областей ограничения.

00:23:05.982 --> 00:23:06.582
Выводы.

00:23:07.135 --> 00:23:10.570
Основанный на геометрической интерпретации
задачи.

00:23:11.130 --> 00:23:15.724
Рассмотренная геометрическая интерпретация
в постановке задачи линейного

00:23:15.883 --> 00:23:21.197
программирования позволяет сделать важные
выводы относительно подхода к решению

00:23:21.396 --> 00:23:22.635
задач. Первое.

00:23:24.067 --> 00:23:29.983
Решение задачи будет краевая точка,
характеризуемая тем, что K равно N минус M

00:23:30.143 --> 00:23:31.343
— свободных переменных.

00:23:31.782 --> 00:23:33.861
В нашем случае две переменные.

00:23:34.901 --> 00:23:39.978
Второе, как следствие, возможность решения
задачи состоит в переборе краевых точек.

00:23:41.353 --> 00:23:45.909
Третье. Переход от одной краевой точки к
другой состоит в замене свободных

00:23:46.069 --> 00:23:52.305
переменных. Очевидно, чтобы пытаться
решить задачу, можно простейшим способом

00:23:52.465 --> 00:23:56.342
задать свободные переменные и решить
систему уравнений.

00:23:56.622 --> 00:23:59.260
Это связано со следующими недостатками.

00:23:59.825 --> 00:24:04.866
Первое — можно получить решение не в
области допустимых решений.

00:24:05.426 --> 00:24:10.346
Второе — задача может быть весьма
громоздкой, например, N равно тридцати, N

00:24:10.666 --> 00:24:16.067
10, то есть сочетание 10 из тридцати будет
составлять огромное число.

00:24:16.869 --> 00:24:22.954
Обратите внимание 30 045

00:24:23.955 --> 00:24:30.762
015. Вывод: возникает задача направленного
перебора краевых

00:24:31.282 --> 00:24:35.406
вершин, то есть направленного перехода к
оптимальному решению.

00:24:36.032 --> 00:24:40.114
Как следствие, возникает задача,
обоснованная критерием оптимальности

00:24:40.274 --> 00:24:42.715
перехода между краевыми точками.

00:24:47.757 --> 00:24:52.038
К такому виду системы всегда сводится
ввиду линейности ограничений, так как

00:24:52.198 --> 00:24:54.439
всегда можно выразить переменные X1.

00:24:55.398 --> 00:24:58.600
И так далее, X2 через какие-либо
коэффициенты.

00:24:58.960 --> 00:25:05.842
F1c равно F1 со звёздочкой — это
коэффициенты X1 + и

00:25:06.002 --> 00:25:07.203
так далее X.

00:25:07.323 --> 00:25:14.005
FM X равно звёздочка от M, XM + 1 и так
далее, X.

00:25:14.906 --> 00:25:19.944
В данном представлении переменные X1 и так
далее XN называются свободными, все

00:25:20.143 --> 00:25:21.623
остальные базисными.

00:25:22.702 --> 00:25:28.100
Соответственно, при данном представлении
можно определить некоторые базисные

00:25:28.579 --> 00:25:33.057
базисные решения: X1 равно Б1, X равно БМ.

00:25:33.812 --> 00:25:37.450
X N равно X равно

00:25:37.530 --> 00:25:46.884
нулюс

00:25:47.004 --> 00:25:49.002
алгоритм процесса приближения к

00:25:49.415 --> 00:25:55.373
К оптиму направленный перебор кривых
решений задача представлена

00:25:57.092 --> 00:26:03.610
к, соответственно, сразу получаемых
несколько исходных базисных решений.

00:26:03.890 --> 00:26:05.529
Возникают следующие вопросы.

00:26:06.283 --> 00:26:08.882
Оптимально или единственно ли оно?

00:26:09.322 --> 00:26:14.999
Если не оптимально, а ранее мы показали,
что поиск решения состоит в переборе

00:26:15.119 --> 00:26:20.996
краевых вершин, то возникает вопрос: как
осуществить переход к следующему решению?

00:26:23.275 --> 00:26:26.674
Вспоминание, что целевая функция выглядит
следующим образом.

00:26:27.485 --> 00:26:33.206
Z равно сумма cita на X житое, где Ж
изменяется от единицы до

00:26:33.406 --> 00:26:40.167
N. Просуммируем, соответственно, уравнения
в системе 2, умножив

00:26:40.287 --> 00:26:42.527
их на коэффициенты c-житое.

00:26:42.647 --> 00:26:47.848
Тогда система 2 будет представлять
следующий вид: c1 x1 + A

00:26:48.737 --> 00:26:55.020
1X M +1 и так далее A1x N равно C1 на

00:26:55.140 --> 00:26:58.461
B1. И так далее.

00:26:58.581 --> 00:27:04.984
И последнее: C1x + AM + 1x + 1 +

00:27:07.104 --> 00:27:13.868
Равно C на BM Тогда целевая функция будет
иметь вид суммы

00:27:13.988 --> 00:27:20.793
c-житое на X-житое, плюс сумма C +

00:27:20.953 --> 00:27:27.197
1 X житое равно Знулевому плюс сумма m + 1

00:27:27.998 --> 00:27:28.718
X житое.

00:27:30.363 --> 00:27:36.959
Где C + 1 житое коэффициент при свободных
переменных зависит от значения A и

00:27:37.039 --> 00:27:38.957
житое B It.

00:27:39.157 --> 00:27:44.913
По своему смыслувое — значение целевой
функции для исходного базисного решения.

00:27:45.393 --> 00:27:46.032
Теорема.

00:27:46.984 --> 00:27:53.952
Допустимое базисное решение X равно BTU,
при И равно от единицы m; X

00:27:54.112 --> 00:27:58.397
житое равно нулю, при Ж равно M + 1 и так
далее M.

00:27:58.717 --> 00:28:03.123
Является оптимальным, если коэффициент C
Mit

00:28:03.820 --> 00:28:06.101
Выражение 3 неотрицательное.

00:28:08.822 --> 00:28:14.624
Доказательство. Если переменные C Mita
больше либо равно нулю, то при любых

00:28:14.744 --> 00:28:20.146
значениях неотрицательных переменных X
житое, разность Z и Z нулевое не

00:28:20.266 --> 00:28:24.668
отрицательная её минимум есть ноль,
следовательно, З не име

00:28:25.842 --> 00:28:30.285
не будет меньше Z-нулевого, что говорит о
том, что его нельзя уменьшить.

00:28:30.646 --> 00:28:36.810
Следствие. Любые решения системы 1,
которым соответствует нулевая

00:28:37.370 --> 00:28:44.295
сумма C, при любых CM-житых больше либо
равных нулю, их

00:28:44.375 --> 00:28:46.017
житых больше либо равных нулю.

00:28:46.548 --> 00:28:51.148
Будет оптимальным, соответственно, при
условии, что CMжитые меньше нуля, решение

00:28:51.348 --> 00:28:52.549
может быть улучшено.

00:28:53.069 --> 00:28:59.469
Допустимое оптимальное базисное решение
окажется единственным, если все CM-житые

00:28:59.629 --> 00:29:02.470
больше нуля, то есть строго больше.

00:29:04.480 --> 00:29:08.724
Данное следствие является
сформулированными признаками оптимальности

00:29:09.084 --> 00:29:11.646
и единственными оптимальными решениями.

00:29:12.047 --> 00:29:17.812
Теперь рассмотрим, как осуществить переход
к новому решению и сформулируем критерии

00:29:17.852 --> 00:29:20.695
оптимальности выбора направления перехода.

00:29:21.321 --> 00:29:25.558
Пусть среди коэффициентов CMG есть
отрицательное значение.

00:29:25.758 --> 00:29:31.434
Это значит, что данное давая приращение
соответствующим переменным, целевая

00:29:31.594 --> 00:29:36.990
функция целевую функцию можно уменьшить,
чтобы перейти к другому целевому решению.

00:29:38.297 --> 00:29:44.302
Как следует из неотрицательности
необходимо сделать положительной, ввести в

00:29:44.382 --> 00:29:51.227
базис какую-то переменную X+1, равную X,
равную нулю, обратив в нуль

00:29:51.427 --> 00:29:53.549
одну из переменных X1 либо X

00:29:54.352 --> 00:29:59.993
Соответственно, в базис должно вводиться
та переменная, ей даётся положительное

00:30:00.153 --> 00:30:06.395
приращение, соответственно, которая имеет
выражение для целевой функции

00:30:06.635 --> 00:30:08.035
отрицательный коэффициент.

00:30:09.797 --> 00:30:16.797
Обозначим через S тот номер Ж или N + 1
величины коэффициентов M и ЖЭ, для

00:30:16.957 --> 00:30:21.357
которого сочетание минимально.

00:30:21.477 --> 00:30:26.117
Отсюда бросается в глаза очевидный подход
к поиску оптимального решения.

00:30:26.885 --> 00:30:32.851
...который используется эээ в системе
ограничений.

00:30:33.131 --> 00:30:39.738
Соответственно, будем давать положительное
приращение к переменной X данные, давая

00:30:39.938 --> 00:30:42.460
данное приращение из уравнения 2
получим...

00:30:44.508 --> 00:30:50.586
X1 равно B1S

00:30:52.026 --> 00:30:55.544
равно BM + AMS.

00:30:55.664 --> 00:31:01.782
Для Z имеет Z равно Z нулевое + C MS.

00:31:03.111 --> 00:31:05.230
Причём CMS меньше нуля.

00:31:05.550 --> 00:31:11.668
Естественно, что выбрав направление
движения, целесообразно максимально

00:31:11.868 --> 00:31:17.786
увеличить переменную X Чтобы получить
максимальное выражение в значении целевой

00:31:17.946 --> 00:31:18.465
функции.

00:31:19.564 --> 00:31:25.169
Однако возрастание переменной X ввиду
требования к неотрицательной переменной

00:31:25.849 --> 00:31:31.053
возможно до тех пор, пока какая-то из
свободных переменных не обратится в ноль.

00:31:31.334 --> 00:31:34.176
То есть, пока не достигнем ограничения
значения.

00:31:35.089 --> 00:31:40.692
Это произойдёт, если хотя бы эти один
коэффициент с индексом X положительным по

00:31:40.772 --> 00:31:44.054
условию и среди B ITV нет отрицательных.

00:31:45.094 --> 00:31:51.338
Если все A и S положительны, то первая в
ноль обратится та базисная переменная, для

00:31:51.458 --> 00:31:54.179
которой будет выполняться X равно
минимуму.

00:31:55.717 --> 00:32:01.602
Это и есть формализованное условие
перехода к последующей краевой вершине.

00:32:03.884 --> 00:32:05.326
Симплекс-метод.

00:32:06.327 --> 00:32:12.653
Решение было показано, что система
ограничений предполагает направленный

00:32:12.813 --> 00:32:14.294
перебор краевых вершин.

00:32:14.988 --> 00:32:19.545
Мы определились с тем, каким образом
осуществлять данный перебор, как выбрать

00:32:19.785 --> 00:32:24.623
направление перебора, как определить, что
в итоге получено оптимальное решение.

00:32:24.942 --> 00:32:29.380
Всё это ранее было выражено в формальном
виде, приведены соответствующие формулы

00:32:29.540 --> 00:32:30.140
для расчёта.

00:32:31.523 --> 00:32:37.408
Однако остаётся проблема, состоящая в том,
как найти то первое допустимое решение, а

00:32:37.568 --> 00:32:43.012
это должна быть краевая точка, с которой
начинать направленный перебор вершин.

00:32:43.172 --> 00:32:46.975
То есть, когда уже установлена возможность
применения решения.

00:32:47.584 --> 00:32:53.903
Для этого цели и служит математическая

00:32:54.063 --> 00:33:01.062
система, состлекс метода, состоящий в
двухэтапном решении задачи.

00:33:01.302 --> 00:33:04.502
На первом этапе требуется найти какое-либо
решение задачи.

00:33:05.337 --> 00:33:07.258
То есть найти исходную краевую точку.

00:33:07.418 --> 00:33:11.702
На втором осуществить перебор вершин с
целью поиска оптимального решения.

00:33:12.102 --> 00:33:16.745
При этом будем помнить, что краевая точка
легко отыскивается в случае представления

00:33:16.906 --> 00:33:21.349
задачи краевых вершин.

00:33:22.773 --> 00:33:27.453
Симплекс-метод предполагает в общем случае
двухэтапное решения

00:33:29.853 --> 00:33:36.453
данных задач. Первый этап начинается с
формального введения в каждую строчку

00:33:36.893 --> 00:33:38.853
стандартной системы искусственной

00:33:39.762 --> 00:33:43.964
неотрицательные переменные для получения
краевых вершин.

00:33:44.044 --> 00:33:49.928
Например, что при представлении задачи в
данном виде сразу можно определить решение

00:33:50.168 --> 00:33:56.932
задачи. Дана исходная задача A1x1+ и так
далее A1x

00:33:57.292 --> 00:33:57.812
равно Б1

00:33:58.813 --> 00:34:04.889
И так далее. A1x1+ и так далее AMXN равно
BM.

00:34:06.288 --> 00:34:13.163
Краевая вершина вводятся новые переменные
и приравниваются к данной системы

00:34:13.283 --> 00:34:13.763
равенств.

00:34:15.035 --> 00:34:21.920
...вновь введённым переменным B1, BM
Однако

00:34:22.161 --> 00:34:27.685
этим мы изменили собственно задачу, в
которой в каком случае решения новой

00:34:27.805 --> 00:34:30.047
задачи и исходная задача будет совпадать.

00:34:30.967 --> 00:34:35.684
Если существует решение для первой задачи,
то оно допустимо и для второй при условии,

00:34:35.764 --> 00:34:40.282
что X+ 1 равно икс M плюс N равно нулю.

00:34:40.681 --> 00:34:45.999
Так как именно эти переменные были нами
введены ввиду их неотрицательности.

00:34:46.502 --> 00:34:49.383
При данном случае все переменные
обращаются в ноль.

00:34:49.903 --> 00:34:54.303
Рассмотрим сумму наименьших значений,
которое есть ноль.

00:34:54.503 --> 00:35:01.424
Ввиду неотрицательности переменных при X +
1 равно X+ N равно нулю.

00:35:02.010 --> 00:35:08.977
Таким образом, проверка условия минимума
суммы для второй системы ограничений

00:35:09.218 --> 00:35:13.422
является условием совпадения решения для
первой и второй задач.

00:35:15.784 --> 00:35:17.146
С учётом сказанного, первый

00:35:17.879 --> 00:35:24.355
Этап решения симплекс-метода состоит в
поиске какого-либо решения исходной задачи

00:35:24.795 --> 00:35:30.951
посредством решения следующей
оптимизационной задачи, то есть, если мы

00:35:31.111 --> 00:35:34.189
будем находить минимум симплекс-метода.

00:35:34.545 --> 00:35:38.984
С учётом ограничений системы, заданной для
второй задачи.

00:35:39.464 --> 00:35:45.343
Для данной задачи приведён краевой
вершине, то есть можно быть применён

00:35:45.463 --> 00:35:50.862
Simplex метод, легко находится первое
решение: XM 1 равно B1 и так далее.

00:35:51.380 --> 00:35:53.779
X M + N равно BM.

00:35:54.179 --> 00:35:57.378
А X1 и так далее X равно нулю.

00:35:57.578 --> 00:36:03.696
После чего может быть использована система
с целью поиска оптимального решения.

00:36:04.175 --> 00:36:07.294
Если удаётся найти оптимальное решение,
для которого

00:36:07.962 --> 00:36:13.122
Если сумма равна нулю, то это решение
является исходным для основной задачи.

00:36:13.362 --> 00:36:16.362
В противном случае задача неразрешима.

00:36:25.563 --> 00:36:26.123
Смотрите.

00:36:27.189 --> 00:36:32.383
Прямоугольная система координат: ось опциа
T'1, ось координат — Tx2.

00:36:32.743 --> 00:36:35.220
Сумма равна нулю в данной точке.

00:36:35.699 --> 00:36:42.012
Основная задача — выпуклый многоугольник и
вспомогательн- вспомогательная задача

00:36:42.132 --> 00:36:43.410
линейного программирования.

00:36:44.216 --> 00:36:46.298
В данном случае определено на графике.

00:36:47.099 --> 00:36:51.383
Второй этап состоит в решении основной
задачи, в использовании

00:36:53.826 --> 00:36:57.149
решения системы уже для решения основной
задачи.

00:36:57.309 --> 00:36:59.992
При этом получим решение вспомогательной
задачи.

00:37:00.429 --> 00:37:06.474
Рассмотренная как исходная для основной
проверяется на оптимальность при

00:37:06.634 --> 00:37:11.559
необходимости осуществления
последовательного перебора решений.

00:37:13.120 --> 00:37:16.643
Замечание. Здесь уже используется целевая
функция Z.

00:37:20.807 --> 00:37:25.051
Примеры решения задачи линейного
программирования Simplex методом.

00:37:25.332 --> 00:37:31.257
Пусть имеется некоторый материал в виде
стандартных листов, который надо раскроить

00:37:31.538 --> 00:37:37.663
таким образом, чтобы получить не менее 80
деталей первого типа и не менее 4.

00:37:38.414 --> 00:37:43.575
Известно четыре способа раскроя листа
листа, для которого результаты раскроя

00:37:43.735 --> 00:37:45.536
представлены в таблице.

00:37:46.576 --> 00:37:51.617
Итак, Cn равно 1, 2, 3, 4.

00:37:52.777 --> 00:37:53.857
Четыре способа.

00:37:56.785 --> 00:38:02.430
В данном случае П — некоторый материал и
указаны

00:38:03.511 --> 00:38:10.398
коэффициенты Требуется получить
необходимое число деталей

00:38:10.518 --> 00:38:12.760
при минимальном расходе листов материала.

00:38:12.840 --> 00:38:15.402
Обозначим через их сжитое количество
листов.

00:38:15.923 --> 00:38:18.401
Расходуемых жим столбцом.

00:38:18.520 --> 00:38:21.078
Целевая функция в данном случае будет
иметь вид.

00:38:21.118 --> 00:38:25.594
Z равно X1 + X 2 + X 3 + X 4.

00:38:25.834 --> 00:38:32.748
При этом должны выполняться следующие
условия: 31, 2x2

00:38:33.950 --> 00:38:39.950
X3 больше либо равно восьмидесяти X1

00:38:41.149 --> 00:38:47.909
+6 X2 + 2 X3 в данном случае

00:38:48.189 --> 00:38:52.909
9 X3, да? И 13 X4 больше либо равна
сорока.

00:38:56.847 --> 00:39:00.209
То есть, в данном случае опечатка не 2x3,
а 9x3.

00:39:00.809 --> 00:39:04.972
Для применения симплекс-метода прежде
всего задачу требуется привести к

00:39:05.052 --> 00:39:06.373
стандартному виду.

00:39:06.573 --> 00:39:10.736
То есть систему ограничений мы должны
привести к системе равенств.

00:39:11.096 --> 00:39:12.657
Вводим новые переменные.

00:39:13.532 --> 00:39:20.452
3 X1+ 2 X2 + X 3 -x5 равно 80; X1

00:39:20.612 --> 00:39:26.491
+6 X2 + 9 X 3 + 13 X 4 - X6 равно 40.

00:39:26.731 --> 00:39:30.051
Вводятся новые переменные, при этом они не
должны повторяться.

00:39:30.683 --> 00:39:34.481
У нас в заданной системе ограничений
четыре переменные.

00:39:34.681 --> 00:39:38.958
Значит, вводим дополнительные, которые не
повторяются — это X5 и X6.

00:39:39.317 --> 00:39:44.234
Таким образом, так как ограничения были
больше либо равно, из каждой строки нужно

00:39:44.474 --> 00:39:46.752
вычесть, соответственно, переменную.

00:39:47.032 --> 00:39:51.988
Очевидно, базисное решение: -x5 равно 80,
-x640.

00:39:52.598 --> 00:39:55.754
Икс один и так далее, X4 равны нулю.

00:39:58.790 --> 00:40:03.184
Недопустимо ввиду неотрицательности
переменной, так как данное решение

00:40:03.384 --> 00:40:06.939
недопустимо. Задачу необходимо решить в
два этапа.

00:40:07.459 --> 00:40:08.058
Первый этап

00:40:08.944 --> 00:40:15.470
К решении вспомогательной задачи приведём
исходную задачу к краевым вершинам.

00:40:17.472 --> 00:40:24.439
Наша система примет следующий вид: 31 + 2
X2 + X 3 -x5 + X 7 равно 80.

00:40:26.179 --> 00:40:33.146
Второе равенство: X1 + 6 X 2 + 9 X 3 + 13
X4 -6 + X8 равно

00:40:33.307 --> 00:40:35.309
сорок сорок.

00:40:35.429 --> 00:40:40.194
Для этого введём дополнительные
переменные: X7.8, соответственно,

00:40:41.275 --> 00:40:44.638
сформулируем и решаем данную задачу
целевой функцией.

00:40:45.288 --> 00:40:47.568
которая должна быть минимизирована.

00:40:47.768 --> 00:40:52.449
Помня, что её решение будет решением
основной при условии, что сумма равна

00:40:52.529 --> 00:40:58.930
нулю. Здесь легко отыскивается и исходное
значение: X7 равно восьмидесяти,

00:40:59.130 --> 00:41:00.050
X8 40

00:41:00.885 --> 00:41:07.166
X1 и так далее, X6 — нулевое, сумма 80 +
40 — 120.

00:41:08.047 --> 00:41:13.768
Применим следующий метод систем и, прежде
всего, проверим получение решения на

00:41:13.848 --> 00:41:15.089
оптимальность.

00:41:15.409 --> 00:41:17.049
Рассмотрим целевую функцию.

00:41:17.850 --> 00:41:24.293
равное сумме X7 + X8, в которой переменные
X7 X8 выразим через остальные.

00:41:24.813 --> 00:41:31.456
Итак, сумма равна X7 + X 8 равна 80 - 3 X1
- 2x2,

00:41:31.576 --> 00:41:33.697
-X 3 + X5 + 40

00:41:34.405 --> 00:41:39.968
X1, -6 X2, -9 X3, - 13 X4 -6.

00:41:40.208 --> 00:41:46.931
В результате нахождения подобных
переменных получаем 120 - 4, -8 X2,

00:41:47.011 --> 00:41:52.094
- 10 X3, - 13 X4 + 5 и + X6.

00:41:54.244 --> 00:41:59.649
Присутствие отрицательных коэффициентов
указывает на неоптимальность полученного

00:41:59.809 --> 00:42:05.254
решения. Так как максимальное по модулю
отрицательное значение коэффициента имеет

00:42:05.414 --> 00:42:11.060
переменные X4, то в соответствии с
рассмотренным ранее критерием именно ей

00:42:11.220 --> 00:42:13.182
будет давать положительное преращение.

00:42:13.802 --> 00:42:15.482
X3 равно X4.

00:42:15.842 --> 00:42:21.202
Теперь рассмотрим, для какой величины
можно увеличить X4, а при этом переменная

00:42:21.402 --> 00:42:28.082
обнулится X7 равно восьмидесяти, X8 равно
40 - 13 X4.

00:42:28.962 --> 00:42:34.723
Вводя положительную переменную X4 из
исходной системы для нашего решения имеем

00:42:35.252 --> 00:42:40.896
Таким образом, видим, что X4 можно
увеличить до значения 4013.

00:42:41.216 --> 00:42:45.379
При этом X8 обратится в нуль, и получим
новое решение.

00:42:45.739 --> 00:42:48.541
X1 равно X2 равно X-3 равно нулю.

00:42:48.986 --> 00:42:55.751
X4 равно 413, X5 равно X6 равно нулю, X7
равно восьмидесяти, X8

00:42:56.071 --> 00:42:57.672
80.

00:42:57.752 --> 00:42:59.714
Сумма будет равна 80 +

00:42:59.994 --> 00:43:05.758
4м целевую функцию.

00:43:06.407 --> 00:43:10.650
Так как 8 равно нулю, выразим только X7.

00:43:12.251 --> 00:43:18.575
Ну и получается у нас сумма будет равна X7
+ X8 равна - 3 X-1, - 2

00:43:18.735 --> 00:43:22.257
X2, -X 3 + X5, -X8.

00:43:23.721 --> 00:43:28.166
Видим, что решение не оптимально, и так
как максимальный отрицательный коэффициент

00:43:28.366 --> 00:43:33.132
имеет переменная X1, то именно ей надо
дать положительное преращение.

00:43:33.532 --> 00:43:38.779
Определим, до каждого значения можно
увеличить X1 и какая при этом переменная

00:43:38.899 --> 00:43:39.740
обратится в ноль.

00:43:40.151 --> 00:43:42.911
X4 X7 — не нулевые значения.

00:43:43.591 --> 00:43:49.952
Тогда X7 будет равно 80 - 3 X1, X4 40 -X1
разделить на

00:43:50.032 --> 00:43:56.432
13. X1 может разность достигнет разности
до

00:43:56.592 --> 00:43:57.992
83.

00:43:58.557 --> 00:44:05.322
При этом обращается в ноль, X7 получаем X1
равно

00:44:05.442 --> 00:44:12.407
восемь третьих, X4:40 — 39; X2: X3, X5;
X6; X7; X-8

00:44:13.008 --> 00:44:13.928
равно нулю.

00:44:14.420 --> 00:44:18.264
Сумма будет равна нулю, x7 x8.

00:44:18.704 --> 00:44:20.266
Это оптимальное решение.

00:44:20.746 --> 00:44:25.511
Так как целевая функция не содержит
отрицательных коэффициентов, её минимум

00:44:25.631 --> 00:44:30.155
есть ноль, то найденное оптимальное
решение может рассматриваться как исходное

00:44:30.315 --> 00:44:31.396
решение для выполнения

00:44:31.930 --> 00:44:38.929
Второго этапа. Второй этап — система
равенств первое: 3x1 + 2 X2 + X 3

00:44:39.049 --> 00:44:40.928
- X равно восьмидесяти.

00:44:41.350 --> 00:44:46.748
X1 +6 X2 + 9 X 3 + 13: X4 - X6 — равно 40.

00:44:47.027 --> 00:44:53.144
Исходное решение X1 равно 803, X4:4039;

00:44:53.384 --> 00:45:00.141
X2: X3, X5; X6; X7 X8 равно нулю; сумма X
равна X7 X8

00:45:00.421 --> 00:45:01.060
равно нулю.

00:45:01.792 --> 00:45:05.596
Имея допустимое базисное решение,
полученное на первом этапе решения,

00:45:05.676 --> 00:45:07.918
начинаем решение основной задачи.

00:45:08.838 --> 00:45:09.599
Второй этап.

00:45:13.139 --> 00:45:15.740
Прежде всего проверим оптимальность
полученного решения.

00:45:15.860 --> 00:45:18.021
Для этого выразим X1 и X4.

00:45:18.261 --> 00:45:25.184
Получаем из четвёртой системы: X1 равно 80
- 2 X2 - X3 + X5,

00:45:25.224 --> 00:45:28.145
делённое на 3; X4 равно 40 минус

00:45:28.714 --> 00:45:34.276
X1 - 2 X2 -9 X3 + X 6, делённое на 13.

00:45:34.476 --> 00:45:40.437
Целевая функция Z будет равна X1 + X 2 + X
3 + X 4 и равна.

00:45:40.637 --> 00:45:45.838
Подставляем вместо X1 X4 коэффициенты,
находим подобное.

00:45:45.918 --> 00:45:52.640
В результате получим 1 080 - 3 X2 + 12 X1
+ 3 X6 делное на

00:45:52.720 --> 00:45:53.120
39

00:45:54.168 --> 00:46:00.599
Вывод. Полученное решение не оптимально,
следует дать при ращение переменной X2.

00:46:00.839 --> 00:46:05.993
Для определения того, насколько
увеличивать X2, выразим наши нулевые

00:46:06.072 --> 00:46:08.869
переменные X1. X4 через X2.

00:46:09.109 --> 00:46:09.508
Получим

00:46:11.412 --> 00:46:18.254
X1 равно 80 - 2 X2, делное на 3, X4 равно
40 -16 X2, делённое

00:46:18.374 --> 00:46:21.895
на 39. X1 выражаем через X2.

00:46:22.175 --> 00:46:28.297
Отсюда получаем, что X2 может
увеличиваться на 2,5, при этом X4

00:46:29.217 --> 00:46:30.177
превращаем в ноль.

00:46:30.875 --> 00:46:36.836
X1 равно 25, X2 — 2,5, X3: X6 — нулю.

00:46:36.916 --> 00:46:41.397
Целевая функция будет равна 27,5.

00:46:41.837 --> 00:46:44.558
Проверим данное решение на оптимальность.

00:46:44.758 --> 00:46:48.598
Для этого выразим целевую функцию через
переменные.

00:46:48.932 --> 00:46:51.170
X1; X2.3 X4.

00:46:51.690 --> 00:46:58.327
Подставим вместо X значения вместо X1 и X4
получим 440

00:46:58.806 --> 00:47:03.764
+ 2 X3 + 3 X 4 + X 5 + 5 X6 разделить на
16

00:47:04.807 --> 00:47:09.244
Вывод. Данное решение задачи является
оптимальным и единственным.

00:47:09.404 --> 00:47:15.600
Таким образом, оптимальный способ раскроя
листов посмотрите ещё раз задачу, состоит

00:47:15.720 --> 00:47:22.237
в следующем: 25 кроет первым кроить первым
способом, 25 вторым.

00:47:22.739 --> 00:47:27.222
В результате потребуется 25 с половиной
листов.

00:47:29.944 --> 00:47:31.865
Недостатки Symplex метода.

00:47:31.945 --> 00:47:36.589
Метод решения основанный на геопетрической
интерпретации задачи линейного

00:47:36.749 --> 00:47:39.671
программирования. Собственный критерий
оптимальности

00:47:40.272 --> 00:47:46.358
Не призван оптимизировать вычислительную
процедуру, так как сложность вычислений

00:47:46.478 --> 00:47:52.004
представляется числом перебираемых вершин,
в то время как критерии оптимальности не

00:47:52.084 --> 00:47:56.008
минимизируют их числа при поиске
оптимального решения.

00:47:57.265 --> 00:48:03.223
Сложность использования вычислительных
средств для решения задачи алгоритмы,

00:48:03.263 --> 00:48:06.622
ориентированные на применение
вычислительных средств, должны

00:48:07.022 --> 00:48:12.820
характеризоваться по возможности
простейшими операциями: плюс, минус и так

00:48:12.940 --> 00:48:13.260
далее.

00:48:13.583 --> 00:48:18.187
Здесь же, при обработке каждого решения
необходимо решать достаточно сложные

00:48:18.347 --> 00:48:22.992
системы уравнений, что сложно
формулируется на AVM.

00:48:23.072 --> 00:48:28.517
Таким образом, можно сделать вывод, что
для решения задач больше размерности, где

00:48:28.677 --> 00:48:30.158
необходимо применение AVM.

00:48:30.683 --> 00:48:37.236
Необходимы иные подходы, следовательно,
другая интерпретация задачи и

00:48:37.396 --> 00:48:38.994
критерии оптимальности.

00:48:39.434 --> 00:48:43.550
Особенно сложен симплекс-метод для решения
целочисленных задач.

00:48:45.827 --> 00:48:48.704
Целочисленное программирование — метод
Гамори.

00:48:50.783 --> 00:48:56.302
Задачи, сформулированные в терминах
линейного программирования и содержащие

00:48:56.422 --> 00:49:01.941
требования все или некоторые переменные,
целые числа называются задачами

00:49:02.181 --> 00:49:04.261
целочисленного программирования.

00:49:04.581 --> 00:49:07.260
Рассмотрим пример интерпретации задачи.

00:49:12.905 --> 00:49:19.831
Задана прямоугольная система координат,
дана выпуклая

00:49:19.871 --> 00:49:21.752
фигура.

00:49:22.233 --> 00:49:27.277
Девять точек, которые находятся в данной
области, и целевая функция

00:49:29.039 --> 00:49:30.200
определена прямой.

00:49:30.944 --> 00:49:36.423
Пусть к X1 выставлены требования
целочисленности.

00:49:36.623 --> 00:49:41.102
Решение задачи в этом случае будет
располагаться на соответствующих не

00:49:41.222 --> 00:49:45.781
пересекающихся линиях, характеризующих
целочисленность переменных.

00:49:46.061 --> 00:49:48.140
Если обе переменные целочисленные

00:49:48.809 --> 00:49:53.291
То решение задачи определяется узлами
соответствующей решётки на плоскости

00:49:53.971 --> 00:49:59.454
метода гаммори, состоит из выполнения
следующих шагов.

00:50:00.935 --> 00:50:05.057
Решается задача классическим
сиблекс-методом, и полученное решение

00:50:05.258 --> 00:50:06.818
проверяется на целочисленность.

00:50:07.360 --> 00:50:13.006
Если полученное решение не целочисленное,
вводят по определённым правилам в систему

00:50:13.126 --> 00:50:17.731
ограничений, отсекающих полученное решение
и задача решается вновь.

00:50:17.971 --> 00:50:21.614
Процедура повторяется, пока не найдено
целочисленное решение.

00:50:22.055 --> 00:50:22.495
Вывод.

00:50:22.997 --> 00:50:27.882
Условия целочисленности принципиально
усложняют решение задачи, так как в общем

00:50:28.002 --> 00:50:33.448
случае требует многократное применение
симплекс-метода с увеличением области

00:50:33.608 --> 00:50:36.692
ограничения, с введением дополнительных
условий.

00:50:51.674 --> 00:50:57.555
Методы оптимизации ориентированы на
применение AVM, общий подход к построению.

00:51:01.915 --> 00:51:08.315
Сложный подход в математической задаче.

00:51:09.393 --> 00:51:15.588
Методом потенциалов называется
необходимость разработки методов

00:51:15.708 --> 00:51:20.385
оптимизации, базирующихся на
вычислительных и логических операциях.

00:51:20.784 --> 00:51:25.181
Общей для этих методов является
необходимость доказательства

00:51:25.421 --> 00:51:27.380
целесообразности и достаточности.

00:51:28.230 --> 00:51:32.231
Целесообразность обусловливается
интерпретацией или физическим смыслом

00:51:32.351 --> 00:51:37.232
метода решения достаточным доказательством
исходности алгоритма.

00:51:37.592 --> 00:51:42.233
Каждый алгоритм предполагает некоторое
правило поиска решений и обусловливает

00:51:42.393 --> 00:51:44.073
переход к последующему решению.

00:51:44.695 --> 00:51:50.213
Отношения, связывающие очередные решения
при использовании алгоритма, называется

00:51:50.333 --> 00:51:52.252
алгоритмическим отображением.

00:51:52.532 --> 00:51:57.810
Алгоритм, построенный на основе
отображения, сходится, если он позволяет

00:51:58.170 --> 00:52:05.047
либо непосредственно вычислить оптимальное

00:52:06.378 --> 00:52:11.142
Экстремальное значение либо представляет
его в виде некоторой предельной точки,

00:52:11.222 --> 00:52:14.105
задаваемой последовательностью
приближения.

00:52:14.506 --> 00:52:20.111
В общем случае следует говорить о
сходимости алгоритма в смысле

00:52:20.591 --> 00:52:23.314
существования подобной предельной точки.

00:52:24.154 --> 00:52:28.838
Основной группой методов оптимизации,
ориентированных на использование ЛМ,

00:52:28.918 --> 00:52:31.881
является так называемые методы возможных
направлений.

00:52:32.202 --> 00:52:36.846
Общая идея методов возможных направлений
состоит в следующем: от изначально

00:52:37.087 --> 00:52:39.689
допустимой по условию задачи точки X1

00:52:40.545 --> 00:52:44.830
Осуществляется переход к новой допустимой
точке, в которой значение целевой функции

00:52:45.030 --> 00:52:46.471
лучше, чем в предыдущей.

00:52:47.072 --> 00:52:50.956
Процесс продолжается до тех пор, пока
остаётся возможность улучшить значение

00:52:51.116 --> 00:52:55.720
целевой функции, либо задача не может быть
решена с заданной точностью.

00:52:56.273 --> 00:53:00.631
При этом на каждом шаге для перехода в
последующую точку требуется определить

00:53:00.751 --> 00:53:03.110
направление перехода и длины шага.

00:53:03.230 --> 00:53:09.828
Таким образом, следующий шаг определяется
по формуле: X-К+

00:53:10.828 --> 00:53:12.747
-К.

00:53:13.688 --> 00:53:18.286
Один К РК, где, вернее, Альфа-К.

00:53:18.366 --> 00:53:23.124
Альфа-К — величина Ктова шага, РК —
единственный вектор, определяющий

00:53:23.524 --> 00:53:25.363
направление перемещения.

00:53:26.642 --> 00:53:30.441
Данное равенство является общим для
рассматриваемой группы методов

00:53:30.521 --> 00:53:31.320
оптимизации.

00:53:31.738 --> 00:53:35.897
Интерпретация же подхода к её решению
призвана задавать правила определения

00:53:36.097 --> 00:53:38.736
параметров РК и Альфа-К.

00:53:39.576 --> 00:53:42.975
Векторный метод решения задачи линейного
программирования.

00:53:43.375 --> 00:53:47.694
Рассмотрим данный метод как метод,
относящийся к группе методов возможных.

00:53:48.085 --> 00:53:52.881
Направлением оцениваем его преимущества и
недостатки по сравнению с традиционным

00:53:53.081 --> 00:53:57.676
Symplix-методом, проиллюстрируем
интерпретацию данного метода решением

00:53:59.235 --> 00:54:00.873
решённым ранее примером.

00:54:01.952 --> 00:54:03.990
Целевая функция стремится к минимуму.

00:54:04.741 --> 00:54:11.464
Заданы системы ограничений: 3x1 + 2 X2 +
10 X 3 больше либо равно восьмидесяти.

00:54:11.904 --> 00:54:18.586
Вторая система ограничений: X1 +6 X2 + X 3
+ 13—X4 — больше либо равна 40.

00:54:18.987 --> 00:54:21.788
В данном случае интерпретацию на плоскости
можно

00:54:22.567 --> 00:54:26.205
Дать, если число ограничений в системе не
превышает двух.

00:54:26.405 --> 00:54:30.002
Отложим в системе координат шкалы
ограничений.

00:54:30.642 --> 00:54:32.201
Показано на рисунке.

00:54:32.561 --> 00:54:37.757
Итак, ноль, 10,80, 010, 40.

00:54:40.223 --> 00:54:42.262
Строим векторы в данном случае

00:54:49.780 --> 00:54:55.578
ограничения позволяют задать допустимую
область решений, естественно, так как

00:54:55.898 --> 00:54:59.577
требуется достигнуть данного ограничения с
минимальными потерями.

00:55:00.034 --> 00:55:02.355
Нас интересует оптимальное решение.

00:55:02.595 --> 00:55:07.796
Что обеспечивает кратчайший путь между
точками 0 иль-штрих.

00:55:07.956 --> 00:55:13.158
Следует привести вектор 0.0, достающий
кратчайший путь, к области допустимых

00:55:13.278 --> 00:55:17.559
решений. Каждое возможное решение,
задаваемое системой ограничений,

00:55:18.080 --> 00:55:21.443
Также можно представить собственным
вектором на плоскости.

00:55:21.523 --> 00:55:28.250
В частности, если принять X1 равное
единице, X3 равное 3, - gк-1, смотрим

00:55:28.410 --> 00:55:32.134
исходную задачу, ему будет соответствовать
вектор X-1.

00:55:32.254 --> 00:55:35.257
Соответственно, получаем все остальные
векторы.

00:55:36.147 --> 00:55:41.671
Очевидно, что для заданных ограничений
лучшим был бы вектор или решение, которое

00:55:41.791 --> 00:55:48.115
позволяет продвигаться со скоростью две
или совпадающими по направлению с

00:55:48.155 --> 00:55:50.357
идеальным вектором 00-штрих.

00:55:50.637 --> 00:55:50.997
Однако

00:55:51.587 --> 00:55:57.702
Для заданной задачи необходимого вектора
нет, следовательно, возникает задача

00:55:57.862 --> 00:56:03.337
выбора оптимального решения выбора
параметра РК в уравнении 5.

00:56:03.697 --> 00:56:07.334
Так как вектор в общем случае
характеризуется двумя параметрами

00:56:08.030 --> 00:56:09.591
Длиной и направлением.

00:56:09.791 --> 00:56:16.315
В данном случае величина угла между им и
идеальным вектором 00, что с определёнными

00:56:16.395 --> 00:56:21.359
оговорками можно свести к одному критерию
выбора лучшего вектора по длине его

00:56:21.559 --> 00:56:24.441
проекций на идеальный вектор 00.

00:56:25.061 --> 00:56:30.694
Итак, по величине длины проекции можно
выбрать лучший вектор в данном шаге.

00:56:31.014 --> 00:56:36.287
В данном случае в качестве альфа-кая
предполагаем один отложенный вектор.

00:56:37.430 --> 00:56:42.231
Отложение выбранного лучшего вектора на
данном шаге, что означает присвоение

00:56:42.511 --> 00:56:45.952
соответствующим переменной их житой
значение 1.

00:56:46.032 --> 00:56:48.672
Приближает нас к допустимой области
решений.

00:56:48.832 --> 00:56:54.073
Следовательно, для перехода к следующему
шагу оптимизации следует перенести начало

00:56:54.153 --> 00:56:58.433
системы координат, направление и на
величину выбранного лучшего вектора.

00:56:59.323 --> 00:57:04.279
Соответственно, строится и новый идеальный
вектор, учитывающий достижение заданных

00:57:04.399 --> 00:57:06.517
ограничений на предыдущих этапах.

00:57:06.917 --> 00:57:11.713
В новой системе опять откладываются
исходные векторы и вновь убирается лучший

00:57:11.753 --> 00:57:14.991
вектор. Данная процедура выполняется до
тех пор, пока

00:57:15.732 --> 00:57:20.651
Последний лучший из отложенных векторов не
пересечёт

00:57:22.251 --> 00:57:24.170
допустимую область решений.

00:57:24.410 --> 00:57:28.890
Совокупность отложенных векторов на всех
этапах определяет оптимальный план или

00:57:29.050 --> 00:57:30.329
оптимальное решение.

00:57:30.769 --> 00:57:33.969
Замечание. Видим, что в данном случае мы
получаем оптимальное

00:57:34.525 --> 00:57:36.963
...решение целочисленной задачи.

00:57:37.242 --> 00:57:41.079
Посмотрим ещё раз на наш рисунок.

00:57:41.998 --> 00:57:44.876
То есть мы стремимся к идеальному вектору.

00:57:45.275 --> 00:57:51.870
То есть откладываем мы, откладываем один
вектор, второй, третий и приближаемся к

00:57:51.910 --> 00:57:53.868
идеальному вектору 003.

00:58:00.327 --> 00:58:02.128
Подходы к точному решению задачи.

00:58:02.288 --> 00:58:05.851
Первый — метод последовательных
приближений.

00:58:06.291 --> 00:58:11.095
Идея метода состоит в том, что на первом
шаге задачи решаются целочисленно,

00:58:11.175 --> 00:58:15.658
откладываются полные вектора при
пересечении последним отложенным вектором

00:58:15.818 --> 00:58:17.740
допустимой области решения.

00:58:18.619 --> 00:58:22.219
Начинается процесс приближения к
оптимальному точному решению.

00:58:22.539 --> 00:58:26.819
Каждый этап этого приближения состоит в
следующем: изменяется исходная система

00:58:26.939 --> 00:58:30.859
координат: с первого квадрата на третий,
со второго на четвёртый.

00:58:32.139 --> 00:58:34.418
С первого на третий, со второго на
четвёртый.

00:58:36.652 --> 00:58:41.015
Из точки пересечения последнего
отложенного вектора допустимой области

00:58:41.175 --> 00:58:47.618
решения Uм идеальный вектор, относительно
которого

00:58:48.219 --> 00:58:50.100
теперь выбирается лучший вектор.

00:58:50.340 --> 00:58:54.743
Векторы вариантов изменяются направления
на противоположные, и мы начинаем

00:58:54.823 --> 00:58:56.383
рассматривать некоторые их части.

00:58:57.071 --> 00:59:00.674
Длина векторов умножаются на коэффициенты
меньше единицы.

00:59:00.874 --> 00:59:05.677
Процедура повторяется до тех пор, пока
последний отложенный вектор, часть вектора

00:59:05.837 --> 00:59:09.360
не достигается точки ноль с двумя
звёздочками.

00:59:14.804 --> 00:59:15.845
Обратите внимание.

00:59:16.456 --> 00:59:22.417
Вектор 0 штрих либо 0 со звёздочкой, 02
штриха, либо 0 с двумя звёздочками.

00:59:23.017 --> 00:59:28.657
Вот у нас система координат задан вектор и
прямая.

00:59:29.377 --> 00:59:31.097
Метод точного решения.

00:59:32.738 --> 00:59:34.298
Точное решение задачи дали

00:59:35.002 --> 00:59:40.598
Данный альтернативный подход предполагает
отложение на каждом шаге не целиком, а

00:59:40.638 --> 00:59:44.516
лишь часть векторов. Данная часть
выбирается из следующих соображений.

00:59:44.636 --> 00:59:50.073
Предположив, что после отложенного вектора
следующим лучшим становится другой вектор,

00:59:50.153 --> 00:59:51.552
всегда можно определить ту часть,

00:59:52.123 --> 00:59:55.680
Первого вектора, которая задаёт лучшее
направление продвижения в сторону

00:59:55.840 --> 00:59:59.917
исходного вектора. Именно эта часть, а не
целиком вектор.

01:00:00.117 --> 01:00:03.594
Искомая часть вектора может быть
определена следующим образом.

01:00:03.954 --> 01:00:08.590
Если из конца искомой части лучшего
вектора отложить идеальный вектор

01:00:09.144 --> 01:00:13.301
То отложенные из него первый и второй
лучшие вектора будут иметь равную длину

01:00:13.501 --> 01:00:16.858
проекции на вновь отложенный идеальный
вектор.

01:00:17.977 --> 01:00:22.254
Данный подход уже трудно отнести к
методам, ориентированным на ЭВМ, так как

01:00:22.454 --> 01:00:26.091
параметр альфа-кате соответствен
посредством решений уравнений.

01:00:27.443 --> 01:00:29.681
Вот то, что мы с вами проговаривали.

01:00:30.440 --> 01:00:35.475
Проекция первого вектора, второго, и мы
стремимся к идеальному вектору.

01:00:37.993 --> 01:00:41.350
Формализация решения задачи векторным
методом.

01:00:42.269 --> 01:00:46.505
Как отмечали, критерии выбора решений на
каждом этапе определяется двумя

01:00:46.585 --> 01:00:47.185
параметрами.

01:00:48.064 --> 01:00:53.350
Длинный вектор решений и величина угла
вектора решения с идеальным вектором n,

01:00:53.350 --> 01:01:00.238
равная нулю. Соответственно, свести задачу
к однокритеральной

01:01:00.358 --> 01:01:03.762
можно, рассматривая длину проекции вектора
решения на идеальный.

01:01:07.268 --> 01:01:13.312
Модуль N равен XN на косинус альфа n.

01:01:13.792 --> 01:01:20.597
Если обозначить через X1 значение от
единицы до N параметры

01:01:20.717 --> 01:01:24.920
энного вектора, то длина вектора равна X
равна сумме

01:01:25.909 --> 01:01:29.111
X квадрат Ni в степени одной второй

01:01:33.515 --> 01:01:35.597
систему следующим образом.

01:01:38.199 --> 01:01:40.761
X1 вектор равен

01:01:42.419 --> 01:01:48.101
X1T, где X1 и от единицы

01:01:48.261 --> 01:01:54.024
долучим проекцию в артонормированном

01:01:54.144 --> 01:01:55.384
базисе.

01:01:55.824 --> 01:01:57.465
Вот она у нас проекция.

01:01:58.306 --> 01:01:59.066
Замечание.

01:01:59.540 --> 01:02:04.341
Длина вектора и угол между векторами
определяются по следующим формулам: X

01:02:04.861 --> 01:02:11.381
равно сумме, где M изменяется от M малого
до M большого; J M в степени одной

01:02:11.461 --> 01:02:16.342
второй; альфа равна R-косинус в сумме M от
единицы до M большого.

01:02:17.227 --> 01:02:23.868
Ж нулевое M умножить на J умножить на
сумму Ж в квадрате

01:02:24.068 --> 01:02:28.229
нуле и на сумму Ж в квадрате N в степени
одной второй.

01:02:29.229 --> 01:02:31.909
Данное выражение после соответствующих
подстановок

01:02:32.537 --> 01:02:37.981
Предположение, что нормированное значение
идеального вектора равно единице, J0 M

01:02:38.101 --> 01:02:44.626
равно единице, следовательно, ЖН равно
единице на корень из M, умноженное на

01:02:44.706 --> 01:02:46.628
сумму ЖН.

01:02:47.669 --> 01:02:48.029
Так как

01:02:48.929 --> 01:02:53.013
Значение M фиксировано для всех вариантов
решения.

01:02:53.373 --> 01:02:57.537
Это значение можно опустить таким образом:
в качестве критерия выбора оптимального

01:02:57.657 --> 01:03:02.382
вектора на каждом шаге можно рассматривать
параметр, определяющий следующие

01:03:02.462 --> 01:03:05.104
выражение. Система 6.

01:03:09.285 --> 01:03:16.161
X nule равно сумме X Nita при этом

01:03:16.241 --> 01:03:21.118
X It равно отношению X N It на

01:03:21.398 --> 01:03:23.997
X0.

01:03:24.516 --> 01:03:24.996
Видим, что

01:03:26.284 --> 01:03:30.327
Эти формулы просты, что позволяют
эффективно использовать данный метод

01:03:30.447 --> 01:03:35.811
решения задачи линейного программирования
с использованием вычислительных средств.

01:03:35.931 --> 01:03:39.293
Таким образом, методика выбора
оптимального решения сводится к

01:03:39.373 --> 01:03:44.777
следующему: на каждом шаге, используя
критерий шефшей, выбираем следующее

01:03:45.137 --> 01:03:45.898
значение из

01:03:47.456 --> 01:03:50.296
Икс нулевое, которое стремится к
максимуму.

01:03:50.737 --> 01:03:55.497
С учётом выбранного вектора, что
соответствует его откладыванию в системе

01:03:55.577 --> 01:04:01.138
координат, изменяем систему ограничений,
вычитаем из ограничений соответствующие

01:04:01.218 --> 01:04:02.979
параметры векторов.

01:04:04.539 --> 01:04:05.099
Третье.

01:04:05.900 --> 01:04:09.816
Проверяем все полученные ограничения на
условии меньше либо равно нулю.

01:04:09.976 --> 01:04:13.651
Если для всех ограничений оно выполняется,
задача решается.

01:04:13.971 --> 01:04:20.803
Если условие не выполняется, возвращаемся
к шагу один с перенормированием значений

01:04:20.963 --> 01:04:21.402
параметров.

01:04:22.180 --> 01:04:28.696
Пример. Вернёмся к задаче раскроя
материалов, рассмотренных ранее, где

01:04:28.896 --> 01:04:33.933
целевая функция у нас стремится к
минимуму, к уровню 80 и 40.

01:04:34.093 --> 01:04:39.290
Способ у нас четыре способа раскроя
первого типа — 3210.

01:04:39.617 --> 01:04:42.018
Раскрой второго типа: 169, 13

01:04:47.703 --> 01:04:54.548
ограничение: 3x1 + 2x2 + X 3 больше либо
равно восьмидесяти; X1 +

01:04:54.668 --> 01:04:59.152
6 X2 + 9 X3 + 13.4 больше либо равно 40.

01:04:59.552 --> 01:05:02.789
Для иллюстрации выполняем несколько шагов
решения.

01:05:02.909 --> 01:05:07.586
Шаг первый — считаем значение критерия для
различных вариантов.

01:05:08.265 --> 01:05:10.983
Ф равно

01:05:14.540 --> 01:05:15.339
единица.

01:05:15.763 --> 01:05:20.127
Умножить на единицу плюс 13 умножить на
одну вторую приблизительно

01:05:22.610 --> 01:05:24.572
1,4.

01:05:24.932 --> 01:05:30.258
Фи от An приблизительно 0,9.

01:05:30.658 --> 01:05:34.262
Fi, f от An 0,7.

01:05:34.848 --> 01:05:39.243
И четвёртая фи от An у нас приблизительно
0,5

01:05:46.356 --> 01:05:52.589
и на рисунке у нас по оси абциз 80 единиц
отложено, по оси координат — 40 единиц.

01:05:53.609 --> 01:05:58.534
Далее. Коэффициенты 1, 2, 3

01:06:00.656 --> 01:06:06.222
отложены по оси Обцикс и 16913 по оси
ординат.

01:06:06.302 --> 01:06:10.827
То есть раскрой первого типа у нас по оси
Обцикс, раскрой второго типа по оси

01:06:10.907 --> 01:06:11.427
ординат.

01:06:12.267 --> 01:06:15.390
Ну и мы строим, соответственно, векторы.

01:06:15.870 --> 01:06:19.634
Четыре вектора и целевую функцию.

01:06:24.318 --> 01:06:29.203
Сравниваем, выбираем лучший вариант этого
варианта.

01:06:29.323 --> 01:06:31.165
Приравниваем X-1 к единице.

01:06:32.915 --> 01:06:38.072
Формулируем новые ограничения: U1 равно
77, Q239.

01:06:38.512 --> 01:06:42.390
Задача не решена, следовательно, требуется
следующий шаг — решения.

01:06:42.590 --> 01:06:44.229
Не все ограничения нулевые.

01:06:44.349 --> 01:06:49.626
Следующий шаг отличается от предыдущего
тем, что вадиативном критерии изменяется.

01:06:53.273 --> 01:06:59.785
Продолжаем перерасчёт, находим первое F1,
второе F2, третье F2 и

01:06:59.905 --> 01:07:01.983
четвёртое f2 f2.

01:07:02.223 --> 01:07:06.098
То есть это уже мы рассмотрели двадцать
второй шаг и так далее.

01:07:06.578 --> 01:07:10.773
Выбираем лучшее значение по данному
критерию, фиксируем отложенный X

01:07:11.515 --> 01:07:16.318
Пересчитываем ограничения, проверяем,
решена ли задача полностью или требуется

01:07:16.478 --> 01:07:19.120
следующий шаг решения и так далее.

01:07:22.843 --> 01:07:25.044
Нормирование параметров в общем случае.

01:07:25.164 --> 01:07:28.166
В общем случае нормирование параметров
должно учитываться

01:07:30.539 --> 01:07:36.340
Первое. Величину вектора относительно
векторов других сравниваемых вариантов или

01:07:36.580 --> 01:07:39.581
насколько велик шаг в сторону ограничения.

01:07:39.701 --> 01:07:43.942
Будет ли откладывание данного вектора?

01:07:44.022 --> 01:07:49.703
Второе — отношение ограничений между собой
или в какой мере следует продвигаться при

01:07:49.823 --> 01:07:51.023
откладывании векторов?

01:07:51.464 --> 01:07:52.865
Конкретному ограничению.

01:07:53.185 --> 01:07:57.508
Третье — учёт отношения влияния выбранного
решения по отношению к остальным на

01:07:57.588 --> 01:07:58.829
целевую функцию.

01:07:59.750 --> 01:08:01.951
Нормирование значения.

01:08:02.312 --> 01:08:06.755
Нормированное значение параметры задаётся
объективным способом нормирования по

01:08:06.835 --> 01:08:07.875
следующим условиям.

01:08:08.569 --> 01:08:15.126
Вектор QN равно отношению Q относится 0.

01:08:15.206 --> 01:08:20.843
Где 0 — это верхняя точечная

01:08:20.963 --> 01:08:24.082
граница, то есть максимум.

01:08:24.611 --> 01:08:31.126
Учёт отношения ограничений осуществляется
внесением весового элемента,

01:08:31.166 --> 01:08:36.762
определяемого по формуле Beta M равно Н
относится Q степень

01:08:37.482 --> 01:08:40.360
максимальная, где Q максимальная.

01:08:41.155 --> 01:08:43.273
Также верхнее точечное значение.

01:08:43.353 --> 01:08:48.788
Таким образом, выбор лучшего решения на
каждом этапе выполняется по формуле.

01:08:48.908 --> 01:08:53.584
F от равно сумме Q относится U

01:08:55.503 --> 01:08:56.062
умноженное

01:08:57.051 --> 01:09:00.976
На ку большое M и ку максимальное M.

01:09:01.256 --> 01:09:05.661
Для того чтобы учесть, насколько выбранное
решение влияет на целевую функцию при

01:09:05.781 --> 01:09:10.106
условии, что она минимизируется, в
критерии для варианта Н следует ввести

01:09:10.307 --> 01:09:12.029
коэффициент гамма Н.

01:09:12.229 --> 01:09:12.829
Тогда получим

01:09:13.791 --> 01:09:20.595
Следующее значения A N равно гамма
умножить на сумму ку малое n

01:09:20.995 --> 01:09:27.718
на K малое умножить на Q большое N
относится к Uсму M, где гамма

01:09:27.878 --> 01:09:31.360
Н равна минимальное N на Kn

01:09:32.191 --> 01:09:36.956
Ц минимальная — это есть Infinitu-tum,
Infinitu.

01:09:37.917 --> 01:09:44.044
Эта формула является основной расчётной
формулой выбора оптимального плана на

01:09:44.204 --> 01:09:47.168
каждом шаге при постановке задачи в общем
виде.

01:09:48.935 --> 01:09:55.702
Infinitie — это значит минимизируется
достоинства вектора метода

01:09:55.982 --> 01:10:01.468
решения основного основанного на векторной
интерпретации задачи линейного

01:10:01.628 --> 01:10:05.752
программирования. Кроме очевидной
наглядности, данная интерпретация

01:10:05.952 --> 01:10:08.114
позволяет, в отличие от Simplex метода

01:10:08.787 --> 01:10:13.066
Векторный метод позволяет минимизировать
число вычислений, так как критерий

01:10:13.106 --> 01:10:17.425
оптимальности позволяет на каждом шаге
наилучшим образом с точки зрения

01:10:17.625 --> 01:10:22.304
количества вычислений, продвигаться в
сторону области допустимых решений.

01:10:22.944 --> 01:10:26.503
Минимальная вычислительная сложность на
каждом этапе выбора плана.

01:10:27.062 --> 01:10:29.620
Простейшие арифметические и логические
операции.

01:10:29.820 --> 01:10:34.417
Всё это обусловливает эффективность
применения метода для расчёта, оптимизации

01:10:34.617 --> 01:10:37.535
задач на вычислительных машинах.

01:10:39.453 --> 01:10:42.012
Приоритетная задача линейного
программирования.

01:10:42.868 --> 01:10:46.152
Приоритетная задача состоит в том, что в
рамках заданных ограничений

01:10:46.392 --> 01:10:50.517
дополнительного оговаривается порядок
выполнения данных ограничений.

01:10:50.797 --> 01:10:55.762
Возвращаемся к нашей, к нашему примеру
раскрою материалов, где заданы ограничения

01:10:55.923 --> 01:10:58.285
не менее 80 деталей первого типа.

01:10:58.443 --> 01:10:59.844
...и не менее сорока.

01:11:00.204 --> 01:11:06.886
Может быть дополнительно введено,
например, следующее ограничение: в

01:11:07.006 --> 01:11:11.807
первую очередь необходимо провести не
менее 30 деталей первого типа и не менее

01:11:11.847 --> 01:11:13.528
двадцати второго. Во вторую очередь...

01:11:14.987 --> 01:11:18.791
Э-э, увеличиваем значение либо уменьшаем и
так далее.

01:11:18.991 --> 01:11:22.955
То есть вводится некоторый приоритет на
очередность решаемых задач.

01:11:23.075 --> 01:11:26.078
При такой постановке задачи уже
действительно можно говорить об

01:11:26.198 --> 01:11:29.922
оптимальности планирования, так как
учитывается, соответственно,

01:11:30.002 --> 01:11:31.843
последовательность выполнения работ.

01:11:32.750 --> 01:11:36.353
При использовании классического метода
решения задачного линейного

01:11:36.473 --> 01:11:41.356
программирования Simplex методов не
позволяющих учитывать динамику плана,

01:11:41.597 --> 01:11:44.999
данная задача разбивается на
соответствующую совокупность

01:11:45.239 --> 01:11:47.841
невзаимосвязанных задач линейного
программирования.

01:11:48.495 --> 01:11:51.097
Число задач определяется числом
приоритетов.

01:11:51.458 --> 01:11:55.782
Векторный метод решения задач линейного
программирования позволяет строить

01:11:55.942 --> 01:11:59.466
оптимальные планы с учётом динамики
выполнения работ.

01:11:59.986 --> 01:12:03.670
Рассмотрим, как решается приоритетная
задача линейного программирования.

01:12:04.317 --> 01:12:08.641
...векторным методом и в первую очередь,
как она интерпретируется.

01:12:08.921 --> 01:12:12.685
В общем случае приоритетная задача
линейного программирования в своей

01:12:12.765 --> 01:12:17.969
формальной постановке выглядит следующим
образом: пусть задано первое приоритетов

01:12:18.209 --> 01:12:19.971
на заданную область ограничения.

01:12:20.435 --> 01:12:24.116
Соответственно, имеем следующую систему
ограничений.

01:12:26.357 --> 01:12:28.637
Так, задано в виде формул.

01:12:28.797 --> 01:12:34.239
При этом задаётся в первую очередь,
требуется выполнить что QM ограничений.

01:12:34.319 --> 01:12:35.640
Постановка задачи имеет вид

01:12:36.460 --> 01:12:43.335
X M житые такие, что XM, где M изменяется
от 1 и от

01:12:43.455 --> 01:12:50.011
единицы дощается в минимум целевая функция
при условии, что

01:12:50.970 --> 01:12:54.008
система ограничений будет больше либо
равна ку.

01:12:56.227 --> 01:13:01.906
Один и первое ограничение, и второе — ку,
больше либо равна Q и

01:13:03.986 --> 01:13:07.225
причём сумма будет равна m.

01:13:09.425 --> 01:13:12.265
Векторная интерпретация задачи состоит в
следующем.

01:13:12.425 --> 01:13:13.505
Смотрите на рисунок.

01:13:13.888 --> 01:13:17.407
На плоскости проявляется система
допустимых решений.

01:13:23.925 --> 01:13:29.283
Допустимая область с меньшим порядковым
номером более приоритетна у 1.

01:13:30.173 --> 01:13:33.374
Данные ограничения должны выполняться в
первую очередь.

01:13:33.574 --> 01:13:38.297
В каждой допустимой области должно быть
отложен идеальный вектор из начала

01:13:38.377 --> 01:13:42.698
координат в первую очередь, из вершины
предыдущей области, в начало координат

01:13:42.979 --> 01:13:47.821
второй области. Итак, из вершины
предыдущей области опять же откладывается

01:13:47.941 --> 01:13:49.662
идеальный вектор во вторую область.

01:13:51.891 --> 01:13:57.052
Данная задача может решаться так, как так
же, как и в случае без приоритетной

01:13:57.172 --> 01:14:00.652
постановки путём выбора лучшего вектора на
каждом этапе.

01:14:00.932 --> 01:14:05.813
Однако существует два правила преодоления
области допустимых решений.

01:14:07.013 --> 01:14:10.934
Таким образом, данный подход может
позволить использовать возможности

01:14:11.134 --> 01:14:12.814
векторной интерпретации.

01:14:13.592 --> 01:14:18.553
Возможность поиска не только лучших
решений в плане, но и их очерёдность для

01:14:18.713 --> 01:14:23.794
решения приоритетных задач, отличающихся
своей постановкой, заданием очередности

01:14:24.074 --> 01:14:25.714
выполнения ограничений.

01:14:27.914 --> 01:14:30.715
Постановка и метод решения задачи синтеза

01:14:31.425 --> 01:14:34.268
Расписание. Векторная интерпретация
задачи.

01:14:34.629 --> 01:14:39.155
Большинство детерминированных задач в
прикладной области вычислительных систем

01:14:39.355 --> 01:14:44.081
сетей является линейными, поэтому
векторная интерпретация задач здесь имеет

01:14:44.201 --> 01:14:46.283
достаточно большую общность.

01:14:47.370 --> 01:14:54.167
В частности, всегда, когда может быть
определено некое желаемое

01:14:54.367 --> 01:14:55.846
или оптимальное решение?

01:14:56.126 --> 01:15:00.484
Могут быть определены исходные способы
решения, при необходимости задана область

01:15:00.604 --> 01:15:04.642
оптимальных решений. Применим данный
подход, рассмотрим его применение к

01:15:04.722 --> 01:15:07.681
задачам синтеза расписаний реального
времени.

01:15:08.210 --> 01:15:12.896
Рассматриваемая детерминированная задача
теории расписания состоит в определении

01:15:13.056 --> 01:15:18.423
очередности передачи прав на занятие
ресурса, минимизирующей его выполнение

01:15:19.064 --> 01:15:23.189
производительность при выполнении
ограничений реального времени.

01:15:23.775 --> 01:15:27.934
Более подробную постановку задачи синтеза,
расписания реального времени мы рассмотрим

01:15:28.254 --> 01:15:29.614
на практических занятиях.

01:15:29.694 --> 01:15:35.493
Здесь лишь отметим, что ограничение
реального времени на время решения

01:15:35.733 --> 01:15:37.212
различных задач.

01:15:37.372 --> 01:15:41.172
Задача должна быть гарантированно решена
на этот промежуток времени.

01:15:41.808 --> 01:15:45.407
В одной системе реального времени могут
быть сильно различаться ввиду их

01:15:45.926 --> 01:15:51.163
разнородности. Например, при построении
системы уравнений с соответствующими

01:15:51.523 --> 01:15:57.320
различными заданными периодами можно
потребовать измерять скорость,

01:15:57.360 --> 01:16:00.358
температуру, плотность чего-либо и так
далее, и тому подобное.

01:16:01.305 --> 01:16:06.780
В этом случае использование
бесприоритетного режима обслуживания в

01:16:06.859 --> 01:16:11.934
реальном времени по очереди может
оказаться неоптимальным, требующим

01:16:12.214 --> 01:16:15.770
большего увеличения производительности
общного ресурса.

01:16:16.130 --> 01:16:17.169
Требуется построить

01:16:19.750 --> 01:16:24.704
Оптимальную для конкретного приложения
приоритетную дисциплину обслуживания

01:16:24.904 --> 01:16:28.820
реального времени. Рассмотрим
интерпретацию постановки задачи на

01:16:28.940 --> 01:16:35.054
рисунке. Так, реальное время — один,
реальное время два.

01:16:38.182 --> 01:16:44.786
По оси координат откладываются временные
характеристики задачи

01:16:45.306 --> 01:16:50.990
эмного типа, в частности ТМ, и ограчение
реального времени

01:16:54.827 --> 01:16:58.068
...которая ограничивает некоторые
допустимые области решения.

01:16:58.148 --> 01:17:00.269
В данном это случае по оси апциз.

01:17:00.469 --> 01:17:04.870
Однако, в отличие от предыдущего случая
задачи линейного программирования,

01:17:04.990 --> 01:17:09.672
допустимая область решения здесь уже иная,
задаются иные условия.

01:17:10.112 --> 01:17:13.393
Особенностью является и то, что исходная
задача M.

01:17:15.267 --> 01:17:21.306
способов решения задачи при каждом весь
квант времени с учётом затрат времени на

01:17:21.386 --> 01:17:25.865
выбор заявки из очереди Представляется
заявка одной из M очередей.

01:17:25.985 --> 01:17:30.784
Соответственно, имеем M векторов равных
длины

01:17:32.076 --> 01:17:37.792
Совпадающие по направлению с осями системы
координат векторы О-О-1 и

01:17:37.952 --> 01:17:43.548
ОО-1.

01:17:43.828 --> 01:17:45.426
Вот он вектор ещё раз.

01:17:45.826 --> 01:17:46.746
О-О-2.

01:17:51.837 --> 01:17:55.640
В этом случае уже имеет смысл говорить не
о максимальной длине проекции, а о

01:17:55.800 --> 01:17:58.163
ведеальном векторе O-штрих.

01:17:58.403 --> 01:18:02.086
То есть мы должны найти ведеальный вектор
O-штрих.

01:18:03.287 --> 01:18:08.412
А минимальный, что и реализует при
откладывании векторов по осям координат.

01:18:09.106 --> 01:18:14.631
Так как целесообразно обслуживать
максимальное число данных заявок за

01:18:14.791 --> 01:18:20.556
ограниченное время и о достижимости
ограничения T большое M по M осям.

01:18:20.796 --> 01:18:25.560
Естественно, что при синтезе расписания в
первую очередь имеет смысл откладывать

01:18:25.640 --> 01:18:26.281
вектор в том

01:18:28.351 --> 01:18:35.231
Направлении, которые может быть получено
из условия в данном случае минимизации.

01:18:35.311 --> 01:18:40.350
То есть выбираем самое самое жёсткое
ограничение, которое должно быть выбрано

01:18:40.710 --> 01:18:42.110
за минимальное время.

01:18:42.390 --> 01:18:43.030
На рисунке

01:18:43.790 --> 01:18:47.789
Вы его перечертите для того, чтоб было
более понятно была задача — это

01:18:48.029 --> 01:18:50.907
ограничение Tolo 'равное одному.

01:18:51.067 --> 01:18:56.825
Предоставим ресурс выбранной заявки на
фиксированное время занятия, задаваемое

01:18:56.985 --> 01:19:01.583
продолжительностью времени кванта, что на
рисунке соответствует отложению вектора

01:19:01.703 --> 01:19:02.463
ООдин.

01:19:03.245 --> 01:19:06.162
Далее требуется сформулировать новую
систему координат.

01:19:06.402 --> 01:19:10.637
Особенностью её получения будет перенос
системы координат в направление и на

01:19:10.717 --> 01:19:17.550
величину векторов, где равно двум M, что

01:19:17.750 --> 01:19:20.587
на рисунке соответствует переносу вектора
ОО2.

01:19:21.538 --> 01:19:24.900
Поясним физический смысл получения новой
системы координат.

01:19:25.181 --> 01:19:30.264
После обслуживания заявки M равной один,
её место занимает следующая заявка из этой

01:19:30.344 --> 01:19:34.908
очереди, для которой ограничение на время
обслуживания совпадает с исходным.

01:19:35.188 --> 01:19:38.991
Ни одна из заявок других очередей за это
время не обслуживается.

01:19:39.398 --> 01:19:44.401
Или после окончания кванта ограничений на
время обслуживания этих заявок уменьшается

01:19:45.362 --> 01:19:47.163
ровно на продолжительность кванта.

01:19:47.243 --> 01:19:51.086
Многоэтапная процедура оптимизации
выполняется до тех пор, пока заявки всех

01:19:51.166 --> 01:19:52.807
очередей не будут обслужены.

01:19:53.007 --> 01:19:56.569
За ограниченное время и результатом
решения задачи будут оптимальное

01:19:56.649 --> 01:19:57.250
расписание.

01:19:57.680 --> 01:20:02.919
Обслуживание при задании, заданной длине
кванта, которые, собственно, и задаёт

01:20:03.039 --> 01:20:04.798
производительность ресурса.

01:20:05.078 --> 01:20:10.597
Если заявки всех очередей невозможно
обслужить с учётом заданных временных

01:20:10.717 --> 01:20:14.237
ограничений, необходимо повышать
производительность ресурса.

01:20:14.700 --> 01:20:19.100
Что приведёт к уменьшению длины кванта,
задающего продолжительность обслуживания

01:20:19.260 --> 01:20:24.380
одной заявки. Затем процедура синтеза
расписания должна быть выполнена вновь.

01:20:25.820 --> 01:20:31.100
Если заявки всех очередей можно
обслуживать за время меньше задаваемого

01:20:31.942 --> 01:20:36.057
Ограничение. Можно увеличить
продолжительность кванта с повторным

01:20:36.177 --> 01:20:40.971
выполнением процедуры для оптимизации
производительности ресурса.

01:20:41.490 --> 01:20:46.964
Утверждение: продолжительность временного
кванта обслуживания заявки в системе.

01:20:50.020 --> 01:20:52.217
Координат задаётся условием.

01:20:53.256 --> 01:20:56.773
Перепишите это условие.

01:21:00.769 --> 01:21:06.443
Доказательство, чтобы иметь возможность
обслуживать Mок совпадения ТМ.

01:21:07.024 --> 01:21:08.479
Худший для системы случай.

01:21:09.280 --> 01:21:11.522
Без приоритетная дисциплина обслуживания.

01:21:11.602 --> 01:21:17.125
Необходимо и достаточно, чтобы за время ТМ
каждая заявка единожды получала доступ к

01:21:17.205 --> 01:21:22.608
ресурсу, что возможно при условии выбора
положительного кванта, равного TM,

01:21:22.648 --> 01:21:23.929
разделить на M большое.

01:21:24.009 --> 01:21:29.171
Таким образом, использование векторного
метода синтеза расписания состоит в

01:21:29.251 --> 01:21:31.533
следующем: выбирая очередность

01:21:32.916 --> 01:21:37.153
Представленного кванта, синтезируем
дисциплину обслуживания, выбирая же

01:21:37.193 --> 01:21:41.151
величину кванта, определяем оптимальную
производительность ресурса.

01:21:44.389 --> 01:21:48.746
Методы векторной оптимизации имеют массу
практических приложений в нашей области

01:21:48.946 --> 01:21:52.303
знаний, однако существуют и ограничения на
их использование.

01:21:52.812 --> 01:21:56.653
Они могут использоваться лишь в том
случае, когда векторы качества вариантов

01:21:56.813 --> 01:21:59.894
решений совпадают для всех этих этапов
решения.

01:22:00.214 --> 01:22:05.616
Рассмотрим одно из исключений задачу
выбора оптимального маршрута.

01:22:05.816 --> 01:22:08.537
Решаем методом динамического
программирования.

01:22:08.995 --> 01:22:12.192
Основа метода динамического
программирования составляет уменьшение

01:22:12.352 --> 01:22:17.067
вычислительной сложности решения
оптимизации задачи перебор возможных

01:22:17.187 --> 01:22:20.504
маршрутов. Рассмотрим пример постановки.

01:22:22.143 --> 01:22:23.022
Видим маршрут.

01:22:30.550 --> 01:22:36.193
Перепишите либо зафиксируйте при помощи
телефона данную задачу.

01:22:37.473 --> 01:22:42.435
Принятие очередного очередного решения или
выбор маршрута равносилен выбору

01:22:42.715 --> 01:22:47.997
направления выхода из одного угла
коммутации куда попала.

01:22:48.984 --> 01:22:49.383
Сообщение

01:22:56.894 --> 01:22:58.772
метода динамического программирования.

01:22:58.892 --> 01:23:03.606
Возможный подход к решению задачи состоит
в полном переборе решений всех маршрутов

01:23:03.766 --> 01:23:05.524
из точки А в точку Б.

01:23:06.832 --> 01:23:08.517
Из точки А в точку Б.

01:23:10.133 --> 01:23:14.410
То есть могут быть рассчитаны длины путей
и выбран минимальный из них.

01:23:14.530 --> 01:23:18.527
Метод же динамического программирования
предполагает построение оптимального

01:23:19.006 --> 01:23:20.565
решения шаг за шагом.

01:23:20.645 --> 01:23:23.763
На каждом этапе оптимизируются отдельные
шаги.

01:23:23.963 --> 01:23:28.919
В основе решения лежит общая идея данного
класса методов, состоящая в том, что

01:23:29.079 --> 01:23:34.675
всегда алгоритмически проще многократно
решать простую задачу, чем однократно

01:23:34.795 --> 01:23:35.275
сложную.

01:23:35.850 --> 01:23:39.049
Проблема задач динамического
программирования состоит в том, что

01:23:39.129 --> 01:23:44.686
оптимизация маршрутов вне зависимости от
выбора оптимальных решений на последующих

01:23:44.766 --> 01:23:50.164
или предыдущих шагах невозможна, так как
выигрыш, полученный на отдельном шаге,

01:23:50.404 --> 01:23:55.201
может не дать совокупность выигрышей с
учётом всех выбранных шагов маршрута.

01:23:55.241 --> 01:23:57.600
То есть оптимальный маршрут может быть не
найден.

01:23:58.014 --> 01:24:02.138
Следовательно, планируя многошаговую
операцию на отдельном шаге в качестве

01:24:02.458 --> 01:24:09.265
оптимального, надо выбрать решение с
учётом всех его последствий, как на

01:24:09.385 --> 01:24:11.667
предыдущих, так и на последующих шагах.

01:24:11.988 --> 01:24:15.631
Метод динамического программирования
состоит в следующем: планируя вектор

01:24:17.272 --> 01:24:23.187
Эмный шаг делают различные предположения о
том, что чем закончится предыдущий M минус

01:24:23.307 --> 01:24:27.183
первый. И для каждого из этих
предположений находится так называемое

01:24:27.383 --> 01:24:30.300
условно оптимальное решение на эмном шаге.

01:24:30.620 --> 01:24:33.617
Условно оптимальное, так как данное
оптимальное решение находится

01:24:34.531 --> 01:24:39.491
Предположение, что при условии, что M -1
шаг закончился так-то.

01:24:39.771 --> 01:24:43.652
Аналогичным образом могут быть
последовательно выбраны условия,

01:24:43.692 --> 01:24:45.612
оптимальные шаги на всех этапах.

01:24:45.772 --> 01:24:48.932
В процессе оптимизации методом
динамического программирования

01:24:49.092 --> 01:24:50.052
многошаговый процесс

01:24:50.952 --> 01:24:52.311
Осуществляется дважды.

01:24:52.590 --> 01:24:59.503
Первое — от конца к началу с целью условий
оптимальных решений; второе — от

01:24:59.623 --> 01:25:03.340
начала к концу с целью определения
оптимального маршрута.

01:25:03.779 --> 01:25:05.378
Особенная интерпретация или

01:25:06.530 --> 01:25:08.728
Идея метода решения весьма проста.

01:25:08.968 --> 01:25:14.443
Если на промежуточных шагах существует
несколько вариантов проходя одного и того

01:25:14.643 --> 01:25:21.596
же пути между одним и теми же маршрутами

01:25:22.524 --> 01:25:27.766
Можно сравнить эти маршруты и оставить для
последующего анализа только один из этих —

01:25:27.886 --> 01:25:29.487
условно оптимальный.

01:25:29.847 --> 01:25:35.330
Вернёмся к примеру, опять же
проиллюстрируем нашу идею.

01:25:36.890 --> 01:25:37.891
Следуя из пункта

01:25:38.801 --> 01:25:43.041
Из точки Б в обратном направлении в
приложении, что мы указали в узле с

01:25:43.161 --> 01:25:43.441
номером

01:25:43.642 --> 01:25:51.842
21,

01:25:51.962 --> 01:25:56.603
что из УК 21 существует два маршрута в
точку Б.

01:25:57.752 --> 01:25:59.154
Выделены красным цветом.

01:25:59.274 --> 01:26:02.677
То есть мы можем сравнить эти два
маршрута.

01:26:02.797 --> 01:26:06.121
Между собой выбрано из них
условно-оптимальное решение, условно

01:26:06.201 --> 01:26:10.565
оптимальное, так как выбор производства
предположение, что сообщение

01:26:12.096 --> 01:26:13.618
Попала в УК-21.

01:26:13.698 --> 01:26:20.549
Критерий одного варианта определяется как
30 + 236, другого — 30 + 30 равно

01:26:20.629 --> 01:26:21.190
60.

01:26:33.780 --> 01:26:40.105
Другими словами, это мы определяем, что
при условии попадания сообщения в УК-21

01:26:43.428 --> 01:26:47.791
оно должно следовать по выбранному нами
оптимальному маршруту.

01:26:49.712 --> 01:26:52.394
Пойдём аналогично из точки Б по всем
направлениям

01:26:53.323 --> 01:26:58.508
Получаем определённый вариант оптимизации
задачи, состоящей из условно оптимальных

01:26:58.628 --> 01:27:00.143
решений. Смотрите рисунок.

01:27:17.643 --> 01:27:22.003
Теперь остаётся пройти из точки А в точку
Б по условиям условно-оптимальным

01:27:22.083 --> 01:27:26.364
маршрутом, рассчитать для них значение
критериев оптимальности выбора, выбрать

01:27:26.604 --> 01:27:29.924
оптимальный. Оптимальным будет маршрут,
выденный

01:27:30.875 --> 01:27:35.431
Красным цветом. Для этого определения не
потребовалось осуществлять полный перебор

01:27:35.511 --> 01:27:40.187
возможных маршрутов с расчётом для них
критерия оптимальности, с последующим

01:27:40.267 --> 01:27:42.865
сравнением всех возможных вариантов.

01:27:49.780 --> 01:27:52.218
На этом первая лекция подошла к концу.

01:27:52.938 --> 01:27:53.945
Спасибо за внимание.

