WEBVTT

00:00:08.160 --> 00:00:10.678
Учебная дисциплина «Финансовая
математика».

00:00:10.798 --> 00:00:15.073
Тема практического занятия: «Методы
оптимизации в финансовом анализе».

00:00:15.673 --> 00:00:21.467
Преподаватель, кандидат педагогических
наук, доцент Романова Татьяна Николаевна.

00:00:22.826 --> 00:00:28.020
План занятия: методы оптимизации, виды
задач линейного программирования.

00:00:28.529 --> 00:00:32.932
Целочисленные задачи, применение AVM для
решения задач.

00:00:33.132 --> 00:00:37.096
Метод оптимизации как дисциплина
представляет собой раздел теории

00:00:37.216 --> 00:00:42.740
исследований, операций, задачей которой
является поиск в рамках принятой модели

00:00:42.900 --> 00:00:47.264
решений, отвечающих экспериментальным
значениям, критериям.

00:00:56.288 --> 00:01:01.921
Понятие лучше что-либо означает, когда
определении определён показатель или

00:01:02.040 --> 00:01:04.597
критерий качества выбираемых решений.

00:01:04.997 --> 00:01:08.872
Любую операцию можно охарактеризовать
следующими составляющими.

00:01:11.029 --> 00:01:11.828
Стратегия.

00:01:12.623 --> 00:01:17.900
Вариант решения называется допустимый или
возможный способ достижения цели.

00:01:19.460 --> 00:01:25.417
Действующими факторами операции называются
объективные условия, определяющие её

00:01:25.657 --> 00:01:28.095
особенности и влияющие на её исход.

00:01:33.480 --> 00:01:38.682
Критерием эффективности операции или
стратегии называется показатель

00:01:39.043 --> 00:01:44.525
достигнутого соответствия между полученным
результатом и целью операции.

00:01:45.525 --> 00:01:49.847
Состоянием операции в некоторый момент
времени называют совокупность её

00:01:50.087 --> 00:01:50.927
характеристик.

00:01:51.594 --> 00:01:58.400
проявляющихся в данный момент Под
параметром стратегии понимается локальное

00:01:58.560 --> 00:02:04.926
качество операции, обусловливаемое его
действующими факторами и учитываемое

00:02:05.246 --> 00:02:07.448
критерии эффективности стратегии.

00:02:08.878 --> 00:02:13.157
Под моделированием параметров или,
соответственно, моделированию системы

00:02:13.796 --> 00:02:19.195
понимаются определение зависимости
изменения локальных качеств или критериев

00:02:19.955 --> 00:02:23.833
оптимальности с учётом действующих
факторов операции.

00:02:25.439 --> 00:02:31.043
Математической моделью операции называется
формальное соотношение, устанавливающее

00:02:31.123 --> 00:02:36.527
связь принятого критерия эффективности с
действующими факторами операции.

00:02:37.808 --> 00:02:42.732
Решением, ограниченным множеством решений,
связанным с выбранной математической

00:02:42.892 --> 00:02:46.615
моделью, называется конкретный набор
значений параметров.

00:02:47.112 --> 00:02:51.474
полученных в результате использования этой
математической модели.

00:02:52.435 --> 00:02:58.158
Схематично этапы исследования операций
можно представить следующим образом

00:03:00.439 --> 00:03:02.920
Итак содержание этапов, этапы

00:03:03.688 --> 00:03:08.489
Формулировка цели операции обусловливает
выбором критериев эффективности.

00:03:10.930 --> 00:03:17.051
Первый этап — анализ системы с целью,
выбор исходного множества стратегий.

00:03:17.605 --> 00:03:22.923
Обоснованный выбор множества исходных
параметров, описывающих стратегию с учётом

00:03:23.283 --> 00:03:26.122
сформулированной цели операции — второй
этап.

00:03:26.602 --> 00:03:30.360
Третий этап — при необходимости
моделирования параметров стратегии и

00:03:30.400 --> 00:03:32.639
построения математической модели
параметров.

00:03:34.126 --> 00:03:38.451
Четвёртый. Построение математической
модели операции, получение формальной

00:03:38.531 --> 00:03:44.298
зависимости, изменение критерия качества
от изменения параметров системе.

00:03:45.419 --> 00:03:49.383
И пятый заключительный этап — получение
решения.

00:03:49.830 --> 00:03:54.390
Выбор оптимального набора параметров,
соответственно оптимальной стратегии с

00:03:54.470 --> 00:03:57.749
учётом сформулированной цели операции.

00:03:59.109 --> 00:04:04.269
Вместо методов оптимизации в общей теории
исследования операций оптимальным образом

00:04:04.429 --> 00:04:04.709
решения

00:04:05.946 --> 00:04:11.784
Формализованные задачи методы оптимизации
используются на четвёртом-пятом, при

00:04:11.944 --> 00:04:14.742
необходимости на третьем этапах.

00:04:21.900 --> 00:04:24.698
Система называется упорядоченная
совокупностью.

00:04:25.139 --> 00:04:31.057
Материальных объектов, элементов,
объединённых-либо-либо связями, например,

00:04:31.097 --> 00:04:35.456
механическими, электрическими и так далее,
предназначенными для достижения

00:04:35.816 --> 00:04:37.056
определённой цели.

00:04:37.456 --> 00:04:41.975
Если исходить из понятия, что поведение
системы есть последовательный ряд

00:04:42.055 --> 00:04:45.813
операций, то систему можно
классифицировать следующим образом.

00:04:46.823 --> 00:04:52.305
Системы детерминированные, вероятностные и
игровые.

00:04:54.105 --> 00:05:00.146
Детерминированной считается такая система,
в которой составные части взаимодействуют

00:05:00.266 --> 00:05:03.387
друг с другом точно предсказуемым образом.

00:05:03.715 --> 00:05:08.793
Её поведение предсказуемо, если известно
текущее состояние элементов и законы

00:05:08.953 --> 00:05:11.872
преобразования, циркулирующим между ними.

00:05:12.431 --> 00:05:17.949
Вероятностной называют систему возможное
поведение которой её впоследствии

00:05:18.149 --> 00:05:20.788
описывается на языке теории вероятностей.

00:05:21.068 --> 00:05:24.706
Здесь знание текущего состояния и
особенности.

00:05:25.180 --> 00:05:31.785
Взаимной связи элементов недостаточно для
однозначного предсказания будущего, что

00:05:32.025 --> 00:05:35.188
обусловливает необходимость вероятностной
оценки.

00:05:35.748 --> 00:05:42.193
Игровой называется система, осуществляющая
разумный выбор своего поведения в будущем.

00:05:42.825 --> 00:05:48.747
В основе выбора лежат неформальные
соображения, руководствоваться которыми

00:05:48.907 --> 00:05:50.508
может лишь человек.

00:05:54.269 --> 00:06:00.111
Другим важным классификационным признаком
системы является её степень сложности.

00:06:00.271 --> 00:06:04.432
По этому признаку их разделяют на простые
состояния которых

00:06:05.016 --> 00:06:08.379
Немногочисленны и легко поддаются
описанию.

00:06:08.780 --> 00:06:14.065
Сложные, отличающиеся разнообразием
внутренних связей, но допускающие их

00:06:14.185 --> 00:06:20.191
описание крупномасштабные, не поддающиеся
каким-либо описанию связи.

00:06:21.402 --> 00:06:26.966
Важное место в исследовании различного
характера является структура системы и

00:06:27.126 --> 00:06:33.811
возможность её расчленяемости на
подсистемы, каждая из которых может

00:06:34.011 --> 00:06:36.212
иметь свой критерий эффективности.

00:06:36.973 --> 00:06:39.895
Принцип расчленяемости системы находится в

00:06:40.774 --> 00:06:45.340
В основе так называемого системного
подхода, состоящего в том, что задачу

00:06:45.780 --> 00:06:52.748
оптимизации можно упростить, сформулировав
и решив её для отдельных подсистем с

00:06:52.788 --> 00:06:56.633
учётом того, в какой мере критерий
эффективности подсистемы влияет

00:06:57.210 --> 00:07:00.088
На критерии эффективности системы в целом.

00:07:05.204 --> 00:07:10.361
Эвристика оказывается полезной и
независимой при решении задач, имеющих не

00:07:10.481 --> 00:07:14.398
числовую природу или характеризуемых
сложностью определения каких-нибудь

00:07:14.638 --> 00:07:15.197
параметров.

00:07:15.735 --> 00:07:21.976
либо их формализованного сравнения Методы
оптимизации классифицируются по числу

00:07:22.096 --> 00:07:24.177
критериев оптимальности.

00:07:24.257 --> 00:07:31.018
Их подразделяют на однокрекрекритериальные
либо

00:07:31.258 --> 00:07:32.498
многокритериальные

00:07:33.485 --> 00:07:38.124
В последнем случае при выборе оптимального
решения необходимо учитывать уже не один

00:07:38.364 --> 00:07:42.963
критерий, а их совокупность, как правило,
характеризуемых

00:07:44.723 --> 00:07:48.722
разнородными параметрами, что усложняет их
сравнительную задачу.

00:07:49.405 --> 00:07:52.644
Здесь, как правило, не обойдётся без
ивристики.

00:07:57.963 --> 00:08:00.442
Однокретериальная оптимизация.

00:08:00.482 --> 00:08:06.601
Основные методы оптимизации, используемые
при синтезе детерминированных сложных

00:08:06.761 --> 00:08:07.881
технических систем.

00:08:10.144 --> 00:08:14.628
Первое — постановка и методы решения задач
математического программирования, линейное

00:08:14.788 --> 00:08:20.193
программирование. Формальные постановки
задач математического программирования.

00:08:20.553 --> 00:08:24.797
Будем в дальнейшем обозначать МП
аббревиатурой.

00:08:28.600 --> 00:08:29.040
В рамках

00:08:31.620 --> 00:08:37.701
В задач однокреториальной оптимизации
наибольший интерес представляют методы,

00:08:37.781 --> 00:08:43.021
относящиеся к группе оптимального
планирования при ограниченных ресурсах.

00:08:43.501 --> 00:08:49.062
Данными методами учитываются разнообразные
задачи, создание новой техники.

00:08:49.699 --> 00:08:54.180
Множество задач в том или ином виде может
быть сведено к постановке задачи

00:08:54.380 --> 00:08:56.301
математического программирования.

00:08:56.901 --> 00:09:01.062
С формальной точки зрения данная задача
относится к задачам математического

00:09:01.262 --> 00:09:05.503
программирования. Термин
«программирование» здесь понимается в

00:09:05.583 --> 00:09:08.063
смысле составления плана либо программы
действий.

00:09:09.572 --> 00:09:12.731
Задача оптимизации состоит в выборе
наилучших планов.

00:09:13.011 --> 00:09:17.770
Несмотря на смысловое разнообразие задач,
все они формально сводятся к одной общей

00:09:17.890 --> 00:09:24.728
постановке: найти значение переменных,
образующих максимум

00:09:24.848 --> 00:09:27.008
либо минимум значение целевой функции.

00:09:29.108 --> 00:09:34.944
Минимум-максимум, к который стремится
целевая функция F от X1, X2 и так далее,

00:09:34.984 --> 00:09:41.060
X. Замечание.

00:09:41.140 --> 00:09:44.777
В случае, когда целевая функция из
множества действительных чисел,

00:09:44.857 --> 00:09:45.417
используемых

00:09:46.040 --> 00:09:52.401
На практике то целевая функция называется
скалярной и условие G1 от X1

00:09:52.641 --> 00:09:58.921
X2 больше либо равно меньше либо равно B
IT, где от единицы до M,

00:09:59.121 --> 00:10:03.161
предположение, что каждая из N строк может
присутствовать в одной раз

00:10:04.006 --> 00:10:10.328
Рассмотренных ограничений, где функция
больше, либо равна БИТО, либо меньше либо

00:10:10.368 --> 00:10:11.728
равно БИТ.

00:10:12.249 --> 00:10:15.250
Называется областью определения задачи.

00:10:15.650 --> 00:10:20.611
Целевая функция называется целевой,
которая может представлять собой критерий

00:10:20.691 --> 00:10:23.252
оптимальности при синтезе какой-либо
системы.

00:10:24.098 --> 00:10:29.298
Таким образом, целевая функция Z достигает
экстремального значения в одной или

00:10:29.458 --> 00:10:34.699
нескольких точках области определения,
которые требуется отыскать.

00:10:35.819 --> 00:10:39.860
Обычно в постановке задачи выбора
оптимизации решения вид

00:10:40.808 --> 00:10:47.042
Целевой функции Z и Ж известны и константы
BIT, определены специально.

00:10:47.202 --> 00:10:52.638
Оговариваются ограничения, выраженные в
требуемых к неотрицательности либо к

00:10:52.718 --> 00:10:54.396
целочисленным переменным.

00:10:54.876 --> 00:10:58.513
Краткая запись условия задачи
математического программирования имеет

00:10:59.603 --> 00:11:04.284
Икс принадлежит области определения,
стремится к максимуму либо минимуму

00:11:04.444 --> 00:11:05.684
целевой функции.

00:11:07.285 --> 00:11:11.686
Два основных класса задачи математического
программирования — это задачи линейного и

00:11:11.766 --> 00:11:13.366
нелинейного программирования.

00:11:13.646 --> 00:11:16.487
К задачам линейного программирования
относятся те, кто

00:11:16.718 --> 00:11:20.998
...в котором и целевая функция Z, и все
функции жи линейны.

00:11:21.278 --> 00:11:25.758
Задачи которых присутствуют как-либо
нелинейности, соответственно, называются

00:11:25.958 --> 00:11:28.478
задачами нелинейного программирования.

00:11:28.998 --> 00:11:32.878
В данном курсе лекции мы ограничимся
рассмотрением задач линейного

00:11:33.038 --> 00:11:33.678
программирования...

00:11:34.066 --> 00:11:39.343
...которые наиболее часто требуется решать
в нашей предметной области знаний.

00:11:42.501 --> 00:11:45.539
Линейное программирование — постановка
задачи.

00:11:45.899 --> 00:11:50.856
Задача линейного программирования в общей
постановке состоит в отыскании переменных

00:11:51.176 --> 00:11:53.135
X-1 и так далее X.

00:11:53.440 --> 00:12:00.003
образующих экстримум функции Z при
ограничениях

00:12:01.364 --> 00:12:08.207
данной системакс-1 + A12x2 и так далее A1x

00:12:08.607 --> 00:12:09.768
меньше либо равно Б1

00:12:10.748 --> 00:12:17.556
И так далее. Затем Ax1 + AMX 2

00:12:17.676 --> 00:12:22.562
+ и так далее AMX меньше либо равно Б.

00:12:22.962 --> 00:12:26.206
Обычно, кроме того, на практике добавляют
требования

00:12:27.815 --> 00:12:32.579
Неотрицательности для любого X больше.

00:12:33.379 --> 00:12:38.344
Пример постановки задачи: ферма производит
откорм скота.

00:12:38.584 --> 00:12:43.388
Допустим, что имеется четыре вида
продуктов: П-1, П2, P3, p4.

00:12:43.948 --> 00:12:48.512
Стоимость единицы каждого продукта C1, Ц2,
Ц3, Ц4.

00:12:49.352 --> 00:12:54.717
Из этих продуктов требуется составить
пищевой рацион, который должен содержать

00:12:55.197 --> 00:13:01.363
белков не менее B1, углеродов не менее B2,
жиров не менее B3

00:13:02.364 --> 00:13:06.288
для продуктов Б1, Б2, Б3, Б4.

00:13:06.992 --> 00:13:12.716
Содержание белков, жиров и углеродов в
единицах на единицу продукции приведено в

00:13:12.796 --> 00:13:13.396
таблицу

00:13:21.000 --> 00:13:22.161
смотрим на таблицу.

00:13:23.142 --> 00:13:29.385
Продукты: P1, P2, P3, Б4; элементы, белки,
углероды, жиры.

00:13:29.785 --> 00:13:36.628
Ну и коэффициенты, соответственно, матрицы
данокоэффициентов A112, A1—3.

00:13:36.788 --> 00:13:40.070
Вторая строка: A21—3; третья

00:13:40.702 --> 00:13:47.468
A31, A32, A3 и четвёртое: A41, A43.

00:13:47.828 --> 00:13:53.313
Где A и J — некоторые числа и продукт
жи-элемент.

00:13:55.675 --> 00:13:56.276
Задача.

00:13:56.611 --> 00:14:01.771
Составить такой пищевой рацион, то есть
определить количество продуктов П1, П2,

00:14:01.851 --> 00:14:08.411
Б3, Б4, входящих в рацион, что при
минимальной стоимости рациона при условии

00:14:08.491 --> 00:14:11.571
выполнения ограничений белков и жиров и
углеродов.

00:14:12.596 --> 00:14:19.152
Целевая функция будет равна C1 на X1 + C2
на X2 + C3 на X3

00:14:19.591 --> 00:14:22.789
+ C4 на X4 и стремиться к минимуму.

00:14:23.229 --> 00:14:30.145
Здесь мы за X1 и так далее и так далее XN
обозначили количество

00:14:30.345 --> 00:14:31.864
продуктов, которые должны входить

00:14:32.635 --> 00:14:39.473
Рацион. Соответственно, составили систему
ограничений линейных

00:14:40.952 --> 00:14:47.471
ограничений в данном случае A1x1 + A12x2 +
A13-3 +

00:14:47.590 --> 00:14:50.350
A14 либо равно Б1.

00:14:51.364 --> 00:14:57.768
Второе ограничение A21 X1 + A2X 2

00:14:58.168 --> 00:15:04.331
+ A23-3 + A 24 X4 больше либо равно

00:15:04.451 --> 00:15:07.653
Б2. И последнее ограничение

00:15:11.930 --> 00:15:17.893
1, A3 X2; A33, A43 X4 больше либо равно

00:15:18.013 --> 00:15:22.456
Б3. Любая переменная X больше либо равна
нулю.

00:15:22.936 --> 00:15:28.459
Замечание. Измените физический смысл
параметров данной задаче, и вы получите

00:15:28.659 --> 00:15:28.699
задачу

00:15:29.732 --> 00:15:34.967
Оптимизация загрузки ресурсов,
планирование загрузки многомашинной

00:15:35.087 --> 00:15:40.043
вычислительной системы и множества иных
задач из нашей предметной области.

00:15:44.599 --> 00:15:50.155
Геометрическая интерпретация задачи,
обоснование подхода к решению.

00:15:51.787 --> 00:15:57.271
Все последующие рассуждения применимы к
формулированию задачи линейного

00:15:57.391 --> 00:16:01.994
программирования в стандартной форме,
имеющей следующее представление.

00:16:02.394 --> 00:16:07.518
Целевая функция равна сумме ЦЖ и Джим

00:16:08.907 --> 00:16:10.746
изменяется от единицы до N.

00:16:10.866 --> 00:16:15.585
При этом целевая функция может стремиться
как к максимуму, так и к минимуму.

00:16:16.585 --> 00:16:22.463
Обратим внимание на систему равенств 1:
A11x1 +

00:16:22.663 --> 00:16:26.862
A12x2 и так далее +1xN равно B1

00:16:28.693 --> 00:16:35.216
AM1x1 + AMX, + и так далее AMXN равно BM.

00:16:36.336 --> 00:16:40.698
Любую задачу линейного программирования
можно свести к подобному виду.

00:16:40.778 --> 00:16:44.060
В частности, можно изменить знак целевой
функции.

00:16:44.279 --> 00:16:45.881
...и минимизировать её.

00:16:46.202 --> 00:16:51.048
Перейти же от неравенства к равенству
можно введя дополнительные переменные.

00:16:52.129 --> 00:16:57.296
Ответить на вопрос, всегда ли задача имеет
решение, а также сформулировать требования

00:16:57.456 --> 00:16:59.618
к подходу решения можно на основании...

00:17:07.191 --> 00:17:14.037
При условии, что M-M равно K либо

00:17:14.117 --> 00:17:19.561
равно двум, то есть число уравнении на два
меньше, чем число переменных M.

00:17:19.641 --> 00:17:23.885
В этом случае интерпретация может быть
проиллюстрирована на плоскость.

00:17:25.585 --> 00:17:30.109
Известно, что M линейно независимых
уравнений всегда можно решить относительно

00:17:30.469 --> 00:17:34.353
N базисных переменных, выразив их через
ка.

00:17:34.593 --> 00:17:39.477
В нашем случае два.

00:17:40.198 --> 00:17:41.319
Свободные переменные

00:17:42.156 --> 00:17:43.715
То есть две переменных будет.

00:17:43.875 --> 00:17:50.470
Свободные переменные обозначим свободными
переменными: X1x2, базисные X3 X4.

00:17:50.630 --> 00:17:53.987
Тогда из уравнения 1 можно получить
следующую систему.

00:17:55.946 --> 00:18:00.622
X3 равно A31 X1 + A32 X2 + B3

00:18:01.370 --> 00:18:07.734
X4 равно A41 X1 + A4x2 + B4 и так далее.

00:18:07.894 --> 00:18:13.417
X N равно AN1X1 + ANX + BN.

00:18:14.138 --> 00:18:18.020
Теперь будем изображать пару свободных
переменных в системе координат.

00:18:18.825 --> 00:18:23.386
Так как по определению переменные
неотрицательные, то первое условие

00:18:23.506 --> 00:18:28.387
допустимой области решения является первый
квадрат системы координат.

00:18:28.667 --> 00:18:34.348
Теперь уточним область допустимых решений
на плоскости X1, X2.

00:18:35.700 --> 00:18:42.333
С учётом заданных ограничений приравняем
значение переменной X3 к нулю и

00:18:42.493 --> 00:18:49.166
запишем исходное уравнение в следующем
виде: ноль равен X3 и равно A31 X1 +

00:18:49.366 --> 00:18:50.804
A32 X2 + Б

00:18:53.050 --> 00:18:59.572
В системе координат X1 данное уравнение
отображают соответствующие

00:18:59.652 --> 00:19:05.455
прямой. Если её наклон и расположение
определяется соответствующими

00:19:05.535 --> 00:19:06.335
коэффициентами

00:19:07.139 --> 00:19:14.105
Данная прямая характеризуется тем, что
любая на ней точка соответствует условию

00:19:14.865 --> 00:19:16.467
X-3, равному нулю.

00:19:16.627 --> 00:19:20.310
Соответственно, в зависимости от
коэффициентов значение X-3 будет больше

00:19:20.631 --> 00:19:23.073
нуля выше отсекающей прям.

00:19:23.547 --> 00:19:26.984
прямой меньше нуля, ниже отсекающей
прямой.

00:19:27.863 --> 00:19:32.899
Обратите внимание на рисунок X3 равно
нулю.

00:19:33.618 --> 00:19:35.296
Начертили прямой.

00:19:35.816 --> 00:19:41.411
Если у нас ограничение больше либо равно,
то движение пойдёт вверх к данной прямой,

00:19:41.531 --> 00:19:43.129
если меньше либо равно нулю

00:19:43.673 --> 00:19:46.435
То прямая будет направлена вниз.

00:19:47.756 --> 00:19:54.081
Аналогичным образом можно построить
соответствующие прямые для переменных X4 и

00:19:54.201 --> 00:19:56.002
так далее X.

00:20:00.966 --> 00:20:02.807
Обратим внимание опять же на рисунок.

00:20:03.383 --> 00:20:09.539
Когда X3 равнялось нулю, прямая у нас
располагалась таким образом: при

00:20:11.657 --> 00:20:18.213
40, равное нулю вот данная прямая; при X5,
равная нулю,

00:20:18.333 --> 00:20:19.412
следующая прямая.

00:20:20.599 --> 00:20:27.566
6 равное нулю данный вид прямой
совокупность

00:20:27.726 --> 00:20:33.011
данных прямых при условии неотрицательных
переменных отсекает область допустимых

00:20:33.171 --> 00:20:35.413
решений, если она не пуста.

00:20:36.014 --> 00:20:38.977
Проведём подобную операцию с целевой
функцией.

00:20:39.411 --> 00:20:45.607
Выразим Zевую функцию через свободные
переменные и получим Z равно гамма

00:20:45.847 --> 00:20:52.763
1x1 + гамма-2.2 + гамма-нулевое, где
гамма-1-2 коэффициенты

00:20:53.243 --> 00:20:55.042
гамма-нулевое — свободный член.

00:20:55.634 --> 00:20:57.836
который для простоты опустим.

00:20:57.916 --> 00:21:00.358
Обратим данное уравнение в ноль.

00:21:01.199 --> 00:21:08.045
Тогда, соответственно, для данного
уравнения в системе координат X1-X

00:21:09.366 --> 00:21:12.929
быть построена прямая, проходящая через
систему координат.

00:21:13.678 --> 00:21:18.679
Данная прямая называется опорной прямой
либо прямой целевой функции.

00:21:18.799 --> 00:21:22.600
Для любой точке, расположенной на ней,
целевая функция равна нулю.

00:21:22.960 --> 00:21:29.281
Обозначим движение, в направлении которого
целевая функция возрастает или убывает.

00:21:30.435 --> 00:21:37.232
Итак, стрелочками показали вверх она будет
возрастать целевая функция и вниз

00:21:37.672 --> 00:21:44.509
уплывать. Из данной интерпретации видно,

00:21:44.669 --> 00:21:50.186
что в общем случае максимальное значение
целевой функции достигается в некоторой

00:21:50.306 --> 00:21:50.706
точке.

00:21:52.064 --> 00:21:56.540
Области допустимых решений, в точки
пересечения прямых, определяющих область

00:21:56.660 --> 00:21:57.978
допустимых решений.

00:21:58.418 --> 00:22:03.493
В данном случае, если прямая у нас пойдёт
вверх, посмотрите, то мы проводим

00:22:03.573 --> 00:22:07.010
параллельную прямую при движении вверх и
видим, что

00:22:07.971 --> 00:22:11.569
Z у нас вот точка в данном случае
пересечения.

00:22:13.928 --> 00:22:19.166
Ответим на вопрос: всегда ли задача имеет
решение и всегда ли оно единственно?

00:22:19.406 --> 00:22:21.325
Для этого рассмотрим два случая.

00:22:22.325 --> 00:22:25.603
Показан рисунок: первый случай, второй
случай.

00:22:26.489 --> 00:22:29.690
Первое. Область не ограничена сверху.

00:22:32.050 --> 00:22:34.851
Обратите внимание, не замкнутая фигура.

00:22:35.051 --> 00:22:41.173
Задача не имеет решений, так как всегда
можно найти значение лучше предыдущего.

00:22:41.373 --> 00:22:44.653
То есть, если мы будем двигать целевую
функцию по направлению вверх

00:22:45.187 --> 00:22:47.825
Она может возрастать до бесконечности.

00:22:48.384 --> 00:22:53.941
Второе — ограничение параллельно прямой,
отображающей целевую функцию.

00:22:54.221 --> 00:22:58.698
В этом случае имеется бесконечное
множество решений, каждое из которых

00:23:00.257 --> 00:23:04.534
отображается точкой на соответствующей
прямой области определения.

00:23:05.110 --> 00:23:06.869
И это оптимальное решение.

00:23:07.269 --> 00:23:11.267
То есть, если мы будем двигать данную
прямую, то у нас в каждой точке может быть

00:23:11.467 --> 00:23:14.626
решение, и мы будем искать наиболее
оптимальное.

00:23:18.064 --> 00:23:23.782
Замечание. Важно то, что к оптимальным
относятся и краевые точки, задаваемые

00:23:23.942 --> 00:23:26.461
пересечением прямых областей, ограничение.

00:23:29.804 --> 00:23:34.284
Выводы, основанные на геометрической
интерпретации задачи.

00:23:34.844 --> 00:23:39.444
Рассмотренная геометрическая интерпретация
в постановке задачи линейного

00:23:39.604 --> 00:23:44.923
программирования позволяет сделать важные
выводы относительно подхода к решению

00:23:45.123 --> 00:23:45.523
задачи.

00:23:46.004 --> 00:23:52.878
Первое. Решение задачи будет краевая
точка, характеризуемая тем, что К равно

00:23:52.998 --> 00:23:57.554
M s свободных переменных в нашем случае —
две переменные.

00:23:58.593 --> 00:24:03.788
Второе, как следствие, возможность решения
задачи состоит в переборе краевых точек.

00:24:05.045 --> 00:24:09.644
Третье. Переход от одной краевой точки к
другой состоит в замене свободных

00:24:09.804 --> 00:24:16.002
переменных. Очевидно, чтобы пытаться
решить задачу, можно простейшим способом

00:24:16.162 --> 00:24:19.881
задать свободные переменные и решить
систему уравнений.

00:24:20.362 --> 00:24:23.163
Это связано со следующими недостатками.

00:24:23.443 --> 00:24:28.605
Первое — можно получить решение не в
области допустимых решений.

00:24:29.166 --> 00:24:34.168
Второе — задача может быть весьма
громоздкой, например, N равно тридцати, Н

00:24:34.368 --> 00:24:39.770
10, то есть сочетание 10 из 30 будет
составлять огромное число.

00:24:40.595 --> 00:24:46.668
Обратите внимание 30 045

00:24:47.627 --> 00:24:54.420
015. Вывод: возникает задача перебора
краевых

00:24:54.979 --> 00:24:55.739
вершин, то есть

00:24:56.339 --> 00:24:59.256
Направленного перехода к оптимальному
решению.

00:24:59.616 --> 00:25:03.812
Как следствие, возникает задача,
обоснованная критерием оптимальности

00:25:04.012 --> 00:25:05.770
перехода между краевыми точками.

00:25:11.666 --> 00:25:15.741
К такому виду системы всегда сводится
ввиду линейности ограничений, так как

00:25:15.901 --> 00:25:22.294
всегда можно выразить переменные X1 и так
далее X2 через какие-либо коэффициенты.

00:25:22.693 --> 00:25:27.927
F1 равно F1 со звёздочкой — это
коэффициенты X1.

00:25:28.216 --> 00:25:30.936
Плюс и так далее X.

00:25:32.255 --> 00:25:38.135
X равно f звёздочка от M X + 1 и так далее
X.

00:25:38.495 --> 00:25:43.254
В данном представлении переменные X.1 и
так далее X называются свободными.

00:25:43.684 --> 00:25:45.364
Все остальные базисными.

00:25:46.444 --> 00:25:51.805
Соответственно, при данном представлении
можно определить некоторые базисные

00:25:52.325 --> 00:25:57.685
базисные решения: X 1 равно B1, X равно B
X

00:25:59.285 --> 00:26:01.525
+ 1 равно X N равно нулю.

00:26:10.087 --> 00:26:15.723
Симплекс алгоритм процесса приближения к
оптиму, направленный перебор колевых

00:26:15.803 --> 00:26:22.519
решений. Пусть задача представлена к
соответственно

00:26:22.839 --> 00:26:26.037
сразу получаемых несколько исходных
базисных

00:26:26.763 --> 00:26:32.839
Решений. Возникают следующие вопросы:
оптимально или единственно ли оно.

00:26:33.039 --> 00:26:38.716
Если не оптимально, а ранее мы показали,
что поиск решений состоит в переборе

00:26:38.836 --> 00:26:44.432
краевых вершин, то возникает вопрос: как
осуществить переход к следующему решению?

00:26:47.297 --> 00:26:54.249
Вспоминание, что целевая функция выглядит
следующим образом: Z равна сумма Цжитого

00:26:54.329 --> 00:26:58.245
на X-житое, где Ж изменяется от единицы до
N.

00:26:59.244 --> 00:27:03.440
Просуммируем, соответственно, уравнение в
системе два.

00:27:04.080 --> 00:27:10.872
их на коэффициенты ЦЖ Тогда Система 2
будет представлять следующий вид: C1x1

00:27:11.152 --> 00:27:18.064
+ A1x +1 и так далее A1x равно

00:27:18.144 --> 00:27:19.062
C1 на B1

00:27:21.435 --> 00:27:28.314
И так далее. И последнее: c1x M + 1xM +1

00:27:28.554 --> 00:27:33.474
+ AMX равно CM на BT.

00:27:34.154 --> 00:27:38.234
Тогда целевая функция будет иметь вид
суммы Ц.

00:27:38.474 --> 00:27:39.354
на Xжитые плюс

00:27:39.841 --> 00:27:46.240
Сумма C + 1 X житое

00:27:46.720 --> 00:27:51.879
равно Z к нулевому + сумма m + 1 житое X

00:27:51.998 --> 00:27:53.758
жито.

00:27:53.918 --> 00:27:58.117
Где c + 1 житое, коэффициент при свободных
переменных

00:27:58.600 --> 00:28:05.328
...зависит от значения A и ж, Б и по
своему смыслу и значение

00:28:05.488 --> 00:28:08.652
целевой функции для исходного базисного
решения.

00:28:09.173 --> 00:28:13.498
Теорема. Допустимое базисное решение X.

00:28:13.928 --> 00:28:20.601
Ж равно B1, при E равно от единицы до M, X
равно нулю, при Ж равно M + 1

00:28:20.920 --> 00:28:27.872
и так далее M. Является оптимальным, если
коэффициент C MG выражении

00:28:28.072 --> 00:28:29.310
3 неотрицателен.

00:28:32.767 --> 00:28:38.371
Доказательство. Если переменные C MT
больше либо равны нулю, то при любых

00:28:38.491 --> 00:28:44.615
значениях неотрицательных переменных X,
разность Z и Z нулевое — неотрицательная

00:28:45.215 --> 00:28:46.736
её минимум есть ноль.

00:28:46.896 --> 00:28:48.177
Следовательно, З не

00:28:49.551 --> 00:28:53.987
Не будет меньше ЗТ- нулевого, что говорит
о том, что его нельзя уменьшить.

00:28:54.387 --> 00:29:00.501
Следствие. Любые решения системы 1,
которым соответствует нулевая

00:29:01.100 --> 00:29:07.854
сумма CM-житое и сжитые, при любых
ЦМ-житых больше либо равных нулю, и

00:29:08.014 --> 00:29:09.692
сжитых больше либо равных нулю.

00:29:10.308 --> 00:29:14.872
Будет оптимальным, соответственно, при
условии, что CMжитые меньше нуля, решение

00:29:15.072 --> 00:29:16.273
может быть улучшено.

00:29:16.794 --> 00:29:23.039
Допустимое оптимальное базисное решение
окажется единственным, если все CMжит

00:29:23.360 --> 00:29:26.162
больше нуля, то есть строго больше.

00:29:28.206 --> 00:29:32.443
Данное следствие является
сформулированными признаками оптимальности

00:29:32.803 --> 00:29:35.361
и единственными оптимальными решениями.

00:29:35.761 --> 00:29:41.517
Теперь рассмотрим, как осуществить переход
к новому решению и сформулируем критерии

00:29:41.557 --> 00:29:44.275
оптимальности выбора направления перехода.

00:29:45.007 --> 00:29:49.283
Пусть среди коэффициентов CMG есть
отрицательное значение.

00:29:49.483 --> 00:29:55.117
Это значит, что данные давая приращение
соответствующим переменным, целевая

00:29:55.277 --> 00:30:00.672
функция целевую функцию можно уменьшить,
чтобы перейти к другому целевому решению.

00:30:02.040 --> 00:30:08.035
Как следует из неотрицательности
необходимо сделать положительный, ввести в

00:30:08.115 --> 00:30:14.950
базис какую-то переменную X+1, равную x,
равную нулю, обратив в нуль

00:30:15.149 --> 00:30:16.948
одну из переменных X1 либо

00:30:18.110 --> 00:30:23.750
Соответственно, базис должно вводиться та
переменная, ей даётся положительное

00:30:23.870 --> 00:30:30.109
преращение, соответственно, которая имеет
выражение для целевой функции

00:30:30.349 --> 00:30:32.269
отрицательный коэффициент.

00:30:33.389 --> 00:30:34.748
Обозначим через S.

00:30:35.082 --> 00:30:41.082
Тот номер G или N + 1 величины
коэффициентов M и G, для которого

00:30:43.283 --> 00:30:45.123
сочетание минимально.

00:30:45.203 --> 00:30:49.843
Отсюда бросается в глаза очевидный подход
к поиску оптимального решения.

00:30:50.594 --> 00:30:56.591
...который используется эээ в системе
ограничений.

00:30:56.831 --> 00:31:03.468
Соответственно, будем давать положительное
приращение к переменной X, данное, давая

00:31:03.668 --> 00:31:06.187
данное приращение из уравнения 2
получим...

00:31:08.201 --> 00:31:09.321
X1 равно

00:31:09.481 --> 00:31:16.080
B1SM равно

00:31:19.400 --> 00:31:24.239
Для Z имеет Z равно Z нулевое + CMS

00:31:24.762 --> 00:31:28.922
X S, причём CM S меньше нуля.

00:31:29.282 --> 00:31:35.403
Естественно, что, выбрав направление
движения, целесообразно максимально

00:31:35.603 --> 00:31:41.524
увеличить переменную X Чтобы получить
максимальное выражение в значении целевой

00:31:41.644 --> 00:31:42.124
функции.

00:31:43.273 --> 00:31:48.914
Однако возрастание переменной X ввиду
требования к неотрицательной переменной

00:31:49.554 --> 00:31:54.755
возможно до тех пор, пока какая-то из
свободных переменных не обратится в ноль.

00:31:55.075 --> 00:31:58.116
То есть, пока не достигнем ограничения
значения.

00:31:58.716 --> 00:32:00.196
Это произойдёт, если хотя бы

00:32:01.005 --> 00:32:06.646
Один коэффициент с индексом X
положительным по условию и среди Bит нет

00:32:06.806 --> 00:32:12.767
отрицательных. Если все A и S
положительны, то первая в ноль обратится

00:32:13.528 --> 00:32:17.888
та базисная переменная, для которой будет
выполняться X равно минимуму.

00:32:19.443 --> 00:32:25.360
Это и есть формализованное условие
перехода к последующей краевой вершине.

00:32:27.599 --> 00:32:29.079
Симплекс-метод.

00:32:30.038 --> 00:32:36.355
Решение было показано, что система
ограничений предполагает направленный

00:32:36.515 --> 00:32:37.835
перебор краевых вершин.

00:32:38.742 --> 00:32:43.260
Мы определились с тем, каким образом
осуществлять данный перебор, как выбрать

00:32:43.500 --> 00:32:48.338
направление перебора, как определить, что
в итоге получено оптимальное решение.

00:32:48.657 --> 00:32:53.296
Всё это ранее было выражено в формальном
виде, приведены соответственно формулы для

00:32:53.376 --> 00:32:53.695
расчёта

00:32:55.290 --> 00:33:01.130
Однако остаётся проблема, состоящая в том,
как найти то первое допустимое решение, а

00:33:01.290 --> 00:33:06.730
это должна быть краевая точка, с которой
начинать направленный перебор вершин.

00:33:06.890 --> 00:33:10.650
То есть, когда уже установлена возможность
применения решения.

00:33:11.327 --> 00:33:17.609
Для этого цели и служит математическая

00:33:17.809 --> 00:33:24.770
система, состекс метода, состоящий в
двухэтапном решении задачи.

00:33:25.050 --> 00:33:28.211
На первом этапе требуется найти какое-либо
решение задачи.

00:33:29.080 --> 00:33:31.000
То есть найти исходную краевую точку.

00:33:31.120 --> 00:33:35.440
На втором осуществить перебор вершин с
целью поиска оптимального решения.

00:33:35.801 --> 00:33:40.441
При этом будем помнить, что краевая точка
легко отыскивается в случае представления

00:33:40.601 --> 00:33:45.082
задачи краевых вершин.

00:33:46.499 --> 00:33:51.179
Симплекс-метод предполагает в общем случае
двухэтапное решения

00:33:53.579 --> 00:34:00.179
данных задач. Первый этап начинается с
формального введения в каждую строчку

00:34:00.619 --> 00:34:02.539
стандартной системы искусственной

00:34:03.471 --> 00:34:07.706
неотрицательные переменной для получения
краевых вершин.

00:34:07.746 --> 00:34:13.658
Например, что при представлении задачи в
данном виде сразу можно определить решение

00:34:13.898 --> 00:34:18.373
задачи. Дана исходная задача A1x

00:34:22.533 --> 00:34:28.654
И так далее. A1x1+ и так далее AMXN равно
BM.

00:34:30.014 --> 00:34:36.895
Краевая вершина вводятся новые переменные
и приравнивается к данной системы

00:34:37.015 --> 00:34:37.495
равенства.

00:34:38.778 --> 00:34:45.747
...вновь введённым переменным B1, Baco

00:34:45.907 --> 00:34:51.434
этим мы изменили собственно задачу, в
которой в каком случае решения новой

00:34:51.514 --> 00:34:53.757
задачи и исходной задачи будут совпадать.

00:34:54.710 --> 00:34:59.434
Если существует решение для первой задачи,
то оно допустимо и для второй при условии,

00:34:59.475 --> 00:35:04.039
что X+ 1 равно икс M плюс N равно нулю.

00:35:04.399 --> 00:35:09.725
Так как именно эти переменные были нами
введены ввиду их неотрицательности.

00:35:10.212 --> 00:35:13.132
При данном случае все переменные
обращаются в ноль.

00:35:13.652 --> 00:35:17.973
Рассмотрим сумму наименьших значений,
которых есть ноль.

00:35:18.253 --> 00:35:25.133
Ввиду неотрицательности переменных при X +
1 равно X + N равно нулю.

00:35:25.753 --> 00:35:32.705
Таким образом, проверка условия минимума
суммы для второй системы ограничений

00:35:32.905 --> 00:35:37.100
является условием совпадения решений для
первой и второй задач.

00:35:39.497 --> 00:35:40.856
С учётом сказанного, первый

00:35:41.605 --> 00:35:48.046
Этап решения симплекс-метода состоит в
поиске какого-либо решения исходной задачи

00:35:48.526 --> 00:35:53.247
посредством решения следующей
оптимизационной задачи.

00:35:53.727 --> 00:35:57.888
То есть, если мы будем находить минимум
симплекс-метода.

00:35:58.339 --> 00:36:02.703
С учётом ограничений системы, заданной для
второй задачи.

00:36:03.184 --> 00:36:09.069
Для данной задачи приведён краевой
вершине, то есть может быть применён

00:36:09.189 --> 00:36:14.554
Simplex-метод: легко находится первое
решение: X+1 равно B1 и так далее.

00:36:15.372 --> 00:36:17.091
M плюс N равно Б.

00:36:17.891 --> 00:36:21.089
А X1 и так далее X равно нулю.

00:36:21.289 --> 00:36:27.446
После чего может быть использована система
с целью поиска оптимального решения.

00:36:27.925 --> 00:36:31.004
Если удаётся найти оптимальное решение,
для которого

00:36:31.807 --> 00:36:36.812
Если сумма равна нулю, то это решение
является исходным для основной задачи.

00:36:37.092 --> 00:36:40.095
В противном случае задача неразрешима.

00:36:49.305 --> 00:36:49.865
Смотрите.

00:36:50.915 --> 00:36:56.155
Прямоугольная система координат, ось
абцисса Tx1, ось координат Tx2.

00:36:56.475 --> 00:36:58.954
Сумма равная нулю в данной точке.

00:36:59.434 --> 00:37:05.754
Основная задача — выпуклый многоугольник и
вспомогательн- вспомогательная задача

00:37:05.874 --> 00:37:07.193
линейного программирования.

00:37:07.925 --> 00:37:10.007
В данном случае определено на графике.

00:37:10.807 --> 00:37:15.090
Второй этап состоит в решении основной
задачи, в использовании

00:37:17.611 --> 00:37:20.853
решения системы уже для решения основной
задачи.

00:37:21.014 --> 00:37:23.535
При этом получим решение вспомогательной
задачи

00:37:24.199 --> 00:37:30.194
Рассмотренная как исходная для основной
проверяется на оптимальность при

00:37:30.354 --> 00:37:35.231
необходимости осуществления
последовательного перебора решений.

00:37:36.869 --> 00:37:40.387
Замечание. Здесь уже используется целевая
функция Z.

00:37:44.533 --> 00:37:48.773
Примеры решения задачи линейного
программирования Simplex Metod.

00:37:49.053 --> 00:37:54.973
Пусть имеется некоторый материал в виде
стандартных листов, которые надо раскроить

00:37:55.253 --> 00:38:01.373
таким образом, чтобы получить не менее 80
деталей первого типа и не менее 42.

00:38:02.140 --> 00:38:08.135
Известно четыре способа раскроя листа, для
которого результаты раскроя представлены в

00:38:08.215 --> 00:38:13.890
таблице. Итак, Cn равно один, два, три,

00:38:14.010 --> 00:38:15.289
четыре.

00:38:16.488 --> 00:38:17.567
Четыре способа.

00:38:20.477 --> 00:38:26.116
В данном случае некоторый материал и
указаны

00:38:27.235 --> 00:38:28.715
коэффициенты.

00:38:31.514 --> 00:38:35.793
Требуется получить необходимое число
деталей при минимальном расходе листов

00:38:35.913 --> 00:38:39.032
материала, обозначим через их жить
количество листов.

00:38:39.694 --> 00:38:42.136
Расходуемых столбцом.

00:38:42.256 --> 00:38:44.818
Целевая функция в данном случае будет
иметь вид.

00:38:44.858 --> 00:38:49.342
Z равно X1 + X 2 + X 3 + X 4.

00:38:49.582 --> 00:38:56.508
При этом должны выполняться следующие
условия: 31, 2x2

00:38:57.687 --> 00:39:03.692
X3 больше либо равно восьмидесяти X1

00:39:04.893 --> 00:39:11.619
+6 X2 + 2 X3 в данном случае

00:39:11.939 --> 00:39:12.940
девять X3, да?

00:39:13.385 --> 00:39:15.944
...и 134 больше либо равна

00:39:16.104 --> 00:39:22.783
40, то есть, в данном случае опечатка не
2.x3, а

00:39:22.863 --> 00:39:28.701
93. Для применения симплекс-метода прежде
всего задачу требуется привести к

00:39:28.741 --> 00:39:29.781
стандартному виду.

00:39:30.380 --> 00:39:34.463
То есть систему ограничений мы должны
привести к системе равенств.

00:39:34.823 --> 00:39:40.627
Вводим новые переменные: 3 X1 + 2 X2 + X 3

00:39:41.227 --> 00:39:48.152
-x5 равно восемьдесят; X1 +6 X2 + 9 X 3 +
13 X4 -

00:39:48.232 --> 00:39:48.633
X6

00:39:49.193 --> 00:39:52.833
...равно сорока. Вводятся новые
переменные, при этом они не должны

00:39:53.113 --> 00:39:58.712
повторяться. У нас в заданной системе
ограничений четыре переменные, значит,

00:39:58.752 --> 00:40:02.752
вводим дополнительные, которые не
повторяются — это X5 и X6.

00:40:03.032 --> 00:40:06.552
Таким образом, так как ограничения были
больше либо равно...

00:40:06.975 --> 00:40:10.492
Из каждой строки нужно вычесть,
соответственно, переменную.

00:40:10.732 --> 00:40:17.525
Очевидно, базисное решение: -к5 равно
восьмидесяти, минус X6 40 X1 и так далее,

00:40:17.565 --> 00:40:19.403
X4 равны нулю.

00:40:22.560 --> 00:40:26.916
Недопустимо ввиду неотрицательности
переменной, так как данное решение

00:40:27.116 --> 00:40:27.875
недопустимо.

00:40:28.385 --> 00:40:30.622
Задачу необходимо решить в два этапа.

00:40:31.222 --> 00:40:38.173
Первый этап — решение вспомогательных
задачи приведём исходную задачу к краевым

00:40:38.213 --> 00:40:44.806
вершинам. Наша система примет следующий
вид: 31 + 2 X 2 +

00:40:45.286 --> 00:40:48.682
X-xex 3 -X 5 + X 7 равно 80.

00:40:49.641 --> 00:40:56.314
Второе равенство: X1 +6 X2 +9 X3 + 13 X4
-X6 + X8

00:40:56.594 --> 00:40:59.031
равно сорок сорок.

00:40:59.151 --> 00:41:02.348
Для этого введём дополнительные
переменные: X7 X8

00:41:03.294 --> 00:41:08.935
Соответственно, сформулируем и решаем
данную задачу целевой функцией, которая

00:41:09.335 --> 00:41:14.777
должна быть минимизирована, помня, что её
решение будет решением основной при

00:41:14.897 --> 00:41:16.778
условии, что сумма равна нулю.

00:41:17.098 --> 00:41:19.738
Здесь легко отыскивается и исходное
значение.

00:41:20.865 --> 00:41:27.704
X7 равно восьмидесяти, X8 — сорок, X1 и
так далее — X6 — нулевое, сумма 80

00:41:27.864 --> 00:41:29.584
+ 40 — 120.

00:41:31.824 --> 00:41:37.463
Применим следующий метод систем и, прежде
всего, проверим получение решения на

00:41:37.543 --> 00:41:38.223
оптимальность.

00:41:39.231 --> 00:41:45.959
Рассмотрим целевую функцию, равную сумме
X7 + X8, в которой переменные X7 X8

00:41:46.239 --> 00:41:47.921
выразим через остальные.

00:41:48.602 --> 00:41:54.889
Итак, сумма равна X7 + X8, равна 80 - 3 X1
- 2x2.

00:41:55.465 --> 00:42:01.898
X3 + X5 + 40, -X1 — -6 X2, -9 X3, -13

00:42:02.178 --> 00:42:03.697
X4 + 6.

00:42:03.936 --> 00:42:10.889
В результате нахождения подобных
переменных получаем 120 - 4, -8 X2, -

00:42:11.009 --> 00:42:11.609
10 X-3

00:42:12.289 --> 00:42:16.252
Минус 13 X4 + 5 и + X6.

00:42:17.773 --> 00:42:23.378
Присутствие отрицательных коэффициентов
указывает на неоптимальность полученного

00:42:23.538 --> 00:42:28.222
решения, так как максимальное по модулю
отрицательное значение коэффициента

00:42:28.612 --> 00:42:33.214
Если имеет переменные X4, то в
соответствии с рассмотренным ранее

00:42:33.334 --> 00:42:39.217
критерием, именно ей будет давать
положительное преращение X-3 равно X4.

00:42:39.577 --> 00:42:44.939
Теперь рассмотрим, для какой величины
можно увеличить X-4, а при этом переменная

00:42:45.099 --> 00:42:45.700
обнулится.

00:42:46.972 --> 00:42:51.736
X7 равно восьмидесяти, X8 равно 40, - 13 —
X4.

00:42:52.657 --> 00:42:58.742
Вводя положительные переменные X4 из
исходной системы для нашего решения имеем,

00:42:58.982 --> 00:43:02.465
таким образом, видим, что X4 можно
увеличить до значения

00:43:03.371 --> 00:43:04.610
413.

00:43:04.930 --> 00:43:11.802
При этом X8 обратится в ноль, и получим
новое решение: X1 равно X2 равно X3 равно

00:43:11.922 --> 00:43:18.914
нулю, X4 равно сорок тринадцатых X5 равно
X6 равно нулю, X7 равно восьмидесяти;

00:43:18.954 --> 00:43:19.434
X8

00:43:21.477 --> 00:43:24.958
Сумма будет равна 80 + 413.

00:43:25.318 --> 00:43:28.960
Проверим полученное решение на
оптимальность, для этого выразим целевую

00:43:29.080 --> 00:43:34.002
функцию, так как 8 равно нулю, выразим
только X7.

00:43:36.152 --> 00:43:42.317
Ну и получается у нас сумма будет равна X7
+ X8 равна - 3 X1 - 2

00:43:42.437 --> 00:43:46.360
X2, -X 3 + X5 -X8.

00:43:47.321 --> 00:43:51.925
Видим, что решение неоптимально, и так как
максимальный отрицательный коэффициент

00:43:52.085 --> 00:43:53.246
имеет переменная X-1

00:43:53.995 --> 00:43:56.798
То именно ей надо дать положительное
превращение.

00:43:57.238 --> 00:44:02.524
Определим, для каждого значения можно
увеличить X1 и какая при этом переменная

00:44:02.604 --> 00:44:06.568
обратится в ноль X4 X7 — не нулевые
значения.

00:44:07.329 --> 00:44:10.452
Тогда X7 будет равно 80 - 3x1.

00:44:10.762 --> 00:44:14.606
X4 40 -X1 разделить на 13.

00:44:15.206 --> 00:44:22.092
X1 может разности достигнет разности до
восьмидесяти третьих.

00:44:22.212 --> 00:44:29.058
При этом обращается в ноль, X7 получаем X1
равно

00:44:29.138 --> 00:44:32.221
восемь третьих, X4 40 39.

00:44:32.919 --> 00:44:37.835
X2, X3, X5, X6, X7, X8 равно нулю.

00:44:38.075 --> 00:44:41.952
Сумма будет равна нулю, X7, X8.

00:44:42.391 --> 00:44:43.950
Это оптимальное решение.

00:44:44.430 --> 00:44:47.947
Так как целевая функция не содержит
отрицательных коэффициентов

00:44:48.455 --> 00:44:53.090
Если её минимум есть ноль, то найденное
оптимальное решение может рассматриваться

00:44:53.290 --> 00:44:56.566
как исходное решение для выполнения
второго этапа.

00:44:56.886 --> 00:45:03.759
Второй этап — система равенств первое: 3'1
+ 2 X2 + X 3 - X-5 равно

00:45:03.879 --> 00:45:04.638
восьмидесяти.

00:45:05.093 --> 00:45:10.528
X1 +6 X2 + 9: X3 + 13: X4 - X6 — равно 40.

00:45:10.768 --> 00:45:16.763
Исходное решение X1 равно 83, X4:40 39;

00:45:17.202 --> 00:45:21.158
X2: X3, X5; X6; X7; X8 равно нулю.

00:45:21.654 --> 00:45:25.180
Сумма икс равна X7 X8 равна нулю.

00:45:25.500 --> 00:45:29.427
Имея допустимое базисное решение,
полученное на первом этапе решения,

00:45:29.507 --> 00:45:31.750
начинаем решение основной задачи.

00:45:32.672 --> 00:45:33.273
Второй этап

00:45:36.949 --> 00:45:39.587
Прежде всего проверим оптимальность
полученного решения.

00:45:39.667 --> 00:45:41.826
Для этого выразим X1 X4.

00:45:42.066 --> 00:45:48.981
Получаем из четвёртой системы: X1 равно 80
- 2 X2 - X3 + X5,

00:45:49.021 --> 00:45:51.939
делённое на 3; X4 равно 40 минус

00:45:52.626 --> 00:45:58.071
X1 - 2 X 2 -9 X 3 + X 6, делённое на 13.

00:45:58.271 --> 00:46:04.276
Целевая функция Z будет равна X1 + X 2 + X
3 + X 4 и равна.

00:46:04.436 --> 00:46:08.080
Подставляем вместо X1 X4 коэффициенты

00:46:08.574 --> 00:46:15.287
Находим подобное. В результате получим 1
080 - 3 x2 + 12 X1 + 3

00:46:15.407 --> 00:46:17.405
X6, делённое на 39.

00:46:17.844 --> 00:46:23.997
Вывод. Полученное решение не оптимально,
следует дать при вращении переменной X2

00:46:24.745 --> 00:46:29.824
Для определения того, насколько
увеличивать X2, выразим наши нулевые

00:46:29.904 --> 00:46:32.743
переменные X1 и X4 через X2.

00:46:32.983 --> 00:46:39.862
Получим: X-1 равно 80 - 2 X2, делное на 3;
X4 равно

00:46:39.942 --> 00:46:42.901
40 -16 X2, делённое на 39.

00:46:43.734 --> 00:46:45.692
X1 выражаем через X2.

00:46:45.972 --> 00:46:52.126
Отсюда получаем, что X2 может
увеличиваться на 2,5, при этом X4

00:46:53.045 --> 00:46:59.239
превращаем в ноль. X1 равно 25, X2 — 2,5,
X

00:47:00.784 --> 00:47:05.179
Целевая функция будет равна 27,5%.

00:47:05.619 --> 00:47:08.336
Проверим данное решение на оптимальность.

00:47:08.576 --> 00:47:15.169
Для этого выразим целевую функцию через
переменные X1, X2, X3, X4.

00:47:15.488 --> 00:47:18.845
Подставим вместо X значение.

00:47:19.425 --> 00:47:26.032
Вместо X1 и X4 получим 440 + 2 X 3 + 3 X 4
+ X5 + 5

00:47:26.152 --> 00:47:28.195
X6 разделить на 16.

00:47:28.515 --> 00:47:33.080
Вывод. Данное решение задачи является
оптимальным и единственным.

00:47:33.241 --> 00:47:34.963
Таким образом, оптимальный способ

00:47:35.571 --> 00:47:42.445
Раскроя листов. Посмотрите ещё раз задачу
в следующем: 25

00:47:42.685 --> 00:47:46.241
кровь кроить первым способом, 2, половиной
вторым.

00:47:46.481 --> 00:47:50.597
В результате потребуется 25 с половиной
листов.

00:47:53.917 --> 00:47:55.637
Недостатки Symplex метода.

00:47:55.757 --> 00:48:00.396
Метод решения основан на геопетрической
интерпретации задачи линейного

00:48:00.556 --> 00:48:05.715
программирования. Собственно, критерий
оптимальности не призван оптимизировать

00:48:06.914 --> 00:48:11.273
вычислительную процедуру, так как
сложность вычислений представляется числом

00:48:11.862 --> 00:48:13.301
Перебираемых вершин.

00:48:13.501 --> 00:48:18.340
В то время как критерии оптимальности не
минимизируют их числа при поиске

00:48:18.580 --> 00:48:20.060
оптимального решения.

00:48:20.899 --> 00:48:27.058
Сложность использования вычислительных
средств для решения задачи алгоритмы,

00:48:27.098 --> 00:48:30.057
ориентированные на применение
вычислительных средств.

00:48:30.384 --> 00:48:35.779
... должны характеризоваться по
возможности простейшими операциями: плюс,

00:48:35.819 --> 00:48:37.097
минус и так далее.

00:48:37.337 --> 00:48:42.013
Здесь же, при обработке каждого решения,
необходимо решать достаточно сложные

00:48:42.133 --> 00:48:46.768
системы уравнений, что сложно
формулируется на AVM.

00:48:46.808 --> 00:48:47.447
Таким образом,

00:48:48.470 --> 00:48:52.869
Можно сделать вывод, что для решения задач
большей размерности, где необходимо

00:48:52.989 --> 00:48:59.949
применение ЭВМ, необходимы иные подходы,
следовательно, другая интерпретация

00:49:00.269 --> 00:49:02.789
задачи и критерии оптимальности.

00:49:03.269 --> 00:49:07.108
Особенно сложен симплис-метод для решения
целочисленных задач.

00:49:09.878 --> 00:49:12.921
Целочисленное программирование метод
Гаммори.

00:49:14.562 --> 00:49:20.167
Задачи сформулированные в терминах
линейного программирования и содержащие

00:49:20.247 --> 00:49:25.732
требования все или некоторые переменные,
целые числа, называются задачами

00:49:26.052 --> 00:49:27.854
целочисленного программирования.

00:49:28.474 --> 00:49:31.392
Рассмотрим пример интерпретации задачи.

00:49:36.628 --> 00:49:43.623
Задана прямоугольная система координат,
дана выпуклая

00:49:43.663 --> 00:49:44.183
фигура.

00:49:46.193 --> 00:49:51.075
Девять точек, которые находятся в данной
области, и целевая функция

00:49:52.875 --> 00:49:54.276
определена прямой.

00:49:54.636 --> 00:50:00.198
Пусть к X1 выставлены требования целой
численности.

00:50:00.438 --> 00:50:02.999
Решение задачи в этом случае будет
располагаться

00:50:03.749 --> 00:50:08.753
На соответствующих непересекающихся
линиях, характеризующих целочисленность

00:50:08.953 --> 00:50:13.476
переменных. Если обе переменные
целочисленные, то решение задачи

00:50:13.676 --> 00:50:18.800
определяется узлами соответствующей
решётки на плоскости метода гамори.

00:50:19.099 --> 00:50:23.304
Состоит из выполнения следующих шагов.

00:50:24.745 --> 00:50:28.870
Решается задача классическим
сиблекс-методом, и полученное решение

00:50:29.070 --> 00:50:30.992
проверяется на целочисленность.

00:50:31.152 --> 00:50:35.436
Если полученное решение не целочисленное,
водят по определённым правилам

00:50:36.400 --> 00:50:40.683
...систему ограничений, отсекающих
полученное решения и задача решается

00:50:40.923 --> 00:50:45.406
вновь. Процедура повторяется, пока не
найдено целочисленное решение.

00:50:45.926 --> 00:50:50.690
Вывод: условие целочисленности
принципиально усложняет решение задачи,

00:50:50.890 --> 00:50:55.733
так как в общем случае требует
многократное применение симплекс методов.

00:50:56.157 --> 00:51:00.557
С увеличением области ограничений и с
введением дополнительных условий.

00:51:15.501 --> 00:51:21.416
Методы оптимизации ориентированы на
применение ЭВМ, общий подход к построению.

00:51:25.772 --> 00:51:32.126
Сложный подход в математической задаче.

00:51:33.203 --> 00:51:39.404
Методом потенциалов называется
необходимость разработки методов

00:51:39.524 --> 00:51:44.245
оптимизации, базирующихся на
вычислительных и логических операциях.

00:51:44.605 --> 00:51:47.805
Общей для этих методов является
необходимость доказать

00:51:48.443 --> 00:51:51.441
Доказательство целесообразности и
достаточности.

00:51:51.880 --> 00:51:56.037
Целесообразность обусловливается
интерпретацией или физическим смыслом

00:51:56.157 --> 00:52:01.073
метода решения достаточность
доказательством исходности алгоритма.

00:52:01.393 --> 00:52:04.870
Каждый алгоритм предполагает некоторые
правило поиска решений.

00:52:05.332 --> 00:52:08.055
...и обусловливает переход к последующему
решению.

00:52:08.455 --> 00:52:14.061
Отношения, связывающие очередные решения
при использовании алгоритма, называется

00:52:14.182 --> 00:52:16.064
алгоритмическим отображением.

00:52:16.344 --> 00:52:20.749
Алгоритм, построенный на основе
отображения, сходится, если он...

00:52:21.162 --> 00:52:22.960
позволяет либо непосредственно

00:52:27.635 --> 00:52:33.030
вычислить оптимальное экстремальное
значение, либо представляет его в виде

00:52:33.349 --> 00:52:36.466
некоторой предельной точки задаваемой
последовательностью.

00:52:37.115 --> 00:52:43.919
приближения. В общем случае следует
говорить о сходимости алгоритма в смысле

00:52:44.440 --> 00:52:47.281
существования подобной предельной точки.

00:52:47.842 --> 00:52:52.644
Основной группой методов оптимизации,
ориентированных на использование ЛММ,

00:52:52.764 --> 00:52:55.366
является так называемые методы возможных
направлений.

00:52:56.115 --> 00:53:00.632
Общая идея методов возможных направлений
состоит в следующем: от изначально

00:53:00.872 --> 00:53:06.509
допустимой по условию задачи точки X1
осуществляется переход к новой допустимой

00:53:06.629 --> 00:53:10.387
точке, в которой значение целевой функции
лучше, чем в предыдущей.

00:53:10.907 --> 00:53:14.745
Процесс продолжается до тех пор, пока
остаётся возможность улучшить значение

00:53:14.905 --> 00:53:15.705
целевой функции.

00:53:16.343 --> 00:53:19.783
Либо задача не может быть решена с
заданной точностью.

00:53:19.982 --> 00:53:24.421
При этом на каждом шаге для перехода в
последующую точку требуется определить

00:53:24.581 --> 00:53:26.941
направление перехода и длины шага.

00:53:27.021 --> 00:53:30.460
Таким образом, следующий шаг определяется
по формуле.

00:53:39.818 --> 00:53:42.097
Где вернее, альфа-К.

00:53:42.217 --> 00:53:46.935
Альфа-К — величина ка шага, РК —
единственный вектор, определяющий

00:53:47.334 --> 00:53:49.094
направление перемещения.

00:53:50.493 --> 00:53:54.251
Данное равенство является общим для
рассматриваемой группы методов

00:53:54.331 --> 00:53:55.131
оптимизации.

00:53:55.515 --> 00:53:59.716
Интерпретация же подхода к её решению
призвана задавать правила определения

00:53:59.916 --> 00:54:03.957
параметров РК и Альфа-К...

00:54:03.997 --> 00:54:06.477
Метод решения задачи линейного
программирования.

00:54:07.293 --> 00:54:11.535
Рассмотрим данный метод как метод,
относящийся к группе методов возможных

00:54:11.896 --> 00:54:16.698
направлений, оцениваем его преимущества и
недостатки по сравнению с традиционным

00:54:16.898 --> 00:54:21.500
симплекс-методом, проиллюстрируем
интерпретацию данного метода решением

00:54:23.061 --> 00:54:25.658
Решённым ранее примером.

00:54:25.738 --> 00:54:28.096
Целевая функция стремится к минимуму.

00:54:28.495 --> 00:54:34.929
Задана система ограничений: 31 + 2 X2 + 10
X-3 — больше либо равна 80.

00:54:35.688 --> 00:54:42.162
Вторая система ограничений: X1 + 6 X2 +
X-3 + 13—X4 больше либо равна сорока.

00:54:42.900 --> 00:54:48.226
В данном случае интерпретацию на плоскости
можно дать, если число ограничений в

00:54:48.306 --> 00:54:50.028
системе не превышает двух.

00:54:50.228 --> 00:54:53.953
Отложим в системе координат шкалы
ограничений.

00:54:54.513 --> 00:54:55.995
Показано на рисунке.

00:54:56.436 --> 00:54:59.279
Итак, ноль 108.

00:54:59.848 --> 00:55:02.329
Ноль, один, десять, сорок.

00:55:03.889 --> 00:55:06.089
Строим векторы в данном случае

00:55:13.610 --> 00:55:16.850
ограничения позволяют задать допустимую
область решений.

00:55:18.445 --> 00:55:22.767
Естественно, так как требуется достигнуть
данного ограничения с минимальными

00:55:22.887 --> 00:55:28.131
потерями. Нас интересует оптимальное
решение, что обеспечивает кратчайший путь

00:55:28.291 --> 00:55:31.613
между точками 0 иль штрих.

00:55:31.773 --> 00:55:33.974
Следует привести вектор 0,0 штрих.

00:55:34.465 --> 00:55:37.702
Достающий кратчайший путь к области
допустимых решений.

00:55:38.101 --> 00:55:42.217
Каждое возможное решение, задаваемое
системой ограничений, также можно

00:55:42.457 --> 00:55:45.254
представить собственным вектором на
плоскости.

00:55:45.294 --> 00:55:51.008
В частности, если принять X1 равное
единице; X3 — равное 3, gк-1

00:55:51.840 --> 00:55:55.920
Смотрим исходную задачу, ему будет
соответствовать вектор X-1.

00:55:56.080 --> 00:55:59.399
Соответственно, получаем все остальные
векторы.

00:55:59.879 --> 00:56:05.478
Очевидно, что для заданных ограничений
лучшим был бы вектор или решение, которое

00:56:05.638 --> 00:56:08.317
позволяет продвигаться со скоростью

00:56:09.053 --> 00:56:14.168
Две первых или совпадающими по направлению
с идеальным вектором 000-стрих.

00:56:14.487 --> 00:56:21.121
Однако для заданной задачи необходимого
вектора нет, следовательно, возникает

00:56:21.241 --> 00:56:25.477
задача выбора оптимального решения, выбора
параметра РК.

00:56:25.945 --> 00:56:31.463
В уравнении пять. Так как вектор в общем
случае характеризуется двумя параметрами:

00:56:31.743 --> 00:56:36.982
длиной и направлением, в данном случае
величина угла между им и идеальным

00:56:37.062 --> 00:56:42.540
вектором 00, что с определёнными
оговорками можно свести к одному критерию

00:56:42.620 --> 00:56:42.900
выбора

00:56:43.519 --> 00:56:48.715
лучшего вектора по длине его проекции на
идеальный вектор 000х.

00:56:48.795 --> 00:56:54.549
Итак, по величине длины проекции можно
выбрать лучший вектор в данном шаге.

00:56:54.829 --> 00:57:00.104
В данном случае в качестве альфа-катера
предполагаем один отложенный вектор.

00:57:01.258 --> 00:57:06.057
Отложение выбранного лучшего вектора на
данном шаге, что означает присвоение

00:57:06.337 --> 00:57:11.256
соответствующей переменной их жито
значение 1 приближает нас к допустимой

00:57:11.336 --> 00:57:15.695
области решений. Следовательно, для
перехода к следующему шагу оптимизации

00:57:16.335 --> 00:57:19.534
следует перенести начало системы
координат, направление

00:57:20.168 --> 00:57:22.690
...и на величину выбранного лучшего
вектора.

00:57:23.011 --> 00:57:28.094
Соответственно, строится и новый идеальный
вектор, учитывающий достижение заданных

00:57:28.215 --> 00:57:30.336
ограничений на предыдущих этапах.

00:57:30.736 --> 00:57:35.500
В новой системе опять откладываются
исходные векторы и вновь выбирается лучший

00:57:35.540 --> 00:57:35.940
вектор...

00:57:36.668 --> 00:57:42.630
Данная процедура выполняется до тех пор,
пока последний лучший из отложенных

00:57:42.750 --> 00:57:47.952
векторов не пересечёт допустимую область
решений.

00:57:48.232 --> 00:57:52.714
Совокупность отложенных векторов на всех
этапах определяет оптимальный план или

00:57:52.914 --> 00:57:53.834
оптимальное решение.

00:57:57.289 --> 00:58:00.767
Оптимальное решение целочисленной задачи.

00:58:01.087 --> 00:58:04.925
Посмотрим ещё раз на наш рисунок.

00:58:05.885 --> 00:58:08.804
То есть мы стремимся к идеальному вектору.

00:58:09.083 --> 00:58:12.562
То есть откладываем мы, откладываем один
вектор, второй

00:58:14.417 --> 00:58:18.697
И приближаемся к идеальному вектору 0.

00:58:24.017 --> 00:58:25.977
Подходы к точному решению задачи.

00:58:26.097 --> 00:58:29.457
Первый — метод последовательных
приближений.

00:58:30.172 --> 00:58:34.931
Идея метода состоит в том, что на первом
шаге задачи решаются целочисленно,

00:58:34.971 --> 00:58:39.489
откладываются полные вектора при
пересечении последним отложенным вектором

00:58:39.609 --> 00:58:45.287
допустимой области решения Unce процесс
приближения к оптимальному точному

00:58:45.407 --> 00:58:45.887
решению.

00:58:46.463 --> 00:58:50.662
Каждый этап этого приближения состоит в
следующем: изменяется исходная система

00:58:50.742 --> 00:58:56.621
координат: с первого квадрата на третий,
со второго на четвёртый с первого на

00:58:56.741 --> 00:58:58.741
третий, со второго на четвёртый.

00:59:00.381 --> 00:59:02.140
Из точки пересечения последнего

00:59:02.882 --> 00:59:09.757
Сложенного вектора допустимой области
решений Формируем идеальный

00:59:09.957 --> 00:59:13.914
вектор, относительно которого теперь
выбирается лучший вектор.

00:59:14.154 --> 00:59:18.551
Векторы вариантов изменяются направления
на противоположные, и мы начинаем

00:59:18.631 --> 00:59:20.150
рассматривать некоторые их части.

00:59:20.932 --> 00:59:24.490
Длина векторов умножается на коэффициенты
меньше единицы.

00:59:24.729 --> 00:59:29.486
Процедура повторяется до тех пор, пока
последний отложенный вектор часть вектора

00:59:29.646 --> 00:59:33.163
не достигается точки ноль с двумя
звёздочками.

00:59:38.599 --> 00:59:39.639
Обратите внимание.

00:59:40.300 --> 00:59:46.263
Вектор 0 штрих либо 0 со звёздочкой, ноль
два штриха, либо 0 с двумя звёздочками.

00:59:46.863 --> 00:59:52.506
Вот у нас система координат задан вектор и
прямая.

00:59:53.266 --> 00:59:54.907
Метод точного решения.

00:59:56.548 --> 00:59:58.148
Точное решение задачи дали

00:59:58.846 --> 01:00:04.445
Данный альтернативный подход предполагает
отложение на каждом шаге не целиком, а

01:00:04.485 --> 01:00:08.364
лишь часть векторов. Данная часть
выбирается из следующих соображений.

01:00:08.444 --> 01:00:13.883
Предположив, что после отложенного вектора
следующим лучшим становится другой вектор,

01:00:13.963 --> 01:00:15.483
всегда можно определить ту часть.

01:00:15.968 --> 01:00:19.527
Первого вектора, который задаёт лучшее
направление продвижения в сторону

01:00:19.687 --> 01:00:20.887
исходного вектора.

01:00:21.127 --> 01:00:23.766
Именно эта часть, а не целиком вектор.

01:00:23.926 --> 01:00:27.525
Искомая часть вектора может быть
определена следующим образом.

01:00:27.805 --> 01:00:31.924
Если из конца искомой части лучшего
вектора отложить идеальный

01:00:32.995 --> 01:00:37.116
То отложенные из него первый и второй
лучшие векторов будут иметь равную длину

01:00:37.356 --> 01:00:40.477
проекций на вновь отложенный идеальный
вектор.

01:00:41.838 --> 01:00:46.119
Данный подход уже трудно отнести к
методам, ориентированным на ЭВМ, так как

01:00:46.279 --> 01:00:48.640
параметр альфа-кате соответственно
посредством

01:00:51.703 --> 01:00:57.861
Что мы с вами проговаривали проекции
первого вектора, второго, и мы стремимся к

01:00:57.901 --> 01:00:59.501
идеальному вектору.

01:01:01.821 --> 01:01:05.260
Формализация решения задачи векторным
методом.

01:01:06.180 --> 01:01:10.379
Как отмечали, критерии выбора решений на
каждом этапе определяется двумя

01:01:10.459 --> 01:01:11.018
параметрами.

01:01:12.010 --> 01:01:17.204
Длинный вектор решений и величина угла
вектора решений с идеальным вектором Н,

01:01:17.244 --> 01:01:24.118
равная нулю. Соответственно, свести задачу
к однокритериальной

01:01:24.198 --> 01:01:27.634
можно, рассматривая длину проекции вектора
решения на идеальный.

01:01:31.146 --> 01:01:37.189
Модуль N равен x на косинус альфа n.

01:01:37.710 --> 01:01:44.554
Если обозначить через X1 значение от
единицы до N пар параметры

01:01:44.634 --> 01:01:46.315
энного вектора, то длина вектора

01:01:46.748 --> 01:01:53.466
Равнок N равно сумме X квадрат N и в
степени одной второй.

01:01:57.505 --> 01:01:59.424
Систему следующим образом.

01:02:04.105 --> 01:02:07.023
Вектор равен X1

01:02:11.381 --> 01:02:18.098
и от единицы до Nim проекцию в
артонормированном

01:02:18.218 --> 01:02:18.738
базисе.

01:02:20.077 --> 01:02:21.518
Вот она у нас проекция.

01:02:22.398 --> 01:02:27.439
Замечание. Длина вектора и угол между
векторами определяется по следующим

01:02:27.519 --> 01:02:34.360
формулам: X N равно сумме, где M
изменяется от M малого до M большого, GM

01:02:34.760 --> 01:02:35.600
в степени одной второй

01:02:36.480 --> 01:02:43.162
Альфа равна R косинус в сумме M от единицы
до M большого M

01:02:43.722 --> 01:02:50.404
умножить на J умножить на сумму Ж в
квадрате и на сумму Ж в квадрате n

01:02:50.764 --> 01:02:51.965
в степени одной второй.

01:02:53.456 --> 01:02:57.412
Данное выражение после соответствующих
постановок предположение, что

01:02:57.532 --> 01:03:03.047
нормированное значение идеального вектора
равно единицель M равно единице,

01:03:03.127 --> 01:03:09.081
следовательно, ноль равно единице на
корень из N, умноженного на сумму

01:03:09.241 --> 01:03:10.240
ЖН.

01:03:12.031 --> 01:03:18.357
Так как значение M фиксировано для всех
вариантов решений, это значение можно

01:03:18.558 --> 01:03:22.601
опустить таким образом: в качестве
критерия выбора оптимального вектора на

01:03:22.762 --> 01:03:27.126
каждом шаге можно рассматривать параметр,
определяющий следующие выражение.

01:03:28.410 --> 01:03:35.092
Система 6 X нулевое равно

01:03:35.332 --> 01:03:42.174
сумме X NI При этом X равно отношению

01:03:45.342 --> 01:03:48.183
На X0 и T.

01:03:48.663 --> 01:03:53.984
Видим, что эти формулы просты, что
позволяют эффективно использовать данный

01:03:54.144 --> 01:03:58.504
метод решения задачи линейного
программирования с использованием

01:03:58.544 --> 01:03:59.945
вычислительных средств.

01:04:00.065 --> 01:04:03.425
Таким образом, методика выбора
оптимального решения сводится к

01:04:03.465 --> 01:04:04.025
следующему.

01:04:04.624 --> 01:04:10.070
На каждом шаге, используя критерий
шефшесть, выбираем следующее значение из

01:04:11.271 --> 01:04:14.474
X нулевое, которое стремится к максимуму.

01:04:14.875 --> 01:04:19.760
С учётом выбранного вектора, что
соответствует его откладыванию в системе

01:04:19.840 --> 01:04:20.440
координат.

01:04:20.797 --> 01:04:25.920
Изменяем систему ограничений, вычитаем из
ограничений соответствующие параметры

01:04:26.120 --> 01:04:29.642
векторов. Третье.

01:04:30.082 --> 01:04:34.805
Проверяем все полученные ограничения на
условие меньше либо равно нулю, если для

01:04:34.965 --> 01:04:37.927
всех ограничений оно выполняется, задача
решается.

01:04:38.331 --> 01:04:45.164
Если условие не выполняется, возвращаемся
к шагу один с перенормированием значений

01:04:45.404 --> 01:04:47.561
параметров. Пример.

01:04:48.600 --> 01:04:54.154
Вернёмся к задаче раскроя материалов,
рассмотренных ранее, где целевая функция у

01:04:54.194 --> 01:04:55.473
нас стремится к минимуму.

01:04:56.377 --> 01:04:58.297
Равну 80 и сорока.

01:04:58.457 --> 01:05:05.096
Способ у нас четыре способа: раскрой
первого типа 321, раскрой второго типа

01:05:05.296 --> 01:05:06.456
16913

01:05:12.215 --> 01:05:18.967
Ограничение: 3x1 + 2x2 + X3 больше либо
равно восьмидесяти; X1 +

01:05:19.127 --> 01:05:23.762
6: X2 + 9 X3 + 13 X4 — больше либо равно
40.

01:05:23.962 --> 01:05:27.238
Для иллюстрации выполняем несколько шагов
решения.

01:05:27.318 --> 01:05:27.917
Шаг первый.

01:05:28.830 --> 01:05:31.987
Считаем значение критерия для различных
вариантов.

01:05:32.707 --> 01:05:39.500
Ф равно единице

01:05:40.140 --> 01:05:44.496
умножить на единицу плюс 13 умножить на
одну вторую приблизительно

01:05:47.190 --> 01:05:48.950
1,4.

01:05:49.390 --> 01:05:54.748
F отблизительно 0,9.

01:05:56.468 --> 01:06:02.826
F от An 0,7 и четвёртая — фи от An у нас
приблизительно

01:06:02.946 --> 01:06:04.306
0,5.

01:06:09.938 --> 01:06:16.383
Так. И на рисунке у нас по оси Апец 80
единиц отложено, по оси ординат — 40

01:06:16.623 --> 01:06:23.069
единиц. Далее коэффициенты 1, 2, 3

01:06:25.231 --> 01:06:28.673
отложены по осе ЦС 1,6,9, 13.

01:06:29.715 --> 01:06:34.517
По оси ординат. То есть раскрой первого
типа у нас по оси абциз, раскрой второго

01:06:34.597 --> 01:06:36.278
типа по оси ординат.

01:06:36.758 --> 01:06:43.121
Ну и мы строим, соответственно, векторы,
четыре вектора и целевую

01:06:43.241 --> 01:06:50.044
функцию. Сравниваем, выбираем

01:06:50.164 --> 01:06:51.044
лучший вариант этого

01:06:53.178 --> 01:06:56.096
Варианта. Приравниваем икс один к единице.

01:06:57.335 --> 01:06:59.093
Формулируем новые ограничения.

01:06:59.173 --> 01:07:02.611
U1 равно 77, 2 39.

01:07:03.050 --> 01:07:06.888
Задача не решена, следовательно, требуется
следующий шаг решения.

01:07:07.127 --> 01:07:08.766
Не все ограничения нулевые.

01:07:08.886 --> 01:07:13.203
Следующий шаг отличается от предыдущего
тем, что в вадиативном критерии

01:07:13.363 --> 01:07:14.122
изменяется.

01:07:17.809 --> 01:07:24.328
Продолжаем перерасчёт, находим первое F1,
второе F2, третье F2 f2 и

01:07:24.448 --> 01:07:26.568
четвёртое F2 f2.

01:07:26.768 --> 01:07:30.687
То есть это уже мы рассмотрели двадцать
второй шаг и так далее.

01:07:31.127 --> 01:07:35.366
Выбираем лучшее значение по данному
критерию, фиксируем отложенный X

01:07:36.017 --> 01:07:40.856
Пересчитываем ограничения, проверяем,
решена ли задача полностью или требуется

01:07:41.016 --> 01:07:43.615
следующий шаг решения и так далее.

01:07:47.414 --> 01:07:49.573
Нормирование параметров в общем случае.

01:07:49.693 --> 01:07:52.652
В общем случае нормирование параметров
должно учитываться

01:07:55.059 --> 01:08:00.863
Первое — величину вектора относительно
векторов других сравниваемых вариантов или

01:08:01.143 --> 01:08:04.145
насколько велик шаг в сторону ограничения.

01:08:04.265 --> 01:08:08.468
Будет ли откладывание данного вектора?

01:08:08.588 --> 01:08:14.273
Второе — отношение ограничений между собой
или в какой мере следует продвигаться при

01:08:14.393 --> 01:08:15.593
откладывании векторов?

01:08:16.007 --> 01:08:17.447
Конкретному ограничению.

01:08:17.727 --> 01:08:22.048
Третье — учёт отношения влияния выбранного
решения по отношению к остальным на

01:08:22.128 --> 01:08:23.369
целевую функцию.

01:08:24.289 --> 01:08:26.210
Нормирование значения.

01:08:26.850 --> 01:08:31.291
Нормированное значение параметров задаётся
объективным способом нормирования по

01:08:31.371 --> 01:08:32.412
следующим условиям.

01:08:33.122 --> 01:08:39.994
Вектор QN равно отношению QN относится 0,
где 0

01:08:41.233 --> 01:08:47.905
— это верхняя точечная граница, то есть

01:08:48.025 --> 01:08:48.584
максимум.

01:08:49.130 --> 01:08:55.658
Учёт отношения ограничений осуществляется
внесением весового элемента,

01:08:55.698 --> 01:09:01.344
определяемого по формуле Betta M равно Н
относится Q степень

01:09:02.065 --> 01:09:04.868
максимальная, где Q максимальная.

01:09:05.708 --> 01:09:07.830
Также верхнее точечное значение.

01:09:07.910 --> 01:09:14.315
Таким образом, выбор лучшего решения на
каждом этапе выполняется по формуле F от A

01:09:15.516 --> 01:09:20.801
равно сумме Q относится U умноженное

01:09:21.824 --> 01:09:25.705
На ку большое M и ку максимальное M.

01:09:25.986 --> 01:09:30.428
Для того чтобы учесть, насколько выбранное
решение влияет на целевую функцию при

01:09:30.508 --> 01:09:34.830
условии, что она минимизируется, в
критерии для варианта Н следует ввести

01:09:35.030 --> 01:09:36.751
коэффициент гамма Н.

01:09:36.951 --> 01:09:37.551
Тогда получим

01:09:38.570 --> 01:09:45.448
Следующее значение A N равно гамма
умножить на сумму ку малое N

01:09:45.968 --> 01:09:52.646
на Q малое M умножить на K большое N
относится к ку максимальному M, где гамма

01:09:52.806 --> 01:09:53.365
Н равно

01:09:54.072 --> 01:10:00.748
C минимальное N на C, Ц минимальное — это
есть Infinitutum,

01:10:00.828 --> 01:10:07.705
Infinitu. Эта формула является основной
расчётной формулой при выборе оптимального

01:10:07.865 --> 01:10:12.143
плана на каждом шаге при постановке задачи
в общем виде.

01:10:13.910 --> 01:10:20.665
Infinitie — это значит минимизируется
достоинства вектора метода

01:10:20.985 --> 01:10:26.421
решения основ основанного на векторной
интерпретации задачи линейного

01:10:26.580 --> 01:10:30.657
программирования. Кроме очевидной
наглядности, данная интерпретация

01:10:30.897 --> 01:10:33.015
позволяет, в отличие от Simplex метода

01:10:33.762 --> 01:10:38.045
Векторный метод позволяет минимизировать
число вычислений, так как критерий

01:10:38.125 --> 01:10:42.408
оптимальности позволяет на каждом шаге
наилучшим образом с точки зрения

01:10:42.608 --> 01:10:47.372
количества вычислений продвигаться в
сторону области допустимых решений.

01:10:47.933 --> 01:10:51.495
Минимальная вычислительная сложность на
каждом этапе выбора плана.

01:10:52.240 --> 01:10:54.802
Простейшие арифметические и логические
операции.

01:10:55.002 --> 01:10:59.566
Всё это обусловливает эффективность
применения метода для расчёта оптимизации

01:10:59.806 --> 01:11:02.688
задач на вычислительных машинах.

01:11:04.650 --> 01:11:07.452
Приоритетная задача линейного
программирования.

01:11:07.932 --> 01:11:11.335
Приоритетная задача состоит в том, что в
рамках заданных ограничений

01:11:11.535 --> 01:11:12.136
дополнительного

01:11:12.872 --> 01:11:15.754
Оговаривается порядок выполнения данных
ограничений.

01:11:16.035 --> 01:11:20.479
Возвращаемся к нашей, к нашему примеру
раскрою материалов, где заданы

01:11:20.599 --> 01:11:25.163
ограничения: не менее 80 деталей первого
типа и не менее 40.

01:11:25.524 --> 01:11:29.407
Может быть дополнительно введено,
например, следующее ограничение.

01:11:32.345 --> 01:11:37.107
В первую очередь необходимо провести не
менее 30 деталей первого типа и не менее

01:11:37.187 --> 01:11:43.550
двадцати второго. Во вторую очередь, э-э,
увеличиваем значение либо уменьшаем и так

01:11:43.670 --> 01:11:48.272
далее. То есть сводится некоторый
приоритет на очерёдность решаемых задач.

01:11:48.392 --> 01:11:51.393
При такой постановке задачи уже
действительно можно говорить об

01:11:51.513 --> 01:11:52.954
оптимальном планирования.

01:11:53.580 --> 01:11:57.503
Так как учитывается, соответственно,
последовательность выполнения работ.

01:11:57.903 --> 01:12:02.385
При использовании классического метода
решения задач линейного программирования

01:12:02.585 --> 01:12:08.669
симплекс-методов, не позволяющих учитывать
динамику плана, данная задача разбивается

01:12:08.829 --> 01:12:12.271
на соответствующую совокупность
невзаимосвязанных задач линейного

01:12:12.391 --> 01:12:12.991
программирования.

01:12:13.824 --> 01:12:16.421
Число задач определяется числом
приоритетов.

01:12:16.741 --> 01:12:20.696
Векторный метод реша решение задач
линейного программирования позволяет

01:12:20.776 --> 01:12:24.732
строить оптимальные планы с учётом
динамики выполнения работ.

01:12:25.251 --> 01:12:28.847
Рассмотрим, как решается приоритетная
задача линейного программирования.

01:12:29.630 --> 01:12:33.949
...векторным методом и в первую очередь,
как она интерпретируется.

01:12:34.229 --> 01:12:37.988
В общем случае приоритетная задача
линейного программирования в своей

01:12:38.068 --> 01:12:43.267
формальной постановке выглядит следующим
образом: пусть задано первое приоритетов

01:12:43.507 --> 01:12:45.586
на заданную область ограничения.

01:12:45.706 --> 01:12:48.945
Соответственно, имеем следующую систему
ограничений.

01:12:51.822 --> 01:12:53.983
Так задано в виде формул.

01:12:54.104 --> 01:12:59.507
При этом задаётся в первую очередь,
требуется выполнить что OM — ограничение.

01:12:59.627 --> 01:13:06.110
Постановка задачи имеет вид X такие, что
X, где M

01:13:06.630 --> 01:13:09.792
изменяется от 1 и от 1.

01:13:10.767 --> 01:13:17.734
Обращается в минимум целевая функция при
условии, что система ограничений будет

01:13:17.934 --> 01:13:24.782
больше либо равна Uит первое ограничение и
второе — ку

01:13:25.583 --> 01:13:27.545
больше либо равна QMITE.

01:13:29.397 --> 01:13:32.556
Причём сумма будет равна m.

01:13:34.715 --> 01:13:37.554
Векторная интерпретация задачи состоит в
следующем.

01:13:37.714 --> 01:13:42.713
Посмотрите на рисунок. На плоскости
появляется система допустимых решений.

01:13:49.377 --> 01:13:54.940
Допустимая область с меньшим порядковым
номером более приоритетна.

01:13:55.420 --> 01:13:58.702
Данные ограничения должны выполняться в
первую очередь.

01:13:58.862 --> 01:14:03.625
В каждой допустимой области должно быть
отложен идеальный вектор из начала

01:14:03.705 --> 01:14:07.988
координат в первую очередь, из вершины
предыдущей области в начало координат.

01:14:08.441 --> 01:14:13.116
Второй области. Итак, из вершины
предыдущей области опять же откладывается

01:14:13.236 --> 01:14:15.393
идеальный вектор во вторую область.

01:14:17.111 --> 01:14:22.346
Данная задача может решаться так, как так
же, как и в случае без приоритетной

01:14:22.466 --> 01:14:25.622
постановки путём выбора лучшего вектора на
каждом этапе.

01:14:26.282 --> 01:14:31.281
Однако существует два правила преодоления
области допустимых решений.

01:14:32.441 --> 01:14:36.440
Таким образом, данный подход может
позволить использовать возможности

01:14:36.640 --> 01:14:41.399
векторной интерпретации, возможность
поиска не только лучших решений,

01:14:42.084 --> 01:14:47.045
Плане, но и их очередность для решения
приоритетных задач, отличающихся своей

01:14:47.205 --> 01:14:54.087
постановкой заданием очередности
выполнения ограничений Постановка и

01:14:54.167 --> 01:14:59.608
метод решения задачи синтеза расписания,
векторная интерпретация задач.

01:15:00.195 --> 01:15:04.639
Большинство детерминированных задач в
прикладной области вычислительных систем

01:15:04.840 --> 01:15:06.641
сетей является линейными.

01:15:06.761 --> 01:15:12.087
Поэтому векторная интерпретация задач
здесь имеет достаточно большую общность.

01:15:12.728 --> 01:15:15.851
В частности, всегда, когда может быть
определено

01:15:18.848 --> 01:15:21.525
Некое желаемое или оптимальное решение.

01:15:21.804 --> 01:15:26.239
Могут быть определены исходные способы
решения, при необходимости задана область

01:15:26.359 --> 01:15:30.434
оптимальных решений. Применим данный
подход, рассмотрим его применение к

01:15:30.474 --> 01:15:33.630
задачам синтеза расписаний реального
времени.

01:15:33.909 --> 01:15:34.469
Рассматривая

01:15:35.115 --> 01:15:39.909
Детерминированная задача теории расписания
состоит в определении очередности передачи

01:15:40.029 --> 01:15:46.781
прав на занятие ресурса, минимизирующего
его производительность при выполнении

01:15:47.260 --> 01:15:48.139
ограничений реально

01:15:57.776 --> 01:16:02.984
...реального времени на время решения
различных задач.

01:16:03.184 --> 01:16:07.270
Задача должна быть гарантированно решена
на этот промежуток времени.

01:16:07.551 --> 01:16:09.994
В одной системе реального времени могут
быть...

01:16:22.011 --> 01:16:27.211
измерять скорость, температуру, плотность
чего-либо и так далее и тому подобное В

01:16:27.331 --> 01:16:33.771
этом случае использование бесприоритетного
режима обслуживания в реальном времени по

01:16:33.891 --> 01:16:36.851
очереди может оказаться неоптимальным

01:16:37.359 --> 01:16:41.841
Требующим большего увеличения
производительности общного ресурса.

01:16:42.161 --> 01:16:48.565
Требуется построить оптимальную для
конкретного приложения приоритетную

01:16:48.965 --> 01:16:51.967
дисциплину обслуживания реального времени.

01:16:52.287 --> 01:16:55.208
Рассмотрим интерпретацию постановки задачи
на ресурс.

01:16:58.773 --> 01:17:01.490
Реальное время один, реальное время два.

01:17:04.008 --> 01:17:10.762
По оси координат откладываются временные
характеристики задачи

01:17:11.322 --> 01:17:14.159
эмного типа, в частности ТМ.

01:17:15.458 --> 01:17:21.460
...и ограничение реального времени Т
большое M, которое...

01:17:41.856 --> 01:17:48.485
способов решения задачи при каждом весь
квант времени с учётом времени на выбор

01:17:48.604 --> 01:17:52.318
заявки из очереди Представляется заявка
одной из M очередей

01:18:08.368 --> 01:18:12.444
О1. Потом вектор ещё раз.

01:18:12.684 --> 01:18:17.560
О-о-о — вектор.

01:18:18.479 --> 01:18:22.435
В этом случае уже имеет смысл говорить не
о максимальной длине проекции, а о

01:18:22.555 --> 01:18:24.713
ведиальном векторе О-О-шрих.

01:18:25.378 --> 01:18:32.257
То есть мы должны найти идеальный вектор
О-шрих минимальный, что и

01:18:32.337 --> 01:18:38.096
реализует при откладывании векторов по
осям координат, так как целесообразно

01:18:38.176 --> 01:18:40.536
обслуживать максимальное число данных
заявок.

01:18:41.658 --> 01:18:47.255
за ограниченное время и о достижимости
ограничения T большое M по M осям

01:18:47.655 --> 01:18:52.453
Естественно при синтезе расписания в
первую очередь имеет смысл откладывать

01:18:52.573 --> 01:18:56.930
вектор в том энном направлении, которое
может быть получено

01:18:57.402 --> 01:19:02.157
Из условия в данном случае минимизации.

01:19:02.197 --> 01:19:07.232
То есть выбираем самое самое жёсткое
ограничение, которое должно быть выбрано

01:19:07.632 --> 01:19:08.950
за минимальное время.

01:19:09.310 --> 01:19:14.185
На рисунке вы его перечертите для того,
чтоб была более понятная была задача.

01:19:16.703 --> 01:19:18.022
Большое, равное одному.

01:19:18.222 --> 01:19:24.019
Предоставим ресурсы выбранной заявки на
фиксированное время занятия, задаваемое

01:19:24.179 --> 01:19:28.776
продолжительностью времени кванта, что на
рисунке соответствует отложению вектора

01:19:28.896 --> 01:19:30.215
ООО.

01:19:30.335 --> 01:19:33.253
Далее требуется сформулировать новую
систему координат.

01:19:33.656 --> 01:19:37.895
Особенностью её получения будет перенос
системы координат в направлении и на

01:19:37.975 --> 01:19:44.814
величину векторов, где i равно двум, что

01:19:45.014 --> 01:19:48.094
на рисунке соответствует переносу вектора
ОО-2.

01:19:49.534 --> 01:19:51.573
Задание для самостоятельной работы.

01:19:52.419 --> 01:19:56.502
Самостоятельная работа обучающихся
является одной из важнейших составляющих

01:19:56.582 --> 01:20:02.026
образовательного процесса, независимо от
направления подготовки и характера работы.

01:20:02.386 --> 01:20:06.429
Любой начинающий специалист должен
обладать фундаментальными знаниями,

01:20:06.709 --> 01:20:08.910
профессиональными умениями и навыками.

01:20:09.836 --> 01:20:14.431
деятельности своего профиля, опыт
творческой и исследовательской

01:20:14.591 --> 01:20:16.948
деятельности по решению новых проблем.

01:20:17.428 --> 01:20:21.703
Самостоятельная работа определяется как
индивидуальная или коллективная учебная

01:20:21.863 --> 01:20:24.860
деятельность, осуществляемая обучающимися

01:20:26.159 --> 01:20:30.481
Самостоятельно по заданиям преподавателя и
под его контролем.

01:20:32.082 --> 01:20:37.686
Необходимо для самостоятельной работы
ответить на следующие вопросы: какие виды

01:20:37.806 --> 01:20:40.648
финансовых задач можно решать векторным
методом?

01:20:41.208 --> 01:20:45.050
Какие задачи включает в себя метод
линейного программирования?

01:20:45.868 --> 01:20:48.986
Нормирование параметров в общем случае.

01:20:49.106 --> 01:20:53.502
Как интегрировать задачу линейного
программирования и что означает

01:20:54.021 --> 01:20:57.059
положительность временного кванта.

01:20:59.097 --> 01:21:03.213
Вам предлагается перечень основной и
дополнительной учебной литературы,

01:21:03.293 --> 01:21:05.971
необходимой для освоения данной
дисциплины.

01:21:06.291 --> 01:21:07.450
Спасибо за внимание.

