WEBVTT

00:00:10.067 --> 00:00:15.106
Лекция первая. Методы оптимизации их место
в теории исследования операций.

00:00:15.505 --> 00:00:19.424
Метод оптимизации как дисциплина
представляет собой раздел теории

00:00:19.584 --> 00:00:25.102
исследования операций, задачей которой
является поиск в рамках принятой модели

00:00:25.222 --> 00:00:25.742
решений.

00:00:26.459 --> 00:00:29.740
отвечающих экспериментальным значениям
критериям

00:00:38.583 --> 00:00:41.584
понятие лучшего что-либо означает, когда
определение

00:00:42.636 --> 00:00:46.992
Определён показатель или критерий качества
выбираемых решений.

00:00:47.352 --> 00:00:51.269
Любую операцию можно охарактеризовать
следующими составляющими.

00:00:53.387 --> 00:00:59.462
Стратегия, вариант решения называется
допустимый или возможный способ достижения

00:00:59.622 --> 00:00:59.982
цели.

00:01:02.009 --> 00:01:07.815
Действующими факторами операции называются
объективные условия, определяющие её

00:01:08.015 --> 00:01:11.018
особенности и влияющие на её исход.

00:01:15.783 --> 00:01:17.945
Критерием эффективности операций

00:01:18.687 --> 00:01:24.245
Или стратегией называется показатель
достигнутого соответствия между полученным

00:01:24.365 --> 00:01:27.084
результатом и целью операции.

00:01:27.884 --> 00:01:32.202
Состоянием операции в некоторый момент
времени называет совокупность её

00:01:32.522 --> 00:01:35.841
характеристик, проявляющихся в данный
момент.

00:01:37.068 --> 00:01:42.383
Под параметром стратегии понимается
локальное качество операции,

00:01:42.583 --> 00:01:48.937
обусловливаемое его действующими факторами
и учитываемое критерием эффективности

00:01:49.177 --> 00:01:55.531
стратегии. Под моделированием параметров
или, соответственно, моделирование системы

00:01:56.183 --> 00:02:01.584
Понимается определение зависимости
изменения локальных качеств или критериев

00:02:02.344 --> 00:02:06.505
оптимальности с учётом действующих
факторов операции.

00:02:07.705 --> 00:02:11.865
Математической моделью операции называется
формальное соотношение

00:02:12.540 --> 00:02:17.785
устанавливающие связь принятого критерия
эффективности с действующими факторами

00:02:18.025 --> 00:02:24.311
операции. Решением ограниченным множеством
решений, связанным с выбранной

00:02:24.431 --> 00:02:28.915
математической моделью, называется
конкретный набор значений и параметров

00:02:29.446 --> 00:02:33.683
полученных в результате использования этой
математической модели.

00:02:34.802 --> 00:02:40.557
Схематично этапы исследования операций
можно представить следующим образом

00:02:42.756 --> 00:02:45.473
Итак, содержание этапов, этапы.

00:02:46.020 --> 00:02:50.895
Формулировка цели операции, обусловленная
выбором критериев эффективности.

00:02:53.253 --> 00:02:59.768
Первый этап — анализ системы с целью,
выбор исходного множества стратегий,

00:02:59.888 --> 00:03:05.163
обоснованный выбор множества исходных
параметров, описывающих стратегию с учётом

00:03:05.803 --> 00:03:08.564
Сформулированной цели операции — второй
этап.

00:03:08.924 --> 00:03:12.725
Третий этап — при необходимости
моделирования параметров стратегии и

00:03:12.805 --> 00:03:15.526
построение математической модели
параметров.

00:03:16.366 --> 00:03:20.807
Четвёртый — построение математической
модели операции, получение формальной

00:03:20.927 --> 00:03:21.687
зависимости.

00:03:22.218 --> 00:03:26.698
Изменение критериев качества изменения
параметров системы.

00:03:27.777 --> 00:03:33.496
И пятый заключительный этап — получение
решения, выбор оптимального набора

00:03:33.616 --> 00:03:39.015
параметров, соответственно оптимальной
стратегии с учётом сформулированной цели

00:03:39.215 --> 00:03:39.855
операции.

00:03:41.650 --> 00:03:46.687
Вместо методов оптимизации в общей теории
исследования операций оптимальным образом

00:03:46.846 --> 00:03:52.602
решения формализованной задачи методы
оптимизации используются на

00:03:52.722 --> 00:03:56.359
четвёртом-пятом, при необходимости, на
третьем этапах.

00:04:04.495 --> 00:04:08.693
Системой называется упорядоченная
совокупность материальных объектов,

00:04:08.773 --> 00:04:14.211
элементов, объединённых-либо какими-либо
связями, например, механическими,

00:04:14.251 --> 00:04:17.849
электрическими и так далее,
предназначенными для достижения

00:04:18.209 --> 00:04:23.007
определённой цели. Если исходить из
понятия, что поведение системы есть

00:04:23.327 --> 00:04:25.566
последовательный ряд операций, то система

00:04:26.135 --> 00:04:28.414
Можно классифицировать следующим образом.

00:04:29.134 --> 00:04:34.814
Системы: детерминированные, вероятностные
и игровые.

00:04:36.454 --> 00:04:42.493
Детерминированной считается такая система,
в которой составные части взаимодействуют

00:04:42.653 --> 00:04:43.333
друг с другом.

00:04:43.932 --> 00:04:45.850
Точно предсказуемым образом.

00:04:46.090 --> 00:04:51.166
Её поведение предсказуемо, если известно
текущее состояние элементов и законы

00:04:51.286 --> 00:04:54.204
преобразования, циркулирующие между ними.

00:04:54.764 --> 00:04:58.761
Вероятностной называют систему, возможное
поведение которой

00:04:59.581 --> 00:05:03.218
Его последствия описываются на языке
теории вероятностей.

00:05:03.457 --> 00:05:09.013
Здесь знание текущего состояния и
особенности взаимной связи элементов

00:05:09.532 --> 00:05:15.887
недостаточно для однозначного предсказания
будущего, что обусловливает необходимость

00:05:16.086 --> 00:05:17.325
вероятностной оценки.

00:05:18.384 --> 00:05:24.858
Игровой называется система, осуществляющая
разумный выбор своего поведения в будущем.

00:05:25.137 --> 00:05:31.131
В основе выбора лежат неформальные
соображения, руководствоваться которыми

00:05:31.291 --> 00:05:32.889
может лишь человек.

00:05:36.606 --> 00:05:37.325
Другим важным

00:05:38.448 --> 00:05:42.527
Классификационным признаком системы
является её степень сложности.

00:05:42.647 --> 00:05:48.885
По этому признаку их разделяют на простые,
состояния которых немногочисленны и легко

00:05:49.005 --> 00:05:50.404
поддаются описанию.

00:05:51.124 --> 00:05:54.763
Сложные, отличающиеся разнообразием
внутренних связей

00:05:55.182 --> 00:06:00.786
... допускающие их описания
крупномасштабные, не поддающиеся

00:06:00.907 --> 00:06:02.908
каким-либо описанию связи.

00:06:03.669 --> 00:06:09.353
Важное место в исследовании различного
характера является структура системы и

00:06:09.553 --> 00:06:10.514
возможность её.

00:06:12.300 --> 00:06:17.540
Расчленяемости на подсистемы, каждая из
которых может иметь свой критерий

00:06:17.620 --> 00:06:24.419
эффективности. Принцип расчленяемости
системы находится в основе так называемого

00:06:24.859 --> 00:06:30.219
системного подхода, состоящего в том, что
задачу оптимизации можно упростить и

00:06:31.813 --> 00:06:36.531
Сформулировав и решив её для отдельных
подсистем с учётом того, в какой мере

00:06:36.691 --> 00:06:41.889
критерий эффективности подсистемы влияет
на критерий эффективности системы в целом

00:06:47.646 --> 00:06:52.324
эвристика оказывается полезной и
независимой при решении задач, имеющих

00:06:52.743 --> 00:06:56.099
...не числовой природой или
характеризуемых сложностью определения

00:06:56.339 --> 00:07:01.254
каких-нибудь параметров либо их
формализованного сравнения.

00:07:01.733 --> 00:07:06.488
Методы оптимизации классифицируются по
числу критериев оптимальности.

00:07:06.568 --> 00:07:09.325
Их подразделяют на однокретные...

00:07:12.370 --> 00:07:15.332
Критериальные либо многокритериальные.

00:07:15.732 --> 00:07:20.495
В последнем случае при выборе оптимального
решения необходимо учитывать уже не один

00:07:20.735 --> 00:07:25.378
критерий, а их совокупность, как правило,
характеризуемых

00:07:27.099 --> 00:07:31.142
разнородными параметрами, что усложняет их
сравнительную задачу.

00:07:31.720 --> 00:07:35.044
Здесь, как правило, не обойдётся без
ивристики.

00:07:40.291 --> 00:07:42.573
Однокретериальная оптимизация.

00:07:42.894 --> 00:07:46.618
Основные методы оптимизации используемые
при синтезе.

00:07:47.762 --> 00:07:50.600
Детерминированных сложных технических
систем.

00:07:52.319 --> 00:07:57.036
Первое — постановка и методы решения задач
математического программирования, линейное

00:07:57.156 --> 00:08:02.553
программирование. Формальная постановка
задач математического программирования.

00:08:02.953 --> 00:08:05.272
Будем в дальнейшем обозначать МП.

00:08:06.003 --> 00:08:11.561
Аббревиатурой в рамках

00:08:13.959 --> 00:08:20.116
задач однокреториальной оптимизации
наибольший интерес представляют методы,

00:08:20.156 --> 00:08:23.035
относящиеся к группе оптимального
планирования.

00:08:23.762 --> 00:08:25.443
При ограниченных ресурсах.

00:08:25.884 --> 00:08:31.767
Данными методами учитываются разнообразные
задачи, создание новой техники.

00:08:31.927 --> 00:08:36.610
Множество задач в том или ином виде может
быть сведено к постановке задачи

00:08:36.770 --> 00:08:38.732
математического программирования.

00:08:39.252 --> 00:08:43.455
С формальной точки зрения данная задача
относится к задачам математического

00:08:43.615 --> 00:08:44.415
программирования.

00:08:45.761 --> 00:08:50.122
Термин «программирование» здесь понимается
в смысле составления плана либо программы

00:08:50.242 --> 00:08:55.124
действий. Задача оптимизации состоит в
выборе наилучших планов.

00:08:55.404 --> 00:09:00.125
Несмотря на смысловое разнообразие задач,
все они формально сводятся к одной общей

00:09:00.245 --> 00:09:00.925
постановке.

00:09:01.792 --> 00:09:08.397
Найти значение переменных, образующих
максимум либо в минимуме значение

00:09:08.517 --> 00:09:09.758
целевой функции.

00:09:11.400 --> 00:09:17.524
Минимум, максимум, к который стремится
целевая функция F от X1, X2 и так далее X

00:09:22.892 --> 00:09:27.209
Замечание. В случае, когда целевая функция
из множества действительных чисел,

00:09:27.329 --> 00:09:34.005
используемых на практике, то целевая
функция называется скалярной и условие J1

00:09:34.285 --> 00:09:38.202
от X1x2 больше либо равно меньше либо
равно Б.

00:09:38.873 --> 00:09:41.272
Итая, где от единицы до M.

00:09:41.512 --> 00:09:46.990
Предположение, что в каждой из N строк
может присутствовать одно из рассмотренных

00:09:47.110 --> 00:09:52.989
ограничений, где функция Ж либо больше
либо равна Битого, либо меньше, либо равно

00:09:53.069 --> 00:09:57.467
Б ито. Называется областью определения
задачи.

00:09:58.189 --> 00:10:02.994
Целевая функция называется целевой,
которая может представлять собой критерий

00:10:03.114 --> 00:10:05.917
оптимальности при синтезе какой-либо
системы.

00:10:06.357 --> 00:10:11.683
Таким образом, целевая функция Z достигает
экстремального значения в одной или

00:10:11.883 --> 00:10:16.728
нескольких точек области определения,
которые требуется отыскать.

00:10:18.337 --> 00:10:24.141
Обычно в постановке задачи выбора,
оптимизации решения вид целевой функции Z

00:10:24.501 --> 00:10:31.386
и Ж известны и константы BIT, определены
специально оговариваются ограничения,

00:10:31.426 --> 00:10:36.550
выраженные в требуемых к неотрицательности
либо к целочисленным переменным.

00:10:37.440 --> 00:10:40.958
Краткая запись условий задачи
математического программирования имеет

00:10:41.118 --> 00:10:46.675
вид: X принадлежит области определения,
стремится к максимуму либо минимуму

00:10:46.795 --> 00:10:48.115
целевой функции.

00:10:49.674 --> 00:10:54.072
Два основных класса задачи математического
программирования — это задачи линейного и

00:10:54.152 --> 00:10:55.591
нелинейного программирования.

00:10:56.232 --> 00:11:00.756
К задачам линейного программирования
относятся те, к которым и целевая функция

00:11:00.876 --> 00:11:03.278
Z, и все функции Ж линейны.

00:11:03.638 --> 00:11:08.202
Задачи, к которым присутствуют как-либо
нелинейности, соответственно, называются

00:11:08.362 --> 00:11:10.924
задачами нелинейного программирования.

00:11:11.444 --> 00:11:15.287
В данном курсе лекции мы ограничимся
рассмотрением задач линейного

00:11:15.447 --> 00:11:16.088
программирования.

00:11:16.465 --> 00:11:21.706
...которые наиболее часто требуется решать
в нашей предметной области знаний.

00:11:24.866 --> 00:11:27.946
Линейное программирование, постановка
задачи.

00:11:28.306 --> 00:11:33.266
Задача линейного программирования в общей
постановке состоит в отыскании переменных

00:11:33.546 --> 00:11:35.467
X-1 и так далее X.

00:11:35.861 --> 00:11:42.382
образующих экстремум функции Z при
ограничениях

00:11:43.702 --> 00:11:50.544
дана системак1 + A12x2 и так далее A1x

00:11:50.984 --> 00:11:52.144
меньше либо равно Б1

00:11:53.130 --> 00:11:59.938
И так далее. Затем AM1x1 + AMX 2

00:12:00.098 --> 00:12:04.984
+ и так далее AMXN меньше либо равно Б.

00:12:05.344 --> 00:12:08.828
Обычно, кроме того, на практике добавляют
требования.

00:12:10.187 --> 00:12:14.951
Неотрицательности для любого X жито больше
нуля.

00:12:15.751 --> 00:12:20.756
Пример постановки задачи: ферма производит
откорм скота.

00:12:20.956 --> 00:12:25.119
Допустим, что имеется четыре вида
продуктов: П-1, П2, П3, П-4

00:12:26.357 --> 00:12:31.198
Стоимость единицы каждого продукта C1,
C2—34.

00:12:31.558 --> 00:12:37.119
Из этих продуктов требуется составить
пищевой рацион, который должен содержать

00:12:37.559 --> 00:12:41.880
белков не менее B1 единиц, углеродов не
менее B2 единиц.

00:12:42.631 --> 00:12:48.865
Жиров не менее Б3 единицы для продуктов
П1, П2, Б3, П4.

00:12:49.225 --> 00:12:55.059
Содержание белков, жиров и углеродов в
единицах на единицу продукции приведено в

00:12:55.139 --> 00:12:55.538
таблице.

00:13:03.455 --> 00:13:04.856
Смотрим на таблицу.

00:13:05.456 --> 00:13:11.861
Продукты: 1, П2, П3, Б4, элементы, белки,
углероды, жиры.

00:13:12.141 --> 00:13:18.626
Ну и коэффициенты, соответственно, матрица
данокоэффициентов A11, A12, A1—3

00:13:19.277 --> 00:13:26.072
Вторая строка: A21 A2 A3; третья — A31
A323; и четвёртая:

00:13:26.151 --> 00:13:32.826
A41 A42 A43, где A некоторые числа

00:13:33.146 --> 00:13:35.144
и продукт жилемент.

00:13:38.184 --> 00:13:43.709
Задача: составить такой пищевой рацион, то
есть определить количество продуктов П1,

00:13:43.789 --> 00:13:50.276
П-2, П-3, П-4, входящих в рацион, что при
минимальной стоимости рациона при

00:13:50.436 --> 00:13:53.960
условии выполнения ограничений белков и
жиров и углеродов.

00:13:54.995 --> 00:14:01.560
Целевая функция будет равна C1 на X1 + C2
на X2 + C3 на X3

00:14:01.961 --> 00:14:05.243
+ C4 на X4 и стремится к минимуму.

00:14:05.604 --> 00:14:12.569
Здесь мы за X1 и так далее XN обозначили
количество

00:14:12.769 --> 00:14:14.330
продуктов, которые должны входить

00:14:16.618 --> 00:14:21.856
Соответственно, составили систему
ограничений линейных

00:14:23.336 --> 00:14:29.094
ограничений в данном случае: A1x1 + A12x2
+13

00:14:29.733 --> 00:14:32.772
+14 больше либо равно Б1.

00:14:33.673 --> 00:14:39.754
Второе ограничение A21 X1 + A2X

00:14:40.554 --> 00:14:46.715
+ A23-3 + A4 либо равно

00:14:46.835 --> 00:14:50.036
B2. И последнее ограничение

00:14:53.254 --> 00:15:00.013
A13, A232; A33, A43-4 больше либо

00:15:00.053 --> 00:15:04.853
равно Б3. Любая переменная X больше либо
равна нулю.

00:15:05.333 --> 00:15:10.812
Замечание. Измените физический смысл
параметров данной задаче, и вы получите

00:15:11.012 --> 00:15:11.052
задачу

00:15:12.080 --> 00:15:17.317
Оптимизация загрузки ресурсов,
планирование загрузки многомашинной

00:15:17.477 --> 00:15:22.514
вычислительной системы и множества иных
задач из нашей предметной области.

00:15:26.952 --> 00:15:30.310
Геометрическая интерпретация задач.

00:15:30.700 --> 00:15:32.781
Обоснование подхода к решению.

00:15:34.021 --> 00:15:39.663
Все последующие рассуждения применимы к
формулированию задачи линейного

00:15:39.823 --> 00:15:44.265
программирования в стандартной форме,
имеющей следующее представление.

00:15:44.745 --> 00:15:46.586
Целевая функция равна сумме

00:15:47.771 --> 00:15:53.130
Ц на X и G изменяется от единицы до N.

00:15:53.290 --> 00:15:57.849
При этом целевая функция может стремиться
как к максимуму, так и к минимуму.

00:15:58.969 --> 00:16:04.488
Обратим внимание на систему равенств 1.1x1

00:16:04.728 --> 00:16:09.567
+1x2 и так далее +1xN равно B1.

00:16:11.082 --> 00:16:17.997
AM1x1 + AMX 2 + и так далее AMXN равно BM.

00:16:18.757 --> 00:16:23.194
Любую задачу линейного программирования
можно свести к подобному виду, в

00:16:23.274 --> 00:16:26.392
частности, можно изменить знак целевой
функции.

00:16:26.763 --> 00:16:28.282
...и минимизировать её.

00:16:28.562 --> 00:16:33.440
Перейти же от неравенства к равенству
можно введя дополнительные переменные.

00:16:34.519 --> 00:16:39.677
Ответить на вопрос: всегда ли задача имеет
решение, а также сформулировать требования

00:16:39.837 --> 00:16:42.315
к подходу решения можно на основании...

00:16:42.705 --> 00:16:44.668
Геометрической интерпретации.

00:16:45.028 --> 00:16:50.474
Геометрическая интерпретация постановки
решения задач наглядна при условии, что M

00:16:55.439 --> 00:16:57.281
равно K либо равно двум.

00:16:57.361 --> 00:16:58.883
То есть число в уравнении M

00:16:59.715 --> 00:17:01.913
На два меньше, чем число переменных N.

00:17:01.993 --> 00:17:06.787
В этом случае интерпретация может быть
проиллюстрирована на плоскости.

00:17:07.826 --> 00:17:12.461
Известно, что N линейно независимых
уравнений всегда можно решить относительно

00:17:12.780 --> 00:17:15.577
N базисных переменных, выразив их через

00:17:16.406 --> 00:17:23.080
Ка. В нашем случае свободные

00:17:23.240 --> 00:17:26.077
переменные, то есть две переменных будут.

00:17:26.237 --> 00:17:32.670
Свободные переменные обозначим свободными
переменными: X1.2, базисные X3—X4.

00:17:33.043 --> 00:17:36.400
Тогда из уравнения 1 можно получить
следующую систему.

00:17:38.277 --> 00:17:44.630
X3 равно A31x1 + A32 X2 + B3, X4 равно

00:17:44.710 --> 00:17:49.984
A41 X1 + A4x2 + B4 и так далее.

00:17:50.368 --> 00:17:56.974
X N равно An1x1 + ANX + BN Теперь будем

00:17:57.295 --> 00:18:00.698
изображать пару свободных переменных в
системе координат.

00:18:01.059 --> 00:18:05.783
Так как по определению переменные не
отрицательные, то первое условие

00:18:05.903 --> 00:18:07.545
допустимой области решения является

00:18:08.768 --> 00:18:10.810
Первый квадрат системы координат.

00:18:11.090 --> 00:18:17.977
Теперь уточним область допустимых решений
на плоскости X1 X2 с

00:18:18.057 --> 00:18:20.340
учётом заданных ограничений.

00:18:20.460 --> 00:18:24.263
Приравняем значение переменной X3 к нулю.

00:18:24.759 --> 00:18:27.479
И запишем исходное уравнение в следующем
виде.

00:18:27.839 --> 00:18:34.598
Ноль равен X3 и равно A31 X1 + A3 + Betta
3.

00:18:35.438 --> 00:18:42.438
В системе координат X1x2 данное уравнение
отображают соответствующие прямой.

00:18:44.509 --> 00:18:49.789
Если её наклон и расположение определяется
соответствующими коэффициентами, данная

00:18:49.909 --> 00:18:55.908
прямая характеризуется тем, что любое
расположенное на ней точка соответствует

00:18:56.028 --> 00:18:58.868
условию X-3, равному нулю.

00:18:58.988 --> 00:19:02.668
Соответственно, в зависимости от
коэффициентов, значение X-3 будет больше

00:19:02.868 --> 00:19:03.188
нуля.

00:19:03.983 --> 00:19:09.100
Выше отсекающей прямой меньше нуля, ниже
отсекающей прямой.

00:19:10.219 --> 00:19:15.057
Обратите внимание на рисунок X3 равно
нулю.

00:19:16.056 --> 00:19:17.696
Начертили прямую.

00:19:18.135 --> 00:19:18.775
Если у нас

00:19:19.905 --> 00:19:23.781
Ограничение больше либо равно, то движение
пойдёт вверх к данной прямой.

00:19:23.940 --> 00:19:28.655
Если меньше либо равно нулю, то прямая
будет направлена вниз.

00:19:30.134 --> 00:19:34.649
Аналогичным образом можно построить
соответствующие прямые для переменных.

00:19:35.600 --> 00:19:38.801
X4 и так далее, X.

00:19:43.323 --> 00:19:47.884
Обратим внимание опять же на рисунок,
когда X3 равнялось нулю, прямая у нас

00:19:49.605 --> 00:19:50.925
располагалась таким образом

00:19:52.083 --> 00:19:58.961
При X4, равное нулю вот данная прямая; при

00:19:59.041 --> 00:20:05.839
X5, равная нулю, следующая прямая и при
X6, равная нулю данный вид

00:20:06.119 --> 00:20:12.797
прямой. Совокупность данных прямых при
условии неотрицательных переменных.

00:20:13.744 --> 00:20:17.584
Отсекает область допустимых решений, если
она не пуста.

00:20:18.383 --> 00:20:24.103
Проведём подобную операцию с целевой
функцией, выразим Zerea функцию через

00:20:24.303 --> 00:20:30.782
свободные переменные и получим Z равно
гамма 1x1 + гамма 2.X 2 +

00:20:30.902 --> 00:20:31.822
гамма-нулевое.

00:20:32.465 --> 00:20:37.944
Где гамма-1, гамма-2 коэффициенты
гамма-нулевое — свободный член, который

00:20:38.304 --> 00:20:40.224
для простоты опустим.

00:20:40.304 --> 00:20:43.024
Обратим данное уравнение в ноль.

00:20:43.504 --> 00:20:49.423
Тогда, соответственно для данного
уравнения в системе координат X1

00:20:50.071 --> 00:20:55.585
О X2 может быть построена прямая,
проходящая через систему координат.

00:20:55.985 --> 00:21:01.578
Данная прямая называется опорной прямой
либо прямой целевой функции для любой

00:21:01.658 --> 00:21:04.974
точки, расположенной на ней, целевая
функция равна нулю.

00:21:05.294 --> 00:21:06.013
Обозначим

00:21:07.615 --> 00:21:12.016
Движение, в направлении которого целевая
функция возрастает или убывает.

00:21:12.617 --> 00:21:19.218
Итак, стрелочками показали вверх она будет
возрастать, целевая функция и

00:21:19.298 --> 00:21:21.059
вниз убывать.

00:21:24.700 --> 00:21:27.060
Из данной интерпретации видно, что

00:21:28.275 --> 00:21:32.596
В общем случае максимальное значение
целевой функции достигается в некоторой

00:21:32.796 --> 00:21:38.518
точке — области допустимых решений, в
точке пересечения прямых, определяющих

00:21:38.638 --> 00:21:40.358
область допустимых решений.

00:21:40.798 --> 00:21:43.279
В данном случае, если прямая у нас пойдёт
вверх

00:21:44.354 --> 00:21:51.038
Смотрите, то мы проводим параллельную
прямую при движении вверх и видим, что Z у

00:21:51.118 --> 00:21:53.880
нас вот точка в данном случае пересечения.

00:21:56.322 --> 00:22:01.405
Ответим на вопрос: всегда ли задача имеет
решение и всегда ли оно единственно?

00:22:01.845 --> 00:22:03.765
Для этого рассмотрим два случая.

00:22:04.725 --> 00:22:08.205
Показан рисунок: первый случай, второй
случай.

00:22:08.764 --> 00:22:12.124
Первое — область не ограничена сверху.

00:22:14.364 --> 00:22:16.963
Обратите внимание — не замкнутая фигура.

00:22:17.545 --> 00:22:23.501
Задача не имеет решения, так как всегда
можно найти значение лучше предыдущего.

00:22:23.740 --> 00:22:27.857
То есть, если мы будем двигать целевую
функцию по направлению вверх, она может

00:22:28.297 --> 00:22:30.176
возрастать до бесконечности.

00:22:30.735 --> 00:22:33.653
Второе — ограничение параллельно прямой.

00:22:34.296 --> 00:22:36.334
отображающий целевую функцию.

00:22:36.614 --> 00:22:41.049
В этом случае имеется бесконечное
множество решений, каждое из которых

00:22:42.687 --> 00:22:47.243
отображается точками на соответствующей
прямой области определения.

00:22:47.323 --> 00:22:49.201
И это оптимальное решение.

00:22:49.601 --> 00:22:53.597
То есть, если мы будем двигать данную
прямую, то у нас в каждой точке может быть

00:22:53.756 --> 00:22:53.996
решение

00:22:54.708 --> 00:22:57.066
И мы будем искать наиболее оптимальные.

00:23:00.463 --> 00:23:06.217
Замечание. Важно то, что к оптимальным
относятся и краевые точки, задаваемые

00:23:06.337 --> 00:23:09.374
пересечением прямых областей ограничения.

00:23:12.092 --> 00:23:12.691
Выводы.

00:23:13.193 --> 00:23:16.715
Основанный на геометрической интерпретации
задачи.

00:23:17.235 --> 00:23:21.837
Рассмотренная геометрическая интерпретация
в постановке задачи линейного

00:23:21.997 --> 00:23:27.320
программирования позволяет сделать важные
выводы относительно подхода к решению

00:23:27.560 --> 00:23:28.800
задач. Первое.

00:23:30.209 --> 00:23:35.888
Решение задачи будет краевая точка,
характеризуемая тем, что K равно N минус

00:23:36.008 --> 00:23:39.928
M. Свободных переменных в нашем случае две
переменные.

00:23:40.967 --> 00:23:46.087
Второе, как следствие, возможность решения
задачи состоит в переборе краевых точек.

00:23:47.405 --> 00:23:52.046
Третье. Переход от одной краевой точки к
другой состоит в замене свободных

00:23:52.206 --> 00:23:58.407
переменных. Очевидно, чтобы пытаться
решить задачу, можно простейшим способом

00:23:58.607 --> 00:24:02.488
задать свободные переменные и решить
систему уравнений.

00:24:02.688 --> 00:24:04.128
Это связано со следующими

00:24:04.674 --> 00:24:10.988
недостатками. Первое — можно получить
решение не в области допустимых решений.

00:24:11.547 --> 00:24:16.463
Второе — задача может быть весьма
громоздкой, например, Н равно тридцати, N

00:24:16.743 --> 00:24:19.820
10, то есть сочетание 10 из 30.

00:24:20.190 --> 00:24:22.431
Будет составлять огромное число.

00:24:22.871 --> 00:24:29.113
Обратите внимание 30 045

00:24:30.033 --> 00:24:36.875
015. Вывод: возникает задача направленного
перебора краевых

00:24:37.395 --> 00:24:41.397
вершин, то есть направленного перехода к
оптимальному решению.

00:24:42.107 --> 00:24:46.189
Как следствие, возникает задача,
обоснованная критерием оптимальности

00:24:46.389 --> 00:24:48.790
перехода между краевыми точками.

00:24:53.833 --> 00:24:58.155
К такому виду системы всегда сводится
ввиду линейности ограничений, так как

00:24:58.315 --> 00:25:00.556
всегда можно выразить переменные X1.

00:25:01.490 --> 00:25:04.852
И так далее, X2 через какие-либо
коэффициенты.

00:25:05.052 --> 00:25:12.014
F1c равно F1 со звёздочкой — это
коэффициенты X1 + и

00:25:12.174 --> 00:25:19.057
так далее X. FM X равно звёздочка от M, XM
+ 1 и

00:25:19.177 --> 00:25:20.097
так далее, X.

00:25:21.008 --> 00:25:26.086
В данном представлении переменные X1 и так
далее X называются свободными, все

00:25:26.286 --> 00:25:27.725
остальные базисными.

00:25:28.805 --> 00:25:34.202
Соответственно, при данном представлении
можно определить некоторые базисные

00:25:34.642 --> 00:25:39.200
базисные решения: X1 равно Б1, X равно БМ.

00:25:39.870 --> 00:25:43.508
X N равно X равно

00:25:43.588 --> 00:25:52.982
нулюс

00:25:53.102 --> 00:25:55.060
алгоритм процесса приближения к

00:25:55.592 --> 00:25:59.114
К оптиму направленный перебор кривых
решений.

00:26:00.035 --> 00:26:06.440
Пусть задача представлена соответственно
сразу получаемых несколько

00:26:07.321 --> 00:26:09.763
исходных базисных решений.

00:26:10.003 --> 00:26:11.604
Возникают следующие вопросы.

00:26:12.437 --> 00:26:15.039
Оптимально или единственно ли оно?

00:26:15.400 --> 00:26:21.165
Если не оптимально, а ранее мы показали,
что поиск решения состоит в переборе

00:26:21.245 --> 00:26:27.171
краевых вершин, то возникает вопрос: как
осуществить переход к следующему решению?

00:26:29.413 --> 00:26:32.816
Вспоминание, что целевая функция выглядит
следующим образом.

00:26:33.662 --> 00:26:40.548
Z равно сумма cita на X житое, где жи
изменяется от единицы до N.

00:26:41.589 --> 00:26:47.475
Просуммируем, соответственно, уравнения в
системе 2, умножив их на коэффициенты

00:26:47.555 --> 00:26:53.961
c-житое. Тогда система 2 будет
представлять следующий вид: c1 x1 + A

00:26:54.802 --> 00:26:58.525
1x M+1 и так далее.

00:26:58.725 --> 00:27:02.208
A1x N равно C1 на B1.

00:27:03.649 --> 00:27:10.454
И так далее. И последнее: C1x + AM + 1x +

00:27:10.614 --> 00:27:12.255
1 + AM X

00:27:13.220 --> 00:27:19.975
Равно c на BM Тогда целевая функция будет
иметь вид суммы

00:27:20.095 --> 00:27:22.534
Цжитое на X-житое + сумма

00:27:23.973 --> 00:27:28.689
м-1 X житое.

00:27:29.182 --> 00:27:36.135
Равно Z к нулевому + сумма CM + 1 X житое,

00:27:36.295 --> 00:27:42.809
где c + 1 житое, коэффициент свободных
переменных зависит от значения A

00:27:45.387 --> 00:27:51.022
По своему смыслувое значение целевой
функции для исходного базисного решения.

00:27:51.541 --> 00:27:58.456
Теорема. Допустимое базисное решение X
равно B иму; при i равно от

00:27:58.576 --> 00:28:01.253
единицы докс житое равно нулю.

00:28:02.442 --> 00:28:09.324
M + 1 и так далее M является оптимальным,
если коэффициент C MT

00:28:09.724 --> 00:28:15.806
в выражении 3 не отрицательным
доказательство

00:28:17.127 --> 00:28:19.768
переменные CMG больше либо равны нулю

00:28:20.178 --> 00:28:26.096
То при любых значениях неотрицательных
переменных их жито, разность Z и Z нулевое

00:28:26.176 --> 00:28:29.095
— не отрицательная, её минимум есть ноль.

00:28:29.255 --> 00:28:35.093
Следовательно, Z не будет меньше ЗТ
нулевого, что говорит о том, что его

00:28:35.253 --> 00:28:36.212
нельзя уменьшить.

00:28:36.794 --> 00:28:42.921
Следствие. Любые решения системы 1,
которому соответствует нулевая

00:28:43.522 --> 00:28:50.410
сумма cжиты и сжитое, при любых c-житых
больше либо равных нулю их

00:28:50.530 --> 00:28:52.092
житых больше либо равных нулю.

00:28:52.707 --> 00:28:57.225
Будет оптимальным, соответственно, при
условии, что CMжитые меньше нуля, решение

00:28:57.425 --> 00:28:58.664
может быть улучшено.

00:28:59.184 --> 00:29:05.780
Допустимое оптимальное базисное решение
окажется единственным, если все ЦМ, больше

00:29:06.060 --> 00:29:08.578
нуля, то есть строго больше.

00:29:10.622 --> 00:29:14.825
Данное следствие является
сформулированными признаками оптимальности

00:29:15.185 --> 00:29:17.747
и единственными оптимальными решениями.

00:29:18.187 --> 00:29:23.911
Теперь рассмотрим, как осуществить переход
к новому решению и сформулируем критерии

00:29:23.951 --> 00:29:26.753
оптимальности выбора направления перехода.

00:29:27.407 --> 00:29:31.645
Пусть среди коэффициентов ЦМЖ есть
отрицательное значение.

00:29:31.845 --> 00:29:37.563
Это значит, что данное давая приращение
соответствующим переменным, целевая

00:29:37.683 --> 00:29:43.122
функция целевую функцию можно уменьшить,
чтобы перейти к другому целевому решению.

00:29:44.372 --> 00:29:50.409
Как следует из неотрицательности
необходимо сделать положительной, ввести в

00:29:50.489 --> 00:29:57.326
базис какую-то переменную X+1, равную X,
равную нулю, обратив в нуль

00:29:57.526 --> 00:30:01.724
одну из переменных X1 либо X,
соответственно, в базис.

00:30:02.519 --> 00:30:09.204
Должно вводиться та переменная, ей даётся
положительное преращение, соответственно,

00:30:09.804 --> 00:30:14.567
которая имеет выражение для целевой
функции отрицательный коэффициент.

00:30:15.728 --> 00:30:22.413
Обозначим через S тот номер J или N + 1 N
величины коэффициентов m и J.

00:30:22.978 --> 00:30:27.462
Для которого сочетание минимально.

00:30:27.542 --> 00:30:33.507
Отсюда бросается в глаза очевидный подход
к поиску оптимального решения, который и

00:30:33.588 --> 00:30:38.792
используется в системе ограничений.

00:30:39.267 --> 00:30:43.870
Соответственно, будем давать положительное
приращение к переменной X.

00:30:45.631 --> 00:30:52.196
Давая данное приращение, из уравнения 2
получим X1 равно Б1

00:30:55.956 --> 00:31:01.678
A1s X равно BM + AMS.

00:31:01.798 --> 00:31:08.760
Для Z и Z равно Z нулевое + CMS.

00:31:09.000 --> 00:31:11.040
Причём CMS меньше нуля.

00:31:11.791 --> 00:31:17.753
Естественно, что выбрав направление
движения, целесообразно максимально

00:31:18.033 --> 00:31:23.875
увеличить переменную X, чтобы получить
максимальное выражение в значении целевой

00:31:24.075 --> 00:31:30.758
функции. Однако возрастание переменной X
ввиду требования к неотрицательной

00:31:30.838 --> 00:31:31.198
переменной

00:31:32.024 --> 00:31:37.024
Возможны до тех пор, пока какая-то из
свободных переменных не обратится в ноль.

00:31:37.424 --> 00:31:40.464
То есть, пока не достигнем ограничения
значения.

00:31:41.104 --> 00:31:46.784
Это произойдёт, если хотя бы один
коэффициент с индексом XS положительным по

00:31:46.864 --> 00:31:49.903
условию и среди Bит нет отрицательных.

00:31:51.289 --> 00:31:57.447
Если все A и S положительные, то первая в
ноль обратится та базисная переменная, для

00:31:57.567 --> 00:32:00.766
которой будет выполняться X равно
минимуму.

00:32:01.686 --> 00:32:07.285
Это есть формализованное условие перехода
к последующей краевой вершине.

00:32:10.166 --> 00:32:11.367
Симплекс-метод.

00:32:12.287 --> 00:32:18.732
В решении было показано, что система
ограничений предполагает направленный

00:32:18.892 --> 00:32:20.653
перебор краевых вершин.

00:32:21.014 --> 00:32:25.697
Мы определились с тем, каким образом
осуществлять данный перебор, как выбрать

00:32:25.897 --> 00:32:30.420
направление перебора, как определить, что
в итоге получено оптимальное решение.

00:32:31.091 --> 00:32:35.493
Всё это ранее было выражено в формальном
виде, приведены соответствующие формулы

00:32:35.693 --> 00:32:41.897
для расчётов. Однако остаётся проблема,
состоящая в том, как найти то первое

00:32:42.017 --> 00:32:46.619
допустимое решение, а это должна быть
краевая точка, с которой начинать

00:32:46.899 --> 00:32:48.820
направленный перебор вершин.

00:32:49.322 --> 00:32:53.286
То есть, когда уже установленная
возможность применения решения.

00:32:53.566 --> 00:33:00.053
Для этого цели и служит математическая

00:33:00.213 --> 00:33:04.297
система, со симплекс метода, состоящий

00:33:05.247 --> 00:33:07.126
Двухэтапном решении задачи.

00:33:07.446 --> 00:33:12.282
На первом этапе требуется найти какое-либо
решение задачи, то есть найти исходную

00:33:12.442 --> 00:33:16.360
краевую точку, на втором — осуществить
перебор решения с целью поиска

00:33:16.440 --> 00:33:17.799
оптимального решения.

00:33:18.159 --> 00:33:22.836
При этом будем помнить, что краевая точка
легко отыскивается в случае представления

00:33:22.996 --> 00:33:23.435
задачи.

00:33:26.603 --> 00:33:32.691
... краевых вершин. Симплекс-метод
предполагает в общем случае двухэтапное

00:33:33.091 --> 00:33:36.976
решения данных задач.

00:33:37.136 --> 00:33:42.622
Первый этап начинается су-с формального
введения в каждую строчку.

00:33:43.193 --> 00:33:47.870
Стандартной системы искусственной
неотрицательной переменной для получения

00:33:48.909 --> 00:33:54.025
краевых вершин. Например, что при
представлении задачи в данном виде сразу

00:33:54.305 --> 00:33:56.863
можно определить решение задачи.

00:33:58.142 --> 00:34:04.218
Дана исходная задача A1x1+ и так далее A1x
равно Б1.

00:34:04.922 --> 00:34:11.000
И так далее. A1x1+ и так далее AMXN равно
BM.

00:34:12.400 --> 00:34:19.278
Краевая вершина вводятся новые переменные
и приравниваются данные системы

00:34:19.398 --> 00:34:19.838
равенств.

00:34:21.194 --> 00:34:28.034
...вновь введённым переменным B1B Однако

00:34:28.235 --> 00:34:33.755
этим мы изменили собственно задачу, в
которой в каком случае решения новой

00:34:33.875 --> 00:34:36.515
задачи и исходной задачи будет совпадать.

00:34:36.995 --> 00:34:41.795
Если существует решение для первой задачи,
то оно допустимо и для второй при условии,

00:34:41.835 --> 00:34:42.315
что X...

00:34:43.296 --> 00:34:46.415
M+1 равно M+ N равно нулю.

00:34:46.775 --> 00:34:52.533
Так как именно эти переменные были нами
введены ввиду их неотрицательности, при

00:34:52.733 --> 00:34:55.492
данном случае все переменные обращаются в
ноль.

00:34:56.012 --> 00:35:00.091
Рассмотрим сумму наименьших значений,
которое есть ноль.

00:35:00.705 --> 00:35:07.187
Ввиду неотрицательности переменных при X +
1 равно X плюс N равно

00:35:07.307 --> 00:35:13.989
нулю. Таким образом, проверка условия
минимума суммы для второй

00:35:14.069 --> 00:35:18.431
системы ограничений является условием
совпадения решения для первой и второй

00:35:18.551 --> 00:35:18.951
задач.

00:35:22.035 --> 00:35:28.350
С учётом сказанного, первый этап решения
Simplex метода состоит в поиске

00:35:28.470 --> 00:35:32.627
какого-либо решения исходной задачи
посредством решения следующей

00:35:33.107 --> 00:35:38.463
оптимизационной задачи, то есть если мы
будем находить минимум

00:35:39.321 --> 00:35:44.362
Симплекс методов с учётом ограничений
ограничений системы, заданной для второй

00:35:44.482 --> 00:35:51.403
задачи. Для данной задачи приведён краевой
вершине, то есть можно быть применён

00:35:51.603 --> 00:35:57.004
Simplex метод, легко находится первое
решение X+1 равно Б1 и так далее.

00:35:57.472 --> 00:35:59.793
X M + N равно BM.

00:36:00.233 --> 00:36:03.474
А X1 и так далее X равно нулю.

00:36:03.674 --> 00:36:09.796
После чего может быть использована система
с целью поиска оптимального решения.

00:36:10.276 --> 00:36:13.437
Если удаётся найти оптимальное решение,
для которого

00:36:14.054 --> 00:36:19.218
Если сумма равна нулю, то это решение
является исходным для основной задачи.

00:36:19.498 --> 00:36:22.461
В противном случае задача неразрешима.

00:36:31.628 --> 00:36:32.108
Смотрите.

00:36:33.150 --> 00:36:38.546
Прямоугольная система координат: ось
абцесса T1, ось координат — Tx2.

00:36:38.865 --> 00:36:41.303
Сумма равна нулю в данной точке.

00:36:41.783 --> 00:36:48.137
Основная задача — выпуклый многоугольник и
вспомогательн-вспомогательная задача

00:36:48.257 --> 00:36:49.576
линейного программирования.

00:36:50.358 --> 00:36:52.400
В данном случае определено на графике.

00:36:53.200 --> 00:36:57.483
Второй этап состоит в решении основной
задачи, в использовании

00:36:59.965 --> 00:37:03.247
решения системы уже для решения основной
задачи.

00:37:03.407 --> 00:37:06.208
При этом получим решение вспомогательной
задачи.

00:37:06.499 --> 00:37:12.578
Рассмотренная как исходная для основной
проверяется на оптимальность при

00:37:12.738 --> 00:37:17.696
необходимости осуществления
последовательного перебора решений.

00:37:19.216 --> 00:37:22.735
Замечание. Здесь уже используется целевая
функция Z.

00:37:26.882 --> 00:37:31.119
Примеры решения задачи линейного
программирования Simplex Metodom.

00:37:31.439 --> 00:37:37.315
Пусть имеется некоторый материал в виде
стандартных листов, который надо раскроить

00:37:37.675 --> 00:37:43.711
таким образом, чтобы получить не менее 80
деталей первого типа и не менее 42.

00:37:44.483 --> 00:37:49.686
Известно четыре способа раскроя листа
листа, для которого результаты раскроя

00:37:49.806 --> 00:37:51.647
представлены в таблице.

00:37:52.728 --> 00:37:57.931
Итак, Cn равно 1, 2, 3, 4.

00:37:58.932 --> 00:37:59.932
Четыре способа.

00:38:02.927 --> 00:38:08.531
В данном случае П — некоторый материал и
указаны

00:38:09.611 --> 00:38:16.495
коэффициенты Требуется получить
необходимое число деталей

00:38:16.615 --> 00:38:20.938
при минимальном расходе листов материала,
обозначим через их сжитое количество

00:38:21.098 --> 00:38:21.538
листов.

00:38:22.065 --> 00:38:24.507
Расходуемых жим столбцом.

00:38:24.627 --> 00:38:30.872
Целевая функция в данном случае будет
иметь вид равно X1 + X 2 + X 3 + X

00:38:31.072 --> 00:38:37.197
4. При этом должны выполняться следующие
условия: 31,

00:38:38.078 --> 00:38:39.399
2x2 +

00:38:40.052 --> 00:38:46.010
X3 больше либо равно восьмидесяти X1

00:38:47.250 --> 00:38:51.088
+6 X2 + 2 X3

00:38:54.647 --> 00:38:55.367
X3, да?

00:38:55.763 --> 00:38:58.320
И 134 больше либо равна

00:38:58.480 --> 00:39:05.154
40, в данном случае опечатка не 2x3, а

00:39:05.233 --> 00:39:11.068
93. Для применения симплекс-метода прежде
всего задачу требуется привести к

00:39:11.148 --> 00:39:12.147
стандартному виду.

00:39:12.729 --> 00:39:16.850
То есть систему ограничений мы должны
привести к системе равенств.

00:39:17.210 --> 00:39:23.172
Вводим новые переменные: 3x1 + 2, X2 + X
3.

00:39:23.849 --> 00:39:29.970
Минус X5 равно 80, X1 +6 X2 + 9 X3 + 13 X4

00:39:30.250 --> 00:39:32.610
-X6 равно 40.

00:39:32.850 --> 00:39:36.371
Вводятся новые переменные, при этом они не
должны повторяться.

00:39:36.691 --> 00:39:40.612
У нас в заданной системе ограничений
четыре переменные.

00:39:40.772 --> 00:39:44.772
Значит, вводим дополнительные, которые не
повторяются, — это X5 и X6.

00:39:45.510 --> 00:39:50.395
Таким образом, так как ограничения были
больше либо равно, из каждой строки нужно

00:39:50.596 --> 00:39:52.878
вычесть, соответственно, переменную.

00:39:53.118 --> 00:39:59.925
Очевидно, базисное решение: -к 5 равно
восьмидесяти, -к6 40, X1 и так далее,

00:39:59.965 --> 00:40:01.327
X4 равны нулю.

00:40:05.035 --> 00:40:09.319
Недопустимо ввиду неотрицательности
переменной, так как данное решение

00:40:09.519 --> 00:40:13.003
недопустимо. Задачу необходимо решить в
два этапа.

00:40:13.604 --> 00:40:20.571
Первый этап — решение вспомогательной
задачи приведём исходную задачу к краевым

00:40:20.651 --> 00:40:21.172
вершинам.

00:40:23.698 --> 00:40:29.818
Наша система примет следующий вид: 31 +
2x2 + X 3 -X 5 + X 7 равно

00:40:29.937 --> 00:40:36.137
80. Второе равенство: X1 +6 X2 + 9 X 3 +
13

00:40:36.376 --> 00:40:39.616
X4, -x6 + X8 — равно 40.

00:40:40.991 --> 00:40:46.310
сорока. Для этого введём дополнительные
переменные x7, X8, соответственно,

00:40:47.350 --> 00:40:52.069
сформулируем и решаем данную задачу
целевой функции, которая должна быть

00:40:52.389 --> 00:40:57.869
минимизирована, помня, что её решение
будет решением основной при условии, что

00:40:57.949 --> 00:40:58.948
сумма равна нулю.

00:40:59.490 --> 00:41:05.054
Здесь легко отыскивается исходное
значение: X7 равно восьмидесяти,

00:41:05.214 --> 00:41:12.017
X840, X1 и так далее, X6 — нулевое; сумма
80 + 40 — 120.

00:41:14.179 --> 00:41:16.020
Применим следующий метод.

00:41:16.508 --> 00:41:22.024
систем. И прежде всего проверим получение
решения на оптимальность Рассмотрим

00:41:22.144 --> 00:41:29.019
целевую функцию, равную сумме X7 + X8, в
которой переменные X7 X8 выразим

00:41:29.139 --> 00:41:30.578
через остальные.

00:41:30.938 --> 00:41:37.093
Итак, сумма равна X7 + X8 равна 80 - 3 X1
- 2x2

00:41:37.752 --> 00:41:44.278
X3 + X5 + 40, -X1 — -6 X2, -9 X3 — - 13

00:41:44.599 --> 00:41:46.080
X4 + 6.

00:41:46.320 --> 00:41:53.287
В результате нахождения подобных
переменных получаем 120 - 4, -8 X2 — -

00:41:53.407 --> 00:41:54.048
10 X-3

00:41:54.644 --> 00:41:58.646
Минус 13 X4 + 5 и + X6.

00:42:00.167 --> 00:42:05.770
Присутствие отрицательных коэффициентов
указывает на неоптимальность полученного

00:42:05.890 --> 00:42:11.333
решения. Так как максимальное по модулю
отрицательное значение коэффициента имеет

00:42:11.533 --> 00:42:16.255
переменные X4, то в соответствии с
рассмотренным ранее критериями

00:42:16.632 --> 00:42:19.673
Именно ей будет давать положительное
превращение.

00:42:19.753 --> 00:42:21.593
X3 равно X4.

00:42:21.954 --> 00:42:27.315
Теперь рассмотрим, для какой величины
можно увеличить X-4, а при этом переменная

00:42:27.515 --> 00:42:33.877
обнулится. X7 равно восьмидесяти, X8 равно
40, - 13 X4.

00:42:35.250 --> 00:42:41.257
Вводя положительную переменную X4 из
исходной системы для нашего решения имеем.

00:42:41.377 --> 00:42:47.184
Таким образом, видим, что X4 можно
увеличить до значения 413.

00:42:47.344 --> 00:42:51.228
При этом X8 обратится в ноль и получим
новое решение.

00:42:51.956 --> 00:42:58.598
X1 равно X2 равно X3 равно нулю; X4 равно
413; X5 равно X6

00:42:58.799 --> 00:43:03.800
равно нулю; X7 равно восьмидесяти; X8 80.

00:43:03.880 --> 00:43:07.322
Сумма будет равна 80 + 43.

00:43:07.722 --> 00:43:11.323
Проверим полученное решение на
оптимальность, для этого выразим целевую

00:43:11.403 --> 00:43:11.883
функцию.

00:43:12.505 --> 00:43:16.743
Так как 8 равно нулю, выразим только X7.

00:43:18.342 --> 00:43:24.659
Ну и получается у нас сумма будет равна X7
+ X8 равно - 3 X1, - 2

00:43:24.819 --> 00:43:28.417
X2, -X 3 + X 5, -X8.

00:43:29.847 --> 00:43:34.284
Видим, что решение не оптимально, и так
как максимальный отрицательный коэффициент

00:43:34.484 --> 00:43:39.281
имеет переменная X1, то именно ей надо
дать положительное превращение.

00:43:39.641 --> 00:43:44.878
Определим, до каждого значения можно
увеличить X1 и какая при этом переменная

00:43:44.998 --> 00:43:45.478
обратится в

00:43:46.215 --> 00:43:49.014
X4 X7 — не нулевые значения.

00:43:49.693 --> 00:43:56.089
Тогда X7 будет равно 80 - 3 X1, X4 40 -X1
разделить на

00:43:56.169 --> 00:44:02.525
13. X1 может разность достигнет разности
до

00:44:02.685 --> 00:44:04.084
83.

00:44:04.649 --> 00:44:11.447
При этом обращается в ноль, X7 получаем X1
равно

00:44:11.567 --> 00:44:18.484
восемь третьих, X4:40 — 39; X2: X3; X5;
X6; X7; X8

00:44:19.124 --> 00:44:20.003
равно нулю.

00:44:20.539 --> 00:44:24.341
Сумма будет равна нулю, x7, x8.

00:44:24.781 --> 00:44:26.341
Это оптимальное решение.

00:44:26.821 --> 00:44:31.583
Так как целевая функция не содержит
отрицательных коэффициентов, её минимум

00:44:31.743 --> 00:44:36.265
есть ноль, то найденное оптимальное
решение может рассматриваться как исходное

00:44:36.385 --> 00:44:37.505
решение для выполнения

00:44:37.950 --> 00:44:41.946
Второго этапа. Второй этап — система
равенств.

00:44:42.306 --> 00:44:49.300
Первое: 31 + 2 X2 + X 3 - X5 равно
восьмидесяти; X1 +6 X2 + 9

00:44:49.460 --> 00:44:52.897
X 3 + 13 X4 - X6 равно 40.

00:44:53.137 --> 00:44:54.336
Исходное решение.

00:44:54.829 --> 00:45:01.667
X1 равно восемьдесят третьих, X4:4039 X2:
X3: X5; X6;

00:45:01.707 --> 00:45:07.386
X7 X8 равно нулю; сумма X равна X7.8 —
равна нулю.

00:45:07.746 --> 00:45:11.705
Имея допустимое базисное решение,
полученное на первом этапе решения,

00:45:11.785 --> 00:45:13.744
начинаем решение основной задачи.

00:45:15.113 --> 00:45:21.868
Второй этап. Прежде всего проверим
оптимальность полученного решения.

00:45:21.987 --> 00:45:24.146
Для этого выразим X1 и X4.

00:45:24.346 --> 00:45:31.260
Получаем из четвёртой системы: X1 равно 80
- 2 X2 - X3 + X5,

00:45:31.300 --> 00:45:34.178
делённое на 3; X4 равно 40 минус

00:45:34.884 --> 00:45:39.868
X 1 - 2 X 2 -9 X 3 + X 6, делённое на 13

00:45:40.672 --> 00:45:46.546
Целевая функция Z будет равна X1 + X2 + X3
+ X4 и равна.

00:45:46.706 --> 00:45:51.940
Подставляем вместо X1 X4 коэффициенты
находим подобное.

00:45:51.980 --> 00:45:58.733
В результате получим 1 080 - 3 X2 + 12 X1
+ 36 делное на

00:45:58.813 --> 00:45:59.532
39.

00:46:00.293 --> 00:46:06.685
Вывод. Полученное решение не оптимально,
следует дать при ращение переменной X2.

00:46:06.925 --> 00:46:12.118
Для определения того, насколько
увеличивать X-2, выразим наши нулевые

00:46:12.158 --> 00:46:14.995
переменные X1 X4 через X2.

00:46:15.274 --> 00:46:15.634
Получим

00:46:17.487 --> 00:46:24.373
X1 равно 80 - 2 X2, дел на 3, X4 равно 40
минус 16 X2, делённое

00:46:24.493 --> 00:46:27.976
на 39. X1 выражаем через X2.

00:46:28.296 --> 00:46:32.500
Отсюда получаем, что X2 может
увеличиваться на 2,5.

00:46:33.130 --> 00:46:36.570
0,5, при этом X4 превращаем в ноль.

00:46:36.850 --> 00:46:42.890
X1 равно 25, X2 — 2,5, X3, X6 — нулю.

00:46:42.970 --> 00:46:47.450
Целевая функция будет равна 27,5.

00:46:47.890 --> 00:46:50.050
Проверим данное решение на оптимальность.

00:46:51.024 --> 00:46:57.339
Для этого выразим целевую функцию через
переменные X1 X2.3 X4.

00:46:57.819 --> 00:47:04.414
Подставим вместо X значения вместо X-14
получим 440

00:47:04.933 --> 00:47:10.289
+ 2 X 3 + 3 X 4 + X5 + 5 X6 разделить на
16.

00:47:10.915 --> 00:47:15.357
Вывод. Данное решение задачи является
оптимальным и единственным.

00:47:15.557 --> 00:47:21.760
Таким образом, оптимальный способ раскроя
листов посмотрите ещё раз задачу, состоит

00:47:21.880 --> 00:47:28.362
в следующем: 25 крой первым кроить первым
способом, 25 вторым.

00:47:28.807 --> 00:47:33.287
В результате потребуется 25 с половиной
листов.

00:47:36.047 --> 00:47:37.927
Недостатки Simplex метода.

00:47:38.087 --> 00:47:42.687
Метод решения основанный на геопетрической
интерпретации задачи линейного

00:47:42.847 --> 00:47:45.767
программирования. Собственно, критерий
оптимальности

00:47:46.342 --> 00:47:52.455
не призван оптимизировать вычислительную
процедуру, так как сложность вычислений

00:47:52.574 --> 00:47:58.048
представляется числом перебираемых вершин,
в то время как критерии оптимальности не

00:47:58.168 --> 00:48:02.083
минимизируют их числа при поиске
оптимального решения.

00:48:03.306 --> 00:48:09.350
Сложность использования вычислительных
средств для решения задачи алгоритмы,

00:48:09.390 --> 00:48:12.752
ориентированные на применение
вычислительных средств, должны

00:48:13.112 --> 00:48:18.916
характеризоваться по возможности
простейшими операциями: плюс, минус и так

00:48:19.076 --> 00:48:19.437
далее.

00:48:19.675 --> 00:48:24.319
Здесь же, при обработке каждого решения
необходимо решать достаточно сложные

00:48:24.439 --> 00:48:29.084
системы уравнений, что сложно
формулируется на AVM.

00:48:29.204 --> 00:48:34.609
Таким образом, можно сделать вывод, что
для решения задач больше размерности, где

00:48:34.809 --> 00:48:36.250
необходимо применение AVM.

00:48:36.877 --> 00:48:43.361
Необходимы иные подходы, следовательно,
другая интерпретация задачи и

00:48:43.521 --> 00:48:45.162
критерии оптимальности.

00:48:45.602 --> 00:48:49.645
Особенно сложен Simplex метод для решения
целочисленных задач.

00:48:52.007 --> 00:48:54.728
Целочисленное программирование — метод
гаммо.

00:48:56.852 --> 00:49:02.451
Задачи, сформулированные в терминах
линейного программирования и содержащие

00:49:02.571 --> 00:49:08.050
требования все или некоторые переменные,
целые числа называются задачами

00:49:08.290 --> 00:49:10.370
целочисленного программирования.

00:49:10.690 --> 00:49:13.369
Рассмотрим пример интерпретации задачи.

00:49:19.024 --> 00:49:25.939
Задана прямоугольная система координат,
дана выпуклая

00:49:25.979 --> 00:49:27.858
фигура.

00:49:28.297 --> 00:49:33.374
Девять точек, которые находятся в данной
области, и целевая функция

00:49:35.092 --> 00:49:36.292
определена прямой.

00:49:37.047 --> 00:49:42.531
Пусть к X1 выставлены требования
целочисленности.

00:49:42.732 --> 00:49:47.015
Решение задачи в этом случае будет
располагаться на соответствующих

00:49:47.175 --> 00:49:51.899
непересекающихся линиях, характеризующих
целочисленность переменных.

00:49:52.220 --> 00:49:54.261
Если обе переменные целочисленные

00:49:54.934 --> 00:49:59.371
То решение задачи определяется узлами
соответствующей решётки на плоскости

00:50:00.090 --> 00:50:05.686
метода гаммори, состоит из выполнения
следующих шагов.

00:50:07.005 --> 00:50:11.122
Решается задача классическим
сиблекс-методом, и полученное решение

00:50:11.362 --> 00:50:12.961
проверяется на целочисленность.

00:50:13.402 --> 00:50:19.123
Если полученное решение не целочисленное,
вводят по определённым правилам систему

00:50:19.243 --> 00:50:23.803
ограничений, отсекающих полученное решение
и задача решается вновь.

00:50:24.043 --> 00:50:27.724
Процедура повторяется, пока не найдено
целочисленное решение.

00:50:28.124 --> 00:50:28.604
Вывод.

00:50:29.083 --> 00:50:33.964
Условия целойчисленности принципиально
усложняют решение задачи, так как в общем

00:50:34.124 --> 00:50:39.566
случае требует многократное применение
симплекс-метода с увеличением области

00:50:39.726 --> 00:50:42.767
ограничения, с введением дополнительных
условий.

00:50:57.800 --> 00:51:03.674
Методы оптимизации ориентированы на
применение VM, общий подход к построению.

00:51:07.990 --> 00:51:14.424
Сложный подход в математической задаче.

00:51:15.502 --> 00:51:21.739
Методом потенциалов называется
необходимость разработки методов

00:51:21.818 --> 00:51:26.496
оптимизации, базирующихся на
вычислительных и логических операциях.

00:51:26.896 --> 00:51:31.294
Общей для этих методов является
необходимость доказательства

00:51:31.534 --> 00:51:33.573
целесообразности и достаточности.

00:51:34.338 --> 00:51:38.376
Целесообразность обусловливается
интерпретацией или физическим смыслом

00:51:38.455 --> 00:51:42.972
метода решения достаточным доказательством
исходности алгоритма.

00:51:43.789 --> 00:51:48.352
Каждый алгоритм предполагает некоторое
правило поиска решений и обусловливает

00:51:48.512 --> 00:51:50.354
переход к последующему решению.

00:51:50.794 --> 00:51:56.319
Отношения, связывающие очередные решения
при использовании алгоритма называется

00:51:56.479 --> 00:51:58.400
алгоритмическим отображением.

00:51:58.641 --> 00:52:01.923
Алгоритм, построенный на основе
отображения, сходится

00:52:02.640 --> 00:52:05.280
если он позволяет либо непосредственно

00:52:09.921 --> 00:52:15.402
вычислить оптимальное экстремальное
значение, либо представляет его в виде

00:52:15.602 --> 00:52:19.802
некоторой предельной точки с задаваемой
последовательностью приближения

00:52:20.694 --> 00:52:26.177
В общем случае следует говорить о
сходимости алгоритма в смысле

00:52:26.737 --> 00:52:29.618
существования подобной предельной точки.

00:52:30.179 --> 00:52:34.941
Основной группой методов оптимизации,
ориентированных на использование ЛММ,

00:52:35.021 --> 00:52:37.742
является так называемые методы возможных
направлений.

00:52:38.362 --> 00:52:42.926
Общая идея методов возможных направлений
состоит в следующем: от изначально

00:52:43.207 --> 00:52:48.812
допустимой по условию задачи точки X1
осуществляется переход к новой допустимой

00:52:48.932 --> 00:52:52.695
точке, в которой значение целевой функции
лучше, чем в предыдущей.

00:52:53.215 --> 00:52:57.059
Процесс продолжается до тех пор, пока
остаётся возможность улучшить значение

00:52:57.219 --> 00:52:58.060
целевой функции.

00:52:58.642 --> 00:53:02.083
Либо задача не может быть решена с
заданной точностью.

00:53:02.283 --> 00:53:06.724
При этом на каждом шаге для перехода в
последующую точку требуется определить

00:53:06.844 --> 00:53:09.245
направление перехода и длины шага.

00:53:09.325 --> 00:53:16.087
Таким образом, следующий шаг определяется
по формуле X-k + 1

00:53:17.153 --> 00:53:21.791
Минус XK + A1K RK.

00:53:22.031 --> 00:53:24.390
Где вернее, альфа-К.

00:53:24.470 --> 00:53:29.267
Альфа-К — величина Кто шага, РК —
единственный вектор, определяющий

00:53:29.587 --> 00:53:31.426
направление перемещения.

00:53:32.785 --> 00:53:36.543
Данное равенство является общим для
рассматриваемой группы методов

00:53:36.663 --> 00:53:37.463
оптимизации.

00:53:37.830 --> 00:53:42.028
Интерпретация же подхода к её решению
призвана задавать правила определения

00:53:42.188 --> 00:53:44.907
параметров РК и Альфак.

00:53:45.667 --> 00:53:48.826
Векторный метод решения задачи линейного
программирования.

00:53:49.592 --> 00:53:53.832
Рассмотрим данный метод как метод,
относящийся к группе методов возможных

00:53:54.152 --> 00:53:58.992
направления, оцениваем его преимущества и
недостатки по сравнению с традиционным

00:53:59.192 --> 00:54:00.552
Simplix-методом.

00:54:00.712 --> 00:54:03.832
Проиллюстрируем интерпретацию данного
метода решением

00:54:05.325 --> 00:54:07.205
решённым ранее примером.

00:54:08.005 --> 00:54:10.485
Целевая функция стремится к минимуму.

00:54:10.805 --> 00:54:17.284
Задана система ограничений: 3x1 + 2 X2 +
10 X-3 — больше либо равна 80.

00:54:17.924 --> 00:54:24.443
Вторая система ограничений: X1 +6 X2 + X 3
+ 13—X4 больше либо равна сорока.

00:54:25.232 --> 00:54:30.512
В данном случае интерпретацию на плоскости
можно дать, если число ограничений в

00:54:30.592 --> 00:54:32.313
системе не превышает двух.

00:54:32.473 --> 00:54:36.193
Отложим в системе координат шкалы
ограничений.

00:54:36.793 --> 00:54:38.274
Показано на рисунке.

00:54:38.674 --> 00:54:41.554
Итак, ноль, 10, 80.

00:54:42.005 --> 00:54:45.083
Ноль один десять сорок.

00:54:46.162 --> 00:54:48.401
Строим векторы в данном случае

00:54:55.917 --> 00:54:59.115
ограничения позволяют задать допустимую
область решений.

00:55:00.793 --> 00:55:05.075
Естественно, так как требуется достигнуть
данного ограничения с минимальными

00:55:05.195 --> 00:55:10.436
потерями. Нас интересует оптимальное
решение, что обеспечивает кратчайший путь

00:55:10.556 --> 00:55:13.917
между точками 0 иль штрих.

00:55:14.077 --> 00:55:19.239
Следует привести вектор 0.0, достающий
кратчайший путь, к области допустимых

00:55:19.359 --> 00:55:19.759
решений.

00:55:20.504 --> 00:55:24.508
Каждое возможное решение, задаваемое
системой ограничений, также можно

00:55:24.708 --> 00:55:27.551
представить собственным вектором на
плоскости.

00:55:27.631 --> 00:55:33.877
В частности, если принять X1 равное
единице, X-3 равное 3, gк 1.

00:55:34.078 --> 00:55:38.242
Смотрим исходную задачу, ему будет
соответствовать вектор X1.

00:55:38.362 --> 00:55:38.923
Соответственно.

00:55:39.724 --> 00:55:41.725
Получаем все остальные векторы.

00:55:42.165 --> 00:55:47.767
Очевидно, что для заданных ограничений
лучшим был бы вектор или решение, которое

00:55:47.928 --> 00:55:54.210
позволяет продвигаться со скоростью две
или совпадающими по направлению с

00:55:54.290 --> 00:55:56.131
идеальным вектором 00х.

00:55:56.909 --> 00:56:01.984
Однако для заданной задачи необходимого
вектора нет.

00:56:02.184 --> 00:56:08.139
Следовательно, возникает задача выбора
оптимального решения выбора параметра RK в

00:56:08.218 --> 00:56:13.454
уравнении 5. Так как вектор в общем случае
характеризуется двумя параметрами

00:56:14.088 --> 00:56:15.689
Длиной и направлением.

00:56:15.930 --> 00:56:22.416
В данном случае величина угла между им и
идеальным вектором 00, что с определёнными

00:56:22.496 --> 00:56:27.501
оговорками можно свести к одному критерию
выбора лучшего вектора по длине его

00:56:27.701 --> 00:56:30.583
проекций на идеальный вектор 00.

00:56:31.159 --> 00:56:36.801
Итак, по величине длины проекции можно
выбрать лучший вектор в данном шаге.

00:56:37.081 --> 00:56:42.724
В данном случае в качестве альфа-катера
предполагаем один отложенный вектор.

00:56:43.404 --> 00:56:48.366
Отложение выбранного лучшего вектора на
данном шаге, что означает присвоение

00:56:48.606 --> 00:56:50.007
соответствующей переменной.

00:56:50.312 --> 00:56:55.599
Их сжитое значение 1 приближает нас к
допустимой области решений, следовательно,

00:56:55.679 --> 00:57:00.685
для перехода к следующему шагу оптимизации
следует перенести начало системы

00:57:00.805 --> 00:57:04.970
координат, направление и на величину
выбранного лучшего вектора.

00:57:05.290 --> 00:57:06.371
Соответственно, строится

00:57:06.770 --> 00:57:11.286
...и новый идеальный вектор, учитывающий
достижение заданных ограничений на

00:57:11.366 --> 00:57:12.605
предыдущих этапах.

00:57:13.004 --> 00:57:17.800
В новой системе опять откладываются
исходные векторы и вновь выбирается лучший

00:57:17.880 --> 00:57:22.356
вектор. Данная процедура выполняется до
тех пор, пока последний...

00:57:22.758 --> 00:57:29.397
Лучший из отложенных векторов не пересечёт
допустимую область

00:57:29.557 --> 00:57:34.676
решений. Совокупность отложенных векторов
на всех этапах определяет оптимальный план

00:57:34.956 --> 00:57:36.436
или оптимальное решение.

00:57:36.876 --> 00:57:41.075
Замечание. Видим, что в данном случае мы
получаем оптимальное решение.

00:57:41.595 --> 00:57:43.114
Целочисленные задачи.

00:57:43.353 --> 00:57:47.230
Посмотрим ещё раз на наш рисунок.

00:57:48.149 --> 00:57:51.026
То есть мы стремимся к идеальному
спектору.

00:57:51.425 --> 00:57:57.979
То есть откладываем мы, откладываем один
вектор, второй, третий и приближаемся к

00:57:58.019 --> 00:57:59.977
идеальному вектору 03.

00:58:06.402 --> 00:58:08.280
Подходы к точному решению задачи.

00:58:08.400 --> 00:58:11.956
Первый — метод последовательных
приближений.

00:58:12.356 --> 00:58:17.192
Идея метода состоит в том, что на первом
шаге задачи решаются целочисленно,

00:58:17.271 --> 00:58:21.747
откладываются полные вектора при
пересечении последним отложенным вектором

00:58:21.867 --> 00:58:23.865
допустимой области решений.

00:58:24.728 --> 00:58:28.292
Начинается процесс приближения к
оптимальному точному решению.

00:58:28.652 --> 00:58:32.936
Каждый этап этого приближения состоит в
следующем: изменяется исходная система

00:58:33.056 --> 00:58:36.940
координат: с первого квадрата на третий,
со второго на четвёртый.

00:58:38.222 --> 00:58:40.544
С первого на третий, со второго на
четвёртый.

00:58:42.795 --> 00:58:47.116
Из точки пересечения последнего
отложенного вектора допустимой области

00:58:47.276 --> 00:58:53.719
решения Uм идеальный вектор, относительно
которого

00:58:54.319 --> 00:58:56.199
теперь выбирается лучший вектор.

00:58:56.439 --> 00:59:00.841
Векторы вариантов изменяются направления
на противоположные, и мы начинаем

00:59:00.921 --> 00:59:02.482
рассматривать некоторые их части.

00:59:03.180 --> 00:59:06.780
Длина векторов умножаются на коэффициенты
меньше единицы.

00:59:06.980 --> 00:59:11.780
Процедура повторяется до тех пор, пока
последний отложенный вектор, часть вектора

00:59:11.940 --> 00:59:15.501
не достигается точки нод с двумя
звёздочками.

00:59:20.901 --> 00:59:21.981
Обратите внимание.

00:59:22.531 --> 00:59:28.532
Вектор 0 штрих, либо 0 со звёздочкой, 02
штриха, либо 0 с двумя звёздочками.

00:59:29.092 --> 00:59:34.732
Вот у нас система координат задан вектор и
прямая.

00:59:35.492 --> 00:59:37.172
Метод точного решения.

00:59:38.853 --> 00:59:40.533
Точное решение задачи данной

00:59:41.178 --> 00:59:46.703
Данный альтернативный подход предполагает
отложение на каждом шаге не целиком, а

00:59:46.783 --> 00:59:50.626
лишь часть векторов. Данная часть
выбирается из следующих соображений.

00:59:50.746 --> 00:59:56.191
Предположив, что после отложенного вектора
следующим лучшим становится другой вектор,

00:59:56.271 --> 01:00:00.595
всегда можно определить ту часть первого
вектора, которая задаёт лучшее направление

01:00:00.795 --> 01:00:02.877
продвижения в сторону исходного вектора.

01:00:03.440 --> 01:00:05.999
Именно эта часть, а не целиком вектор.

01:00:06.199 --> 01:00:09.636
Искомая часть вектора может быть
определена следующим образом.

01:00:10.076 --> 01:00:15.153
Если из конца искомой части лучшего
вектора отложить идеальный вектор, то

01:00:15.313 --> 01:00:19.990
отложенный из него первый и второй лучший
вектор будут иметь равный длину проекции

01:00:20.430 --> 01:00:22.069
на вновь отложенный идеальный вектор

01:00:24.315 --> 01:00:28.394
Данный подход уже трудно отнести к
методам, ориентированным на ЭВМ, так как

01:00:28.554 --> 01:00:32.553
параметр альфа-каты соответственно
посредством решений уравнений.

01:00:33.393 --> 01:00:39.392
Вот то, что мы с вами проговаривали
проекции первого вектора, второго, и мы

01:00:39.552 --> 01:00:41.032
стремимся к идеальному вектору.

01:00:44.193 --> 01:00:47.515
Формализация решения задачи векторным
методом.

01:00:48.435 --> 01:00:52.676
Как отмечали, критерии выбора решений на
каждом этапе определяется двумя

01:00:52.757 --> 01:00:58.599
параметрами: длинный вектора решений и
величина угла вектора решения с идеальным

01:00:58.679 --> 01:00:59.999
вектором Н, равное нулю.

01:01:00.501 --> 01:01:07.337
Соответственно, свести задачу критерия
можно, рассматривая

01:01:07.537 --> 01:01:13.893
длину проекции вектора решения на
идеальный модуль N

01:01:14.373 --> 01:01:17.212
равен XN на косинус альфа.

01:01:19.882 --> 01:01:26.681
Если обозначить через X1 значение от
единицы до N, параметры

01:01:26.801 --> 01:01:33.079
энного вектора, то длина вектора равна X
равна сумме X квадрат N

01:01:33.959 --> 01:01:35.318
в степени одной второй.

01:01:38.722 --> 01:01:41.563
Арт-нормирую систему следующим образом.

01:01:44.244 --> 01:01:50.887
X1 вектор равен X1,

01:01:51.608 --> 01:01:54.809
где X1 и от единицы до M.

01:01:58.095 --> 01:02:01.214
Получим проекцию в ортонормированном
базисе.

01:02:01.894 --> 01:02:03.494
Вот она у нас проекция.

01:02:04.374 --> 01:02:09.412
Замечание. Длина вектора и угол между
векторами определяется по следующим

01:02:09.492 --> 01:02:16.050
формулам: X N равно сумме, где M
изменяется от M малого до M большого, J

01:02:16.570 --> 01:02:17.810
M в степени одной второй.

01:02:18.457 --> 01:02:25.129
Альфа равна R косинус в сумме M от единицы
до M большого M

01:02:25.729 --> 01:02:32.641
умножить на J умножить на сумму Ж в
квадрате и на сумму Ж в квадрате m

01:02:32.721 --> 01:02:33.959
в степени одной второй.

01:02:35.417 --> 01:02:39.373
Данное выражение после соответствующих
постановок, предположение, что

01:02:39.573 --> 01:02:45.048
нормированное значение идеального вектора
равно единицель M равно единице,

01:02:45.128 --> 01:02:51.082
следовательно, э-э ноль равно единице на
корень из M, умноженная на сумму

01:02:51.282 --> 01:02:52.201
ЖН.

01:02:54.042 --> 01:03:00.370
Так как значение M фиксировано для всех
вариантов решения, это значение можно

01:03:00.571 --> 01:03:04.576
опустить таким образом: в качестве
критерия выбора оптимального вектора на

01:03:04.696 --> 01:03:09.222
каждом шаге можно рассматривать параметр,
определяющий следующие выражение.

01:03:10.382 --> 01:03:17.093
Система 6 X нулевое равно

01:03:17.293 --> 01:03:24.165
сумме X NIT при этом XIT равно отношению

01:03:27.336 --> 01:03:30.253
На X0.

01:03:30.653 --> 01:03:35.967
Видим, что эти формулы просты, что
позволяют эффективно использовать данный

01:03:36.127 --> 01:03:40.443
метод решения задачи линейного
программирования с использованием

01:03:40.483 --> 01:03:41.881
вычислительных средств.

01:03:42.041 --> 01:03:45.357
Таким образом, методика выбора
оптимального решения сводится к

01:03:45.437 --> 01:03:46.037
следующему.

01:03:46.568 --> 01:03:52.045
На каждом шаге, используя критерий шей
шесть, выбираем следующее значение из

01:03:53.284 --> 01:03:56.442
X нулевое, которое стремится к максимуму.

01:03:56.802 --> 01:04:01.559
С учётом выбранного вектора, что
соответствует его откладыванию в системе

01:04:01.639 --> 01:04:02.198
координат.

01:04:02.694 --> 01:04:07.777
Изменяем систему ограничений, вычитаем из
ограничений соответствующие параметры

01:04:07.977 --> 01:04:11.419
векторов. Третье.

01:04:11.860 --> 01:04:16.582
Проверяем все полученные ограничения на
условии меньше либо равно нулю, если для

01:04:16.742 --> 01:04:19.584
всех ограничений оно выполняется, задача
решается.

01:04:20.083 --> 01:04:26.960
Если условие не выполняется, возвращаемся
к шагу один с перенормированием значений

01:04:27.160 --> 01:04:29.199
параметров. Пример.

01:04:30.399 --> 01:04:35.916
Вернёмся к задаче раскроя материалов,
рассмотренных ранее, где целевая функция у

01:04:35.996 --> 01:04:37.315
нас стремится к минимуму.

01:04:38.165 --> 01:04:40.047
Равно восьмидесяти и сорока.

01:04:40.167 --> 01:04:46.734
Способ у нас четыре способа: раскрой
первого типа 3210, раскрой второго типа

01:04:46.934 --> 01:04:48.095
16913

01:04:53.838 --> 01:05:00.642
Ограничение: 3x1 + 2x2 + X3 больше либо
равно восьмидесяти; X1 +

01:05:00.762 --> 01:05:05.445
6 X2 + 9 X3 + 13 X4 — больше либо равно
40.

01:05:05.605 --> 01:05:08.927
Для регистрации выполняем несколько шагов
решения.

01:05:09.007 --> 01:05:09.648
Шаг первый.

01:05:10.437 --> 01:05:13.598
Считаем значение критерия для различных
вариантов.

01:05:14.359 --> 01:05:21.162
Ф равно единица

01:05:21.802 --> 01:05:26.165
умножить на единицу + 13 умножить на одну
вторую приблизительно

01:05:28.814 --> 01:05:30.575
1,4.

01:05:30.976 --> 01:05:36.301
F отблизительно 0,9.

01:05:38.143 --> 01:05:44.469
F от An 0,7 и четвёртая — фи от An у нас
приблизительно

01:05:44.629 --> 01:05:45.990
0,5.

01:05:51.348 --> 01:05:57.950
Так. И на рисунке у нас по осе апцикс 80
единиц отложено, по осе оординат — 40

01:05:58.190 --> 01:06:04.592
единиц. Далее коэффициенты 1, 2, 3

01:06:06.752 --> 01:06:09.833
отложены по осе апцикс 1,6,9, 13

01:06:11.220 --> 01:06:16.065
По оси ординат. То есть раскрой первого
типа у нас по оси абциз, раскрой второго

01:06:16.145 --> 01:06:17.866
типа по оси ординат.

01:06:18.307 --> 01:06:24.712
Ну и мы строим, соответственно, векторы,
четыре вектора и целевую

01:06:24.792 --> 01:06:31.599
функцию. Сравниваем, выбираем

01:06:31.719 --> 01:06:32.599
лучший вариант этого

01:06:34.710 --> 01:06:37.671
Варианта. Приравниваем X1 к единице.

01:06:38.872 --> 01:06:40.672
Формулируем новые ограничения.

01:06:40.792 --> 01:06:44.194
U1 равно 77, 2 39.

01:06:44.634 --> 01:06:48.515
Задача не решена, следовательно, требуется
следующий шаг — решения.

01:06:48.675 --> 01:06:50.356
Не все ограничения нулевые.

01:06:50.476 --> 01:06:52.877
Следующий шаг отличается от предыдущего
тем.

01:06:53.465 --> 01:06:56.103
Что в радиативном критерии изменяется.

01:06:59.142 --> 01:07:05.859
Продолжаем перерасчёт, находим первое F1,
второе фи-2, третье fi fi 2 и

01:07:06.019 --> 01:07:08.018
четвёртое фи-F.

01:07:08.298 --> 01:07:09.737
То есть это уже мы рассмотрели

01:07:10.278 --> 01:07:12.237
Двадцать второй шаг и так далее.

01:07:12.677 --> 01:07:17.473
Выбираем лучшее значение по данному
критерию, фиксируем отложенный X,

01:07:17.553 --> 01:07:22.389
пересчитываем ограничения, проверяем,
решена ли задача полностью или требуется

01:07:22.589 --> 01:07:24.827
следующий шаг решения и так далее.

01:07:29.115 --> 01:07:31.155
Нормирование параметров в общем случае.

01:07:31.235 --> 01:07:38.072
В общем случае нормирование параметров
должно учитывать первое — величину

01:07:38.232 --> 01:07:43.550
вектора относительно векторов других
сравниваемых вариантов или насколько велик

01:07:43.590 --> 01:07:44.230
шаг в сторону

01:07:45.001 --> 01:07:49.997
Ограничение. Будет ли при откладывании
данного вектора?

01:07:50.117 --> 01:07:55.832
Второе — отношение ограничений между собой
или в какой мере следует продвигаться при

01:07:55.952 --> 01:07:58.949
откладывании векторов конкретному
ограничению.

01:07:59.269 --> 01:08:03.626
Третье — учёт отношения влияния выбранного
решения по отношению к остальным на

01:08:03.705 --> 01:08:04.585
целевую функцию.

01:08:05.987 --> 01:08:07.669
Нормирование значения.

01:08:08.470 --> 01:08:12.875
Нормированное значение параметры задаётся
объективным способом нормирования по

01:08:12.955 --> 01:08:18.001
следующем условии: вектор QN равно
отношению Н

01:08:19.683 --> 01:08:21.606
относится к 0, где 0

01:08:22.993 --> 01:08:29.517
Это верхняя точечная граница, то есть

01:08:29.677 --> 01:08:36.522
максимум. Учёт отношения ограничений
осуществляется внесением весового

01:08:36.682 --> 01:08:40.484
элемента, определяемого по формуле Betta M
равно K.

01:08:41.482 --> 01:08:48.126
Относится Um степень максимальная, где Q
максимальное также верхнее

01:08:48.326 --> 01:08:53.490
точечное значение. Таким образом, выбор
лучшего решения на каждом этапе

01:08:53.570 --> 01:08:54.931
выполняется по формуле.

01:08:55.051 --> 01:08:59.494
F от равно сумме Q относится к K

01:09:00.951 --> 01:09:07.072
Ноль M умноженное на ку большое M и ку
максимальное m.

01:09:07.352 --> 01:09:11.752
Для того чтобы учесть, насколько выбранное
решение влияет на целевую функцию при

01:09:11.872 --> 01:09:16.913
условии, что она минимизируется, критерии
для варианта N следует ввести коэффициент

01:09:17.073 --> 01:09:17.913
гамма Н.

01:09:18.370 --> 01:09:25.329
Тогда получим следующее значение An равно
гамма умножить на

01:09:25.449 --> 01:09:31.927
сумму ку малое n на K малое ноль умножить
на K большое M относится к K

01:09:32.047 --> 01:09:37.166
максимальному M, где гамма Н равна
минимальное N на K

01:09:38.300 --> 01:09:43.016
Ц минимальная — это есть Infinitum,
Infinitu.

01:09:44.015 --> 01:09:50.130
Эта формула является основной расчётной
формулой выборе оптимального плана на

01:09:50.250 --> 01:09:53.327
каждом шаге при постановке задачи в общем
виде.

01:09:55.044 --> 01:10:01.758
Infinity — это значит минимизируется
Достоинства вектора метода

01:10:02.118 --> 01:10:07.593
решения основного основанного на векторной
интерпретации задачи линейного

01:10:07.713 --> 01:10:11.790
программирования. Кроме очевидной
наглядности, данная интерпретация

01:10:12.029 --> 01:10:14.227
позволяет, в отличие от симплекс-метода

01:10:14.862 --> 01:10:19.181
Векторный метод позволяет минимизировать
число вычислений, так как критерий

01:10:19.221 --> 01:10:23.540
оптимальности позволяет на каждом шаге
наилучшим образом с точки зрения

01:10:23.740 --> 01:10:28.419
количества вычислений, продвигаться в
сторону области допустимых решений.

01:10:29.059 --> 01:10:32.578
Минимальная вычислительная сложность на
каждом этапе выбора плана.

01:10:33.171 --> 01:10:35.731
Простейшие арифметические и логические
операции.

01:10:35.891 --> 01:10:40.531
Всё это обусловливает эффективность
применения метода для расчёта, оптимизации

01:10:40.731 --> 01:10:43.651
задач на вычислительных машинах.

01:10:45.571 --> 01:10:48.171
Приоритетная задача линейного
программирования.

01:10:48.966 --> 01:10:52.890
Приоритетная задача состоит в том, что в
рамках заданных ограничений дополнительно

01:10:53.651 --> 01:10:56.614
оговаривается порядок выполнения данных
ограничений.

01:10:56.935 --> 01:11:01.860
Возвращаемся к нашей, к нашему примеру
раскрою материалов, где заданы ограничения

01:11:02.060 --> 01:11:05.704
не менее 80 деталей первого типа и не
менее 40.

01:11:06.364 --> 01:11:12.926
Может быть дополнительно введено,
например, следующее ограничение: в

01:11:13.086 --> 01:11:17.887
первую очередь необходимо провести не
менее 30 деталей первого типа и не менее

01:11:17.967 --> 01:11:21.328
двадцати второго. Во вторую очередь, э-э-э

01:11:21.906 --> 01:11:24.869
Увеличиваем значение либо уменьшаем и так
далее.

01:11:25.109 --> 01:11:29.074
То есть вводится некоторый приоритет на
очерёдность решаемых задач.

01:11:29.194 --> 01:11:32.197
При такой постановке задачи уже
действительно можно говорить об

01:11:32.317 --> 01:11:36.001
оптимальности планирования, так как
учитывается, соответственно,

01:11:36.121 --> 01:11:38.003
последовательность выполнения работ.

01:11:38.876 --> 01:11:42.434
При использовании классического метода
решения задачного линейного

01:11:42.594 --> 01:11:47.472
программирования Simplex методов не
позволяющих учитывать динамику плана,

01:11:47.712 --> 01:11:51.071
данная задача разбивается на
соответствующую совокупность

01:11:51.311 --> 01:11:53.950
невзаимосвязанных задач линейного
программирования.

01:11:54.536 --> 01:11:57.219
Число задач определяется числом
приоритетов.

01:11:57.540 --> 01:12:01.945
Векторный метод решание задач линейного
программирования позволяет строить

01:12:02.066 --> 01:12:05.550
оптимальные планы с учётом динамики
выполнения работ.

01:12:06.071 --> 01:12:09.795
Рассмотрим, как решается приоритетная
задача линейного программирования.

01:12:10.392 --> 01:12:14.787
...векторным методом и в первую очередь,
как она интерпретируется.

01:12:15.027 --> 01:12:18.782
В общем случае приоритетная задача
линейного программирования в своей

01:12:18.862 --> 01:12:24.056
формальной постановке выглядит следующим
образом: пусть задано первое приоритетов

01:12:24.256 --> 01:12:25.894
на заданную область ограничений.

01:12:26.554 --> 01:12:30.277
Соответственно, имеем следующую систему
ограничений.

01:12:32.518 --> 01:12:34.760
Так, задано в виде формул.

01:12:34.920 --> 01:12:40.364
При этом задаётся в первую очередь,
требуется выполнить что OM ограничений.

01:12:40.444 --> 01:12:41.765
Постановка задачи имеет вид

01:12:42.619 --> 01:12:49.453
X Mжитые такие, что XM, где M изменяется
от единицы до N и от

01:12:49.573 --> 01:12:56.127
единицы добращается в минимум целевая
функция при условии, что

01:12:57.046 --> 01:13:00.123
система ограничений будет больше либо
равна K.

01:13:02.352 --> 01:13:07.387
Один и Т — первое ограничение, и второе —
ку, больше либо равна Q

01:13:07.947 --> 01:13:13.301
и-и сумма будет равна m.

01:13:15.539 --> 01:13:18.376
Векторная интерпретация задачи состоит в
следующем.

01:13:18.536 --> 01:13:19.495
Смотрите на рисунок.

01:13:20.008 --> 01:13:23.488
На плоскости проявляется система
допустимых решений.

01:13:30.008 --> 01:13:35.408
Допустимая область с меньшим порядковым
номером более приоритетна у 1.

01:13:36.292 --> 01:13:39.454
Данные ограничения должны выполняться в
первую очередь.

01:13:39.654 --> 01:13:44.416
В каждой допустимой области должно быть
отложен идеальный вектор из начала

01:13:44.496 --> 01:13:48.818
координат в первую очередь, из вершины
предыдущей области, в начало координат

01:13:49.098 --> 01:13:53.900
второй области. Итак, из вершины
предыдущей области опять же откладывается

01:13:54.060 --> 01:13:55.821
идеальный вектор во вторую область.

01:13:58.010 --> 01:14:03.773
Данная задача может решаться так, как же,
как и в случае без приоритетной постановки

01:14:03.973 --> 01:14:06.774
путём выбора лучшего вектора на каждом
этапе.

01:14:07.014 --> 01:14:11.937
Однако существует два правила преодоления
области допустимых решений.

01:14:13.137 --> 01:14:17.059
Таким образом, данный подход может
позволить использовать возможности

01:14:17.259 --> 01:14:18.900
векторной интерпретации.

01:14:19.684 --> 01:14:24.688
Возможность поиска не только лучших
решений в плане, но и их очерёдность для

01:14:24.849 --> 01:14:29.933
решения приоритетных задач, отличающихся
своей постановкой, заданием очередности

01:14:30.173 --> 01:14:31.855
выполнения ограничений.

01:14:34.017 --> 01:14:36.779
Постановка и метод решения задачи синтеза

01:14:37.544 --> 01:14:40.383
Расписание. Векторная интерпретация
задачи.

01:14:40.703 --> 01:14:45.261
Большинство детерминированных задач в
прикладной области вычислительных систем

01:14:45.461 --> 01:14:47.220
сетей является линейными.

01:14:47.340 --> 01:14:52.618
Поэтому векторная интерпретация задач
здесь имеет достаточно большую общность.

01:14:53.258 --> 01:14:54.017
В частности, всегда

01:14:55.246 --> 01:15:01.920
Когда может быть определено некое желаемое
или оптимальное решение?

01:15:02.200 --> 01:15:06.596
Могут быть определены исходные способы
решения, при необходимости задана область

01:15:06.716 --> 01:15:10.752
оптимальных решений. Применим данный
подход, рассмотрим его применение к

01:15:10.832 --> 01:15:13.790
задачам синтеза расписаний реального
времени.

01:15:14.336 --> 01:15:18.977
Рассматриваемая детерминированная задача
теории расписания состоит в определении

01:15:19.177 --> 01:15:23.857
очередности передачи прав на занятие
ресурса, минимизирующей его

01:15:25.137 --> 01:15:29.298
производительность при выполнении
ограничений реального времени.

01:15:29.884 --> 01:15:34.045
Более подробно постановку задачи синтеза,
расписания реального времени мы рассмотрим

01:15:34.365 --> 01:15:35.685
на практических занятиях.

01:15:35.805 --> 01:15:41.606
Здесь лишь отметим, что ограничение
реального времени на время решения

01:15:41.846 --> 01:15:46.887
различных задач задача должна быть
гарантированно решена на этот промежуток

01:15:46.927 --> 01:15:47.287
времени.

01:15:47.917 --> 01:15:51.554
В одной системе реального времени могут
быть сильно различаться ввиду их

01:15:52.034 --> 01:15:57.270
разнородностей. Например, при построении
системы уравнений с соответствующими

01:15:57.670 --> 01:16:03.425
различными заданными периодами можно
потребовать измерять скорость,

01:16:03.465 --> 01:16:06.383
температуру, плотность чего-либо и так
далее, и тому подобное.

01:16:07.380 --> 01:16:12.898
В этом случае использование
бесприоритетного режима обслуживания в

01:16:12.978 --> 01:16:18.056
реальном времени по очереди может
оказаться неоптимальным, требующим

01:16:18.336 --> 01:16:21.855
большего увеличения производительности
общного ресурса.

01:16:22.215 --> 01:16:23.294
Требуется построить

01:16:25.875 --> 01:16:30.836
Оптимальную для конкретного приложения
приоритетную дисциплину обслуживания

01:16:31.036 --> 01:16:34.956
реального времени. Рассмотрим
интерпретацию постановки задачи на

01:16:35.036 --> 01:16:41.196
рисунке. Так, реальное время — один,
реальное время два.

01:16:44.273 --> 01:16:50.835
По оси координат откладываются временные
характеристики задачи

01:16:51.435 --> 01:16:57.076
эмного типа, в частности ТМ и ограничение
реального времени

01:17:00.919 --> 01:17:04.162
...которая ограничивает некоторые
допустимые области решения.

01:17:04.242 --> 01:17:06.324
В данном это случае по ассиапциз.

01:17:06.564 --> 01:17:10.968
Однако, в отличие от предыдущего случая
задачи линейного программирования,

01:17:11.088 --> 01:17:15.772
допустимая область решения здесь уже иная,
задаются иные условия.

01:17:16.213 --> 01:17:19.536
Особенностью является и то, что исходная
задача M.

01:17:21.369 --> 01:17:27.406
способов решения задачи при каждом весь
квант времени с учётом затрат времени на

01:17:27.486 --> 01:17:31.963
выбор заявки из очереди Представляется
заявка одной из M очередей.

01:17:32.123 --> 01:17:36.920
Соответственно, имеем M векторов равных
длины

01:17:38.208 --> 01:17:43.924
Совпадающие по направлению с осями системы
координат векторы ОО1 и

01:17:44.044 --> 01:17:49.880
ОО-2-1.

01:17:49.959 --> 01:17:51.638
Вот он вектор ещё раз.

01:17:51.918 --> 01:17:52.877
О-О-2.

01:17:57.939 --> 01:18:01.776
В этом случае уже имеет смысл говорить не
о максимальной длине проекции, а о

01:18:01.896 --> 01:18:04.254
ведеальном векторе O-штрих.

01:18:04.494 --> 01:18:07.931
То есть мы должны найти ведеальный вектор
O-штрих.

01:18:09.370 --> 01:18:14.605
А минимальный, что реализует при
откладывании векторов по осям координат.

01:18:15.158 --> 01:18:20.753
Так как целесообразно обслуживать
максимальное число данных заявок за

01:18:20.913 --> 01:18:26.628
ограниченное время и о достижимости
ограничения Т большое M по M осям.

01:18:26.868 --> 01:18:31.624
Естественно, что при синтезе расписания в
первую очередь имеет смысл откладывать

01:18:31.744 --> 01:18:32.384
вектор в том

01:18:34.427 --> 01:18:41.348
Направлении, которые может быть получено
из условия в данном случае минимизации.

01:18:41.428 --> 01:18:46.468
То есть выбираем самое самое жёсткое
ограничение, которое должно быть выбрано

01:18:46.828 --> 01:18:48.028
за минимальное время.

01:18:48.566 --> 01:18:53.968
На рисунке вы его перечертите для того,
чтоб было более понятно была задача — это

01:18:54.168 --> 01:18:57.008
ограничение ТОльшое, равное одному.

01:18:57.168 --> 01:19:02.970
Предоставим ресурс выбранной заявки на
фиксированное время на занятие, задаваемое

01:19:03.090 --> 01:19:07.691
продолжительностью времени кванта, что на
рисунке соответствует отложению вектора

01:19:07.811 --> 01:19:08.572
ООдин.

01:19:09.405 --> 01:19:12.284
Далее требуется сформулировать новую
систему координат.

01:19:12.484 --> 01:19:16.762
Особенностью её получения будет перенос
системы координат в направление и на

01:19:16.842 --> 01:19:23.640
величину векторов, где равно двум M, что

01:19:23.839 --> 01:19:26.678
на рисунке соответствует переносу вектора
ОО2.

01:19:27.630 --> 01:19:31.029
Поясним физический смысл получения новой
системы координат.

01:19:31.268 --> 01:19:36.387
После обслуживания заявки M равной один,
её место занимает следующая заявка из этой

01:19:36.427 --> 01:19:41.025
очереди, для которой ограничение на время
обслуживания совпадает с исходным.

01:19:41.305 --> 01:19:46.423
Ни одна из заявок других очередей за это
время не обслуживается или после окончания

01:19:46.543 --> 01:19:47.543
кванта ограничения

01:19:48.257 --> 01:19:52.660
На время обслуживания этих заявок
уменьшается ровно на продолжительность

01:19:52.820 --> 01:19:57.183
кванта. Многоэтапная процедура оптимизации
выполняется до тех пор, пока заявки всех

01:19:57.223 --> 01:19:58.904
очередей не будут обслужены.

01:19:59.144 --> 01:20:02.666
За ограниченное время и результатом
решения задачи будут оптимальное

01:20:02.786 --> 01:20:05.187
расписание обслуживания при задании.

01:20:05.525 --> 01:20:09.887
...заданной длине кванта, которые,
собственно, и задают производительность

01:20:10.167 --> 01:20:15.770
ресурса. Если заявки всех очередей
невозможно обслужить с учётом заданных

01:20:16.210 --> 01:20:21.413
временных ограничений, необходимо повышать
производительность ресурса, что приведёт к

01:20:21.453 --> 01:20:22.893
уменьшению длины кванта.

01:20:23.290 --> 01:20:26.371
задающего продолжительность обслуживания
одной заявки.

01:20:26.531 --> 01:20:30.573
Затем процедура синтеза расписания должна
быть выполнена вновь.

01:20:31.934 --> 01:20:32.814
Если заявки

01:20:33.533 --> 01:20:39.254
Всех очередей можно обслуживать за время
меньше задаваемого ограничения, можно

01:20:39.574 --> 01:20:43.894
увеличить продолжительность кванта с
повторным выполнением процедуры для

01:20:44.014 --> 01:20:47.095
оптимизации производительности ресурса.

01:20:47.615 --> 01:20:48.415
Утверждение.

01:20:49.423 --> 01:20:53.066
Продолжительность временного кванта
обслуживания заявки в системе

01:20:55.909 --> 01:20:58.511
координат задаётся условием.

01:20:59.392 --> 01:21:02.915
Перепишите это условие.

01:21:06.919 --> 01:21:10.122
Доказательство, чтобы иметь возможность
обслуживать заявок.

01:21:10.738 --> 01:21:17.621
Совпадение ТМ в худший для системы случай
бесприоритетной дисциплины обслуживания.

01:21:17.701 --> 01:21:23.224
Необходимо и достаточно, чтобы за время TM
каждая заявка единожды получала доступ к

01:21:23.304 --> 01:21:28.427
ресурсу, что возможно при условии выбора
положительного кванта, равного TM

01:21:28.747 --> 01:21:30.027
разделить на M большое.

01:21:30.107 --> 01:21:30.628
Таким образом

01:21:31.279 --> 01:21:36.752
Использование векторного метода синтеза
расписания состоит в следующем: выбирая

01:21:37.271 --> 01:21:42.545
очередность представленного кванта,
синтезируем дисциплину обслуживания,

01:21:42.704 --> 01:21:46.859
выбирая же величину кванта, определяем
оптимальную производительность ресурса.

01:21:50.629 --> 01:21:54.832
Методы векторной оптимизации имеют массу
практических приложений в нашей области

01:21:55.072 --> 01:21:58.635
знаний. Однако существуют и ограничения на
их использование.

01:21:58.876 --> 01:22:02.759
Они могут использоваться лишь в том
случае, когда векторы качества вариантов

01:22:02.959 --> 01:22:05.922
решений совпадают для всех этих этапов
решения.

01:22:06.352 --> 01:22:11.636
Рассмотрим одно из исключений задачи
выбора оптимального маршрута.

01:22:11.956 --> 01:22:14.799
Решаем методом динамического
программирования.

01:22:15.039 --> 01:22:18.322
Основа метода динамического
программирования составляет уменьшение

01:22:18.482 --> 01:22:21.244
вычислительной сложности решения
оптимизации задачи.

01:22:22.174 --> 01:22:24.253
Перебора возможных маршрутов.

01:22:24.573 --> 01:22:26.693
Рассмотрим пример постановки.

01:22:28.292 --> 01:22:29.772
Видим маршрут.

01:22:36.570 --> 01:22:38.889
Перепишите либо зафиксируйте.

01:22:39.353 --> 01:22:46.158
При помощи телефона данную задачу принятие
очередного очередного решения

01:22:46.358 --> 01:22:50.761
или выбор маршрута равноценно выбору
направления выхода из одного угла

01:22:52.562 --> 01:22:55.804
коммутации, куда попало сообщение.

01:23:02.657 --> 01:23:04.898
Идея метода динамического
программирования.

01:23:04.978 --> 01:23:09.699
Возможный подход к решению задачи состоит
в полном переборе решений всех маршрутов

01:23:09.899 --> 01:23:12.099
из точки А в точку Б.

01:23:12.939 --> 01:23:14.620
Из точки А в точку Б.

01:23:16.218 --> 01:23:20.496
То есть могут быть рассчитаны длины путей
и выбран минимальный из них.

01:23:20.656 --> 01:23:24.654
Метод же динамического программирования
предполагает построение оптимального

01:23:25.093 --> 01:23:26.613
решения шаг за шагом.

01:23:26.773 --> 01:23:29.891
На каждом этапе оптимизируются отдельные
шаги.

01:23:30.051 --> 01:23:32.689
В основе решений лежат общие идеи данного

01:23:33.049 --> 01:23:38.766
...класса методов, состоящих в том, что
всегда алгоритмически проще многократно

01:23:38.846 --> 01:23:41.564
решать простую задачу, чем однократно
сложную.

01:23:41.844 --> 01:23:45.162
Проблема задач динамического
программирования состоит в том, что

01:23:45.202 --> 01:23:49.760
оптимизация маршрутов вне зависимости от
выбора оптимальных решений...

01:23:50.105 --> 01:23:55.221
На последующих или предыдущих шагах
невозможно, так как выигрыш, полученный на

01:23:55.301 --> 01:24:00.376
отдельном шаге, может не дать совокупность
выигрышей с учётом всех выбранных шагов

01:24:00.656 --> 01:24:03.813
маршрута. То есть оптимальный маршрут
может быть не найден.

01:24:04.093 --> 01:24:08.210
Следовательно, планируя многошаговую
операцию на отдельном шаге в качестве

01:24:08.529 --> 01:24:09.848
оптимального, надо выбрать

01:24:12.684 --> 01:24:17.726
Решение с учётом всех его последствий, как
на предыдущих, так и на последующих шагах.

01:24:18.086 --> 01:24:23.648
Метод динамического программирования
состоит в следующем: планируя вектор энный

01:24:23.808 --> 01:24:29.730
шаг, делает различные предположения о том,
чем закончится предыдущий M-минус первый.

01:24:30.165 --> 01:24:33.882
И для каждого из этих предположений
находится так называемое условно

01:24:34.002 --> 01:24:36.400
оптимальное решение на энном шаге.

01:24:36.759 --> 01:24:39.757
Условно оптимальное, так как данное
оптимальное решение находится

01:24:40.476 --> 01:24:45.272
предположении, что при условии, что M -1
шаг закончился так-то.

01:24:45.994 --> 01:24:49.758
Аналогичным образом могут быть
последовательно выбраны условия,

01:24:49.798 --> 01:24:51.720
оптимальные шаги на всех этапах.

01:24:51.840 --> 01:24:55.084
В процессе оптимизации методом
динамического программирования

01:24:55.244 --> 01:24:58.527
многошаговый процесс осуществляется
дважды.

01:24:58.768 --> 01:25:00.810
Первый — от конца к началу с целью

01:25:01.497 --> 01:25:04.981
Выявляемый условий оптимальных решений.

01:25:05.101 --> 01:25:09.466
Второе — от начала к концу с целью
определения оптимального маршрута.

01:25:09.947 --> 01:25:14.872
Особиная интерпретация или идея метода
решения весьма проста.

01:25:15.112 --> 01:25:18.716
Если на промежуточных шагах существует
несколько вариантов прохода

01:25:19.446 --> 01:25:22.405
Прохождение одного и того же пути между
одним и теми же

01:25:27.045 --> 01:25:32.644
маршрутами можно сравнить эти маршруты и
оставить для последующего анализа только

01:25:32.964 --> 01:25:35.323
один из этих условно оптимальный.

01:25:36.028 --> 01:25:37.229
Вернёмся к примеру.

01:25:37.469 --> 01:25:44.035
Опять же проиллюстрируем нашу идею следуя
из пункта

01:25:44.196 --> 01:25:49.160
А, из точки B в обратном направлении в
приложении, что мы указали в узле с

01:25:49.240 --> 01:25:50.201
номером 21

01:25:57.623 --> 01:26:04.615
Видим, что из УК21 существуют два маршрута
в точку Б выделены красным

01:26:04.775 --> 01:26:10.288
цветом. То есть мы можем сравнить эти два
маршрута, между собой выбраны из них

01:26:10.368 --> 01:26:14.004
условно-оптимальное решение, условно
оптимальное, так как вы производство

01:26:15.146 --> 01:26:19.701
Предположение, что сообщение попало в
УК21.

01:26:19.781 --> 01:26:26.613
Критерий одного варианта определяется как
30 + 2 36 66; другого: 30 + 30 равно

01:26:26.733 --> 01:26:27.332
60.

01:26:39.906 --> 01:26:46.220
Другими словами, это мы определяем, что
при условии попадания сообщения в УК21

01:26:49.577 --> 01:26:53.894
оно должно следовать по выбранному нами
оптимальному маршруту.

01:26:55.852 --> 01:26:58.490
Пойдём аналогично из точки Б по всем
направлениям

01:26:59.419 --> 01:27:04.608
Получаем определённый вариант оптимизации
задачи, состоящей из условно оптимальных

01:27:04.728 --> 01:27:05.965
решений. Смотрите рисунки.

01:27:23.718 --> 01:27:26.076
Теперь остаётся пройти из точки A в точку
Б.

01:27:26.196 --> 01:27:30.792
По условиям условно оптимальным маршрутам
рассчитать для них значение критерия

01:27:30.992 --> 01:27:33.470
оптимальности выбора, выбрать оптимальный.

01:27:33.790 --> 01:27:37.986
Оптимальным будет маршрут, выденный
красным цветом.

01:27:38.146 --> 01:27:42.023
Для этого определения не потребовалось
осуществлять полный перебор возможных

01:27:42.103 --> 01:27:42.662
маршрутов.

01:27:43.080 --> 01:27:47.642
С расчётом для них критерия оптимальности,
с последующим сравнением всех возможных

01:27:47.762 --> 01:27:48.763
вариантов.

01:27:55.927 --> 01:27:58.248
На этом первая лекция подошла к концу.

01:27:59.041 --> 01:28:00.053
Спасибо за внимание.

