WEBVTT

00:00:08.093 --> 00:00:13.088
Итак, эээ данная тема посвящена, мы с вами
говорили в прошлый раз, что математическое

00:00:13.248 --> 00:00:17.924
моделирование в финансовой математике
включает в себя прямую, двойственную

00:00:18.044 --> 00:00:22.001
задачи линейного программирования:
Simprex-метод, транспортные задачи и так

00:00:22.160 --> 00:00:23.479
далее. Итак

00:00:24.637 --> 00:00:28.554
Сегодня мы с вами рассмотрим прямую
двойственную задачу финансовой математики

00:00:28.674 --> 00:00:29.953
их решения.

00:00:35.030 --> 00:00:38.787
Решение экономической задачи симплекс
методом.

00:00:39.826 --> 00:00:45.703
Для изготовления различных изделий AB и C
предприятие использует три различных вида

00:00:45.783 --> 00:00:46.262
сырья.

00:00:46.922 --> 00:00:51.287
Нормы расхода, цена и общее количество
сырья даны в таблице.

00:00:51.607 --> 00:00:54.169
Итак, три вида сырья в данном случае.

00:00:55.130 --> 00:00:58.614
Нормы и запас сырья в килограммах А-Б.

00:00:59.575 --> 00:01:04.380
Общее количество сырья — 360, 192 и 180
единиц.

00:01:04.911 --> 00:01:08.351
Цена одного изделия в денежных единицах.

00:01:09.112 --> 00:01:14.512
Изделия могут производиться в любых
соотношениях, сбыт обеспечен, но

00:01:14.592 --> 00:01:18.273
производство ограничено выделенным сырьём.

00:01:18.753 --> 00:01:22.193
Необходимо составить план производства,
при котором общая стоимость всех

00:01:23.204 --> 00:01:25.926
Э-э произведённой продукции является
максимальной.

00:01:26.166 --> 00:01:31.851
Итак, я вам даю несколько минут для того,
чтобы вы смогли перечертить данную

00:01:32.251 --> 00:01:34.853
таблицу, чтобы перейти к её решению.

00:01:36.735 --> 00:01:40.297
Ещё раз повторюсь, данную таблицу
необходимо перечертить для того, чтобы

00:01:40.458 --> 00:01:41.618
было понятно решение.

00:01:42.000 --> 00:01:44.521
Данной задачи симплекс методом.

00:05:03.062 --> 00:05:07.781
Итак, я вам дала несколько минут, чтобы вы
записали таблицу для решения данной

00:05:07.901 --> 00:05:11.701
задачи. Итак, решение.

00:05:13.700 --> 00:05:18.220
Э-э, составим систему ограничений для
того, чтобы найти максимум функции.

00:05:19.032 --> 00:05:25.918
F — это целевая функция, она равна 9 X1 +
10 X 2 + 16 X 3.

00:05:26.278 --> 00:05:29.041
Также дано дана система ограничений.

00:05:30.522 --> 00:05:35.607
Первое неравенство — 18 X1 + 15 X 2 + 12
X-3.

00:05:36.328 --> 00:05:43.163
меньше либо равно трём шестидесяти; Второе
ограничение: 61 + 4x2 +7

00:05:43.283 --> 00:05:45.881
X-3 меньше либо равно 192.

00:05:46.240 --> 00:05:52.955
И третье: 5-1 + 3 + 3 меньше либо равно
180.

00:05:53.609 --> 00:05:58.254
При этом обязательное условие у нас, что
X1—X2.3 больше либо равно нулю.

00:05:58.575 --> 00:06:03.901
Систему ограничений также предлагаю вам
записать для решения данной задачи.

00:06:04.142 --> 00:06:05.503
Даю вам 2—3 минуты.

00:06:53.964 --> 00:06:58.845
Итак, мы с вами записали основную таблицу.

00:06:59.005 --> 00:07:05.486
Теперь мне необходимо записать систему
ограничений, так как мы продолжаем

00:07:05.607 --> 00:07:11.408
изучать финансовую математику и в данном
случае это у нас Simplex-метод решения

00:07:11.568 --> 00:07:11.968
задач.

00:07:12.870 --> 00:07:19.824
Связанные с финансовой математикой и с
математическим моделированием,

00:07:19.904 --> 00:07:22.421
которое мы прошли на прошлой лекции.

00:07:23.740 --> 00:07:26.578
Сегодня мы разбираем решение задач.

00:07:27.417 --> 00:07:29.455
Даю несколько минут, чтобы вы смогли

00:07:31.680 --> 00:07:33.720
Переписать данную систему ограничений

00:10:39.785 --> 00:10:42.945
Итак, надеюсь, вы переписали систему
ограничений и пошли дальше.

00:10:43.344 --> 00:10:46.624
Теперь данную задачу запишем в форме
основной задачи линейного

00:10:46.784 --> 00:10:52.422
программирования. Для этого нам необходимо
ввести дополнительные переменные по числу

00:10:52.502 --> 00:10:56.901
ограничений. У нас было три ограничения,
как обратили во внимание в предыдущем.

00:10:58.854 --> 00:11:04.168
Э-э, в этом случае ограничения у нас тоже
три, но уже ставим знак равно.

00:11:04.248 --> 00:11:08.803
При этом вводим новые дополнительные
переменные: X4, X5, X6.

00:11:09.043 --> 00:11:11.999
При этом у нас переменные не должны
повторяться.

00:11:12.599 --> 00:11:13.877
То есть та же самая.

00:11:14.814 --> 00:11:19.218
Система, но теперь в данном случае не
ограничений, а система равенств.

00:11:19.658 --> 00:11:26.024
То есть получается 18 X1 + 15 X2 + 12 X 3
+ X 4

00:11:26.625 --> 00:11:28.466
равно 360.

00:11:28.667 --> 00:11:33.751
Второе равенство: 61 + 4 X 2 + 8 X 3 + X.

00:11:33.791 --> 00:11:35.273
Обратите внимание, что переменные

00:11:35.979 --> 00:11:39.621
В предыдущем было X4, теперь X5 равно 192.

00:11:39.822 --> 00:11:46.065
И, соответственно, в третье ограничение мы
добавляем переменную, со знаком

00:11:46.226 --> 00:11:51.829
X6, то есть 51 + 3x2 + 3x3 + X6 равно 180.

00:11:52.483 --> 00:11:57.560
Ну и обязательное условие сохраняется:
X1—X2.x 3 больше либо равно нулю.

00:11:59.519 --> 00:12:02.998
Теперь данную задачу мы запишем в
векторной форме.

00:12:04.517 --> 00:12:07.476
То есть, в данном случае

00:12:08.527 --> 00:12:15.329
Матрицы, столбцы 1, П2, П3, П4; П56,

00:12:15.809 --> 00:12:22.572
П4, П56 — это единичные матрицы и Пнулевое
— вектор-столбец

00:12:22.852 --> 00:12:24.933
с коэффициентами свободных членов.

00:12:25.053 --> 00:12:28.414
Также даю вам возможность записать,
несколько минут вам даю.

00:12:28.746 --> 00:12:30.996
Перепишите задачу в векторной форме.

00:12:54.690 --> 00:12:57.892
Итак, запишите задачу в векторной форме.

00:13:03.095 --> 00:13:05.016
Для этого достаточно 2—3 минуты.

00:14:26.963 --> 00:14:30.562
В данном случае есть три единичных
вектора.

00:14:31.082 --> 00:14:37.760
Как я вам говорила до этого, посмотрите:
единичные вектора: П4, П5, П6.

00:14:37.880 --> 00:14:43.559
Почему они единичные? Потому что у нас
стоит в данном случае в векторе столбце

00:14:43.719 --> 00:14:45.118
единица и нули.

00:14:46.420 --> 00:14:48.140
Хотя бы одна единица.

00:14:49.181 --> 00:14:56.143
При этом X тогда равен вектор три

00:14:56.343 --> 00:14:59.904
нуля 360, 192, 180.

00:15:00.384 --> 00:15:00.864
И вот для

00:15:02.400 --> 00:15:06.956
В данной задаче мы составим нулевую
симплекс-таблицу.

00:15:08.195 --> 00:15:10.273
Итак, таблица нулевая.

00:15:11.152 --> 00:15:17.546
При этом у нас дан первый столбик — это
количество

00:15:17.826 --> 00:15:18.305
строк.

00:15:18.567 --> 00:15:25.169
Четыре строки: базис p4, p5,p6, свободные
базисные переменные, план,

00:15:25.929 --> 00:15:32.892
который предположительно 360 единиц
товара, 192 единицы

00:15:33.012 --> 00:15:34.292
и 180 единиц.

00:15:35.216 --> 00:15:40.371
И затем, э-э, то, что у нас было, обратите
внимание в начале.

00:15:40.610 --> 00:15:43.647
Давайте вернёмся быстренько к задачи.

00:15:43.847 --> 00:15:49.361
Для изготовления различных изделий А-Б
предприятие использует три различных вида

00:15:49.441 --> 00:15:52.718
сырья, нормы расхода, цена и общее
количество сырья, данные

00:15:53.272 --> 00:15:56.193
Даны в таблице. Эту таблицу вы переписали.

00:15:56.553 --> 00:16:01.915
Далее, изделия могут производиться в любых
соотношениях, но производство ограничено

00:16:02.275 --> 00:16:03.555
выделенным сырьём.

00:16:03.795 --> 00:16:08.076
Сырьё — это 360 единиц, 192 и 180 единиц.

00:16:08.436 --> 00:16:11.597
И необходимо составить план производства,
при котором общая стоимость

00:16:12.237 --> 00:16:14.438
производственной продукции является
максимальной.

00:16:14.929 --> 00:16:21.082
Мы с вами записали эту таблицу, затем
систему ограничений ввели новые переменные

00:16:21.601 --> 00:16:27.394
для решения данной таблицы, записали
задачу в векторной форме и далее

00:16:27.634 --> 00:16:29.352
составляем ноль-таблицу.

00:16:29.591 --> 00:16:31.509
Даю вам опять же несколько минут.

00:16:32.175 --> 00:16:38.583
Для того чтобы вы смогли переписать эту
таблицу, э-э, для та- для чего это нужно

00:16:38.783 --> 00:16:43.468
переписывать? Для того чтобы в дальнейшем
могли понять, что мы будем, каким образом

00:16:43.589 --> 00:16:45.110
будет происходить решение.

00:20:53.327 --> 00:20:57.772
Итак, надеюсь, вы таблицу переписали, лишь
бы сфотографировали, чтобы мы могли де-е-э

00:20:57.932 --> 00:20:59.213
в дальнейшем действовать.

00:20:59.574 --> 00:21:04.139
Обратите внимание, подчёркнуто число 8 и
число 60.

00:21:04.259 --> 00:21:10.746
Пошли дальше. Полученный опорный план
проверяем на оптимальность.

00:21:11.423 --> 00:21:13.662
Вычисляем значение целевой функции.

00:21:14.621 --> 00:21:18.260
В данном случае у нас умножить на P
нулевое.

00:21:18.579 --> 00:21:23.577
Так как предприятие ещё не стало работать,
то целевая функция у нас равна нулю.

00:21:25.416 --> 00:21:30.454
При этом даны у нас Дельта 1 и дельта 2 —
это -9 -10.

00:21:30.654 --> 00:21:31.373
Вернёмся.

00:21:32.573 --> 00:21:35.652
Минус девять, минус 10 из таблицы.

00:21:36.892 --> 00:21:39.811
И у нас пока, смотрите, нулевое значение.

00:21:39.931 --> 00:21:43.930
То есть целевая функция равна нулю.

00:21:47.128 --> 00:21:48.728
Как видно, из нулевой таблицы

00:21:49.898 --> 00:21:54.739
Отличными от нуля являются переменные
X4.5.6.

00:21:55.059 --> 00:21:58.539
А переменные X1.X2.3 равны нулю.

00:21:58.899 --> 00:22:03.980
Так как они не базисные, а свободные
дополнительные же переменные X4.56

00:22:04.420 --> 00:22:07.260
принимают свои значения в соответствии с
ограничениями.

00:22:08.747 --> 00:22:13.867
Эти значения переменных отвечают такому
плану, при котором ничего не производится

00:22:14.147 --> 00:22:19.866
пока в данном случае, сырьё не
используется, только заверители продукции,

00:22:19.946 --> 00:22:23.825
так получается у нас, и значение целевой
функции равно нулю.

00:22:24.065 --> 00:22:27.825
То есть стоимость произведённой продукции
пока отсутствует в данном случае.

00:22:28.559 --> 00:22:31.081
Такой план, конечно, не является
оптимальным.

00:22:31.361 --> 00:22:36.125
Это видно из четвёртой строки таблицы, в
которой имеется три отрицательных оценки:

00:22:36.205 --> 00:22:38.527
минус 9, -6, - 10.

00:22:38.647 --> 00:22:40.288
Обратите внимание ещё раз.

00:22:41.369 --> 00:22:44.812
То есть мы будем решать симплекс-таблицу
до тех пор, пока у нас не будет

00:22:45.012 --> 00:22:49.015
отрицательных оценок: -9, - 10, -16.

00:22:51.981 --> 00:22:55.943
Отрицательные числа не только
свидетельствуют о возможности увеличения

00:22:56.103 --> 00:23:02.146
общей стоимости производимой продукции в
столбцах над отрицательными оценками.

00:23:03.146 --> 00:23:09.229
Стоят положительные числа, но и
показывают, насколько увеличится эта сумма

00:23:09.349 --> 00:23:11.390
при введении в план единицы того,

00:23:11.560 --> 00:23:13.359
...или иного вида продукции.

00:23:13.839 --> 00:23:18.917
Так, число -9 означает, что при включении
в план производства одного изделия A

00:23:19.756 --> 00:23:24.634
обеспечивается увеличение стоимости
продукции на девять денежных единиц.

00:23:27.112 --> 00:23:31.550
Если включить в план производства по
одному изделию B, то общая стоимость

00:23:33.027 --> 00:23:37.671
продукции возрастает, соответственно, на
10 и 16 денежных единиц.

00:23:38.031 --> 00:23:42.315
Поэтому, с экономической точки зрения
целесообразным является включить в план

00:23:42.475 --> 00:23:43.676
изделия Ц.

00:23:44.396 --> 00:23:49.320
Это же необходимо сделать и с той точки
зрения, что -16 является наименьшей

00:23:49.400 --> 00:23:52.803
отрицательной оценкой, значит, в базис
введём вектор B3.

00:23:54.885 --> 00:23:57.042
Итак, найдём ку минимальное значение.

00:23:57.122 --> 00:24:03.795
Это берётся отношение чисел, стоящих в
столбце свободных членов, если обратите

00:24:03.875 --> 00:24:07.871
внимание, в нулевой таблице и делим на
соответствующие коэффициенты, стоящие в

00:24:07.911 --> 00:24:11.707
столбике -16.

00:24:13.572 --> 00:24:14.850
Ещё раз вернусь.

00:24:15.769 --> 00:24:22.363
То есть делим 360 на 12, 192 на 8 и 180 на
3.

00:24:22.603 --> 00:24:29.037
Берём в Z-строке в целевой функции число
по модулю максимальное — это

00:24:29.117 --> 00:24:30.276
-16.

00:24:33.326 --> 00:24:37.726
И полу- и находим минимальное значение 30,
24 и 60.

00:24:38.446 --> 00:24:41.967
Минимальное значение в данном случае
получается 24.

00:24:42.367 --> 00:24:49.287
Введём его в последний столбец таблицы,
число 24 соответствует вектору p5, 192

00:24:49.767 --> 00:24:53.528
разделить на 8. 24 с экономической точки
зрения означает

00:24:54.173 --> 00:24:59.613
Какое количество изделий Ц предприятие
может изготовлять с учётом норм расхода и

00:24:59.773 --> 00:25:02.933
имеющихся объёмов сырья каждого вида?

00:25:04.813 --> 00:25:11.413
Так как сырья каждого вида имеется,
соответственно, 360, 192 и 180 кг

00:25:12.297 --> 00:25:17.974
А на одно изделие Ц требуется затратить
сырья каждого вида, соответственно, 12—8,3

00:25:18.174 --> 00:25:22.652
кг. То максимальное число изделий Ц,
которое может быть изготовлено

00:25:22.772 --> 00:25:26.131
предприятием, равно минимуму 24.

00:25:26.331 --> 00:25:29.050
То есть ограничивающим фактором

00:25:29.627 --> 00:25:34.269
Для производства изделий Ц является
имеющийся объём сырья второго вида.

00:25:34.549 --> 00:25:39.231
С учётом его, предприятие может
производить 24 изделия Ц.

00:25:39.631 --> 00:25:44.313
При этом сырьё второго вида будет
полностью использовано, а значит, вектор 5

00:25:45.186 --> 00:25:47.504
Подлежит исключению из базиса.

00:25:49.222 --> 00:25:51.540
И вот теперь мы составим следующую
таблицу.

00:25:51.700 --> 00:25:57.575
В ней разрешающей является вторая строка,
а разрешающим столбец третий.

00:25:57.854 --> 00:26:00.292
На их пересечении стоит элемент восемь.

00:26:00.612 --> 00:26:05.527
Разделим вторую строку на восемь, а затем
обнулим по методу Жардана Гауса

00:26:06.297 --> 00:26:13.143
или по формулам треугольника третий
столбец Итак, теперь появляется перед

00:26:13.223 --> 00:26:15.305
вашими глазами таблица 1.

00:26:15.705 --> 00:26:21.870
Также прошу её либо сфотографировать её,
либо перепишите, даю несколько минут.

00:26:22.699 --> 00:26:27.905
Здесь мы умножаем вторую строку на минус
12 и прибавили к первой, а затем умножили

00:26:27.945 --> 00:26:30.908
вторую строку на -3 и прибавили к третьей
строке.

00:26:31.269 --> 00:26:34.232
И мы получили новый опорный план — X.

00:26:35.753 --> 00:26:39.758
равно нулю, X второе равно нулю, и X
третье равно 24 уже.

00:26:40.587 --> 00:26:42.465
Ик четвёртая 72.

00:26:42.665 --> 00:26:48.021
То есть получается, у нас осталось 72
единицы, 72 кг продукции первого вида, 0

00:26:48.221 --> 00:26:53.177
кг продукции второго и 108 кг продукции
третьего вида.

00:26:53.696 --> 00:26:58.253
И значение целевой функции у нас уже
увеличилось, то есть мы получили первую

00:26:58.413 --> 00:27:01.250
прибыль, она равна 384 единице.

00:27:01.916 --> 00:27:08.422
Даю вам несколько минут, чтобы вы смогли
записать данную таблицу.

00:31:43.145 --> 00:31:45.868
Итак, продолжаем решение.

00:31:48.470 --> 00:31:53.395
В данном случае мы посчитаем синплекс
разности и заполним четвёртую строку

00:31:53.515 --> 00:31:54.156
таблицы.

00:31:54.776 --> 00:31:58.774
То есть сейчас идёт пояснение таблицы
номер один.

00:31:59.654 --> 00:32:05.451
При данном плане производства
изготавливается 24 изделия Ц и остаётся

00:32:05.571 --> 00:32:11.048
неиспользованным 72 кг сырья первого, 18
кг сырья второго вида.

00:32:11.820 --> 00:32:14.101
Второй вид сырья использован полностью.

00:32:14.501 --> 00:32:16.742
Вы обратили внимание, что там стоит ноль.

00:32:17.142 --> 00:32:22.144
Стоимость всей продукции при этом плане
составляет 384 денежные единицы.

00:32:22.864 --> 00:32:26.826
Указанные числа записаны в столбце план.

00:32:27.492 --> 00:32:29.892
Это опять параметры задачи.

00:32:30.531 --> 00:32:34.290
Но в данном случае они претерпели
изменения, изменились и данные других

00:32:34.450 --> 00:32:38.729
столбцов, их экономическое содержание
стало ещё более сложным.

00:32:40.489 --> 00:32:43.488
И у нас имеется одна отрицательная оценка
— - два.

00:32:44.405 --> 00:32:50.250
Ещё раз вернусь. Обратите внимание, одна
отрицательная оценка, вот она, минус два.

00:32:53.532 --> 00:32:56.415
То есть, это говорит о том, что план можно
улучшить.

00:32:56.495 --> 00:33:00.458
Введём базис вектор P2 и вычислим опять же
минимальное отношение.

00:33:02.434 --> 00:33:06.113
Также я вернусь и покажу, как находится
минимальное отношение.

00:33:06.793 --> 00:33:13.591
Минус два — это у нас P2 столбец: 72 делим
на 9, 24 на 12 и 108 на 3

00:33:13.791 --> 00:33:17.350
вторых. На отрицательные оценки и на 0
делить нельзя.

00:33:18.230 --> 00:33:18.870
И у нас получается

00:33:20.193 --> 00:33:22.075
848 72.

00:33:22.155 --> 00:33:25.718
При этом находим минимальное отношение,
которое равно восьми.

00:33:26.078 --> 00:33:29.641
То есть мы выводим из базиса вектор p4.

00:33:31.322 --> 00:33:35.285
Разрешающим будет первая строка и второй
столбец.

00:33:35.846 --> 00:33:38.528
Разрешающий элемент 9 разделим на

00:33:39.396 --> 00:33:44.630
Девять первую строку, заполним первую
строку новой таблицы, затем обнулим второй

00:33:44.750 --> 00:33:50.584
столбец. Для этого умножим первую строчку
на -1 вторую и прибавим ко второй, а затем

00:33:50.624 --> 00:33:55.538
умножим на первую строку на минус три
вторых и прибавим к третьей строке.

00:33:56.597 --> 00:34:02.922
И теперь мы заполним таблицу 2, которую я
также предлагаю вам либо сфотографировать,

00:34:03.002 --> 00:34:05.725
либо переписать. Даю несколько минут.

00:34:06.005 --> 00:34:07.806
Что у нас получается в этой таблице?

00:34:07.927 --> 00:34:12.210
Обратите внимание, в четвёртой строке у
нас все коэффициенты положительные.

00:34:12.735 --> 00:34:14.858
Значит, полученный опорный план какой?

00:34:14.898 --> 00:34:19.703
X1 равен нулю, X28, X32.

00:34:20.143 --> 00:34:24.988
Оборудование первого вида использовано
полностью и второго, а третьего вида

00:34:25.869 --> 00:34:28.512
остаётся в количестве 96 единиц.

00:34:29.435 --> 00:34:33.158
И новое значение целевой функции у нас уже
400 единиц.

00:34:34.559 --> 00:34:38.522
Все оценки не отрицательны, значит,
прибыль у нас в данном случае составляет

00:34:38.602 --> 00:34:40.843
400 денежных единиц.

00:34:41.324 --> 00:34:44.286
Итак, опять же повторюсь, прошу вас
записать

00:34:45.597 --> 00:34:51.225
Данную таблицу даю несколько минут и
продолжим.

00:37:38.520 --> 00:37:42.443
Итак, я надеюсь, что вы успели запечатлеть
данную таблицу.

00:37:42.924 --> 00:37:47.407
Ещё раз повторюсь, что если вы не
успеваете перечертить её, записать ммм

00:37:47.487 --> 00:37:52.932
цифры необходимые при решении данной
задачи, которые, возможно, вам встретится

00:37:53.172 --> 00:37:53.813
на экзамене.

00:37:54.793 --> 00:37:56.873
Задавайте вопросы свои.

00:37:57.873 --> 00:38:02.713
Вот. И вы можете в любое время прослушать
эту лекцию и просмотреть ещё раз решение

00:38:02.953 --> 00:38:09.312
задачи. Итак, мы убеждаемся, что у нас
появляется синплекс разниц-разности.

00:38:09.312 --> 00:38:11.352
В данном случае дельта 1 равно пяти.

00:38:11.949 --> 00:38:18.829
Дельта 2, дельта 3 лю, то есть дельта —
это разность, как вы поняли, дельта 4,2,

00:38:18.909 --> 00:38:22.589
дельта 5,53, и дельта 6 также равна нулю.

00:38:23.869 --> 00:38:28.109
Оптимальным планом производства не
предусмотрен выпуск изделия A.

00:38:28.807 --> 00:38:33.571
Введение в план выпуска продукции вида A
привело бы к уменьшению указанной общей

00:38:33.771 --> 00:38:38.895
стоимости. Это видно из четвёртой строки
столбца, где числа 5 показывает, что при

00:38:39.055 --> 00:38:43.859
данном плане включение в него выпуска
единицы изделия A приводит лишь к

00:38:43.939 --> 00:38:46.781
уменьшению общей величины стоимости на
пять денежных

00:38:47.635 --> 00:38:54.283
единиц. Итак, план предусматривает выпуск
восьми изделий B и 20 изделий

00:38:54.363 --> 00:39:00.970
C. Сырьё вида 1,2 используется целиком, а
сырьё вида три неиспользованным

00:39:01.210 --> 00:39:04.373
остаётся в количестве 96 кг.

00:39:06.725 --> 00:39:11.124
Ну и теперь мы с вами рассмотрели прямую
задачу Simplex метода, а теперь переходим

00:39:11.204 --> 00:39:15.882
к двойственной задаче линейного
программирования, которую мы, о которой мы

00:39:16.162 --> 00:39:22.959
проговаривали на прошлой лекции при этом
рассматривали основные формулы составления

00:39:23.159 --> 00:39:24.678
прямой и двойственной задачи.

00:39:25.446 --> 00:39:26.766
Симплекс-методом.

00:39:27.925 --> 00:39:32.285
Каждой задаче линейного программирования
можно поставить в соответствие задачу,

00:39:32.325 --> 00:39:35.284
называемую двойственной к исходной задаче.

00:39:35.724 --> 00:39:38.963
Рассмотрим задачу об использовании
ресурсов.

00:39:39.163 --> 00:39:41.763
Предположим, что предприятие A производит
N

00:39:42.445 --> 00:39:48.288
Видов продукции. Величина выпуска каждого
определяется переменными X1.X и так далее

00:39:48.408 --> 00:39:54.331
XN. В производстве используются эммы
различных видов ресурсов, объём которых

00:39:54.491 --> 00:39:58.053
ограничен величинами B1, B2 и так далее
Bn.

00:40:03.476 --> 00:40:08.277
Известны нормы затрат каждого ресурса на
единицу каждого вида продукции, образующую

00:40:08.397 --> 00:40:09.717
матрицу A.

00:40:12.117 --> 00:40:17.838
А также стоимость единицы продукции
каждого вида Ц1, C2 и так далее ЦН.

00:40:18.479 --> 00:40:20.919
Требуется организовать производство так

00:40:21.730 --> 00:40:25.688
Чтобы предприятию А-А была обеспечена
максимальная прибыль.

00:40:27.967 --> 00:40:32.844
В данном случае задача сводится к
нахождению неотрицательных переменных X1,

00:40:32.884 --> 00:40:38.600
X2 и так далее XN, при которых расход
ресурсов не превышает заданного их

00:40:38.680 --> 00:40:41.279
количества, а стоимость всей продукции
достигает

00:40:41.655 --> 00:40:47.696
Максимума. В математической форме задача
записывается в следующем

00:40:47.776 --> 00:40:53.737
виде. Дана F — целевая функция, которая
стремится к максимуму и

00:40:53.937 --> 00:40:59.657
ограничение. В данном случае эту модель я
предлагаю опять же вам записать.

00:44:13.935 --> 00:44:16.854
Итак, мы с вами записали систему
ограничений.

00:44:18.773 --> 00:44:22.772
По этим же исходным данным может быть
сформулирована другая задача.

00:44:22.932 --> 00:44:28.931
Предположим, что предприятие Б решило
закупить все ресурсы, которыми располагает

00:44:29.051 --> 00:44:30.010
предприятие А.

00:44:30.709 --> 00:44:34.913
В этом случае предприятию Б необходимо
установить оптимальные цены на эти

00:44:35.114 --> 00:44:37.396
ресурсы, исходя из следующих условий.

00:44:37.797 --> 00:44:42.562
Первое — общая стоимость ресурсов для
предприятия Б должна быть минимальной.

00:44:42.922 --> 00:44:45.886
Второе — за каждый вид ресурса предприятию
А

00:44:46.577 --> 00:44:50.893
Надо уплатить не менее той суммы, которую
это предприятие может получить при

00:44:51.252 --> 00:44:56.087
переработке данного вида ресурса в готовую
продукцию.

00:44:58.165 --> 00:45:03.240
Если обозначить через переменные iгрек 1,
igrek 2 и так далее, igrek N цены

00:45:04.228 --> 00:45:09.347
По которым предприятие Б покупает ресурсы
у предприятия А, то задача сводится к

00:45:09.427 --> 00:45:14.265
следующему: найти такие значения
переменных: igreк 1, igrek 2 и так далее,

00:45:14.385 --> 00:45:20.224
iгрек N. При которых стоимость ресурсов,
расходуемых на единицу любого вида

00:45:20.304 --> 00:45:20.943
продукции.

00:45:21.200 --> 00:45:26.640
Не меньше прибыли, цены за эту единицу
продукции, а общая стоимость ресурсов

00:45:26.800 --> 00:45:33.400
достигает минимума То есть какова

00:45:33.560 --> 00:45:38.560
должна быть оценка единицы каждого из
ресурсов: Yek 1, igrek 2 и так далее, X

00:45:39.419 --> 00:45:44.575
Чтобы при заданных объёмах имеющихся
ресурсов Б иТ, при заданных стоимости

00:45:44.775 --> 00:45:51.290
Ц-жит единицы продукции и нормах расхода А
и ж минимизировать общую оценку

00:45:51.410 --> 00:45:53.009
затрат на всю продукцию.

00:45:53.089 --> 00:45:57.326
То есть мы должны получить минимальные
затраты на оценку продукции.

00:45:58.982 --> 00:46:05.782
И математическая модель двойственной
задачи записывается в следующем виде: F

00:46:06.062 --> 00:46:08.462
со звёздочкой будет стремиться к минимуму.

00:46:08.502 --> 00:46:12.262
В данном случае это целевая функция, и
заданы ограничения.

00:46:12.662 --> 00:46:17.503
Обратите внимание, в первоначальной модели
математической у нас было знак меньше либо

00:46:17.583 --> 00:46:17.823
равно

00:46:18.917 --> 00:46:20.875
В данном случае больше либо равно.

00:46:21.154 --> 00:46:28.106
Прошу записать эту модель задачи, чтобы в
дальнейшем мы смогли её также решить.

00:46:28.386 --> 00:46:33.619
При этом запомним, что у нас получилось в
прямой задаче Simplex метода 400 денежных

00:46:33.739 --> 00:46:34.778
единиц прибыли.

00:46:36.518 --> 00:46:38.716
Посмотрим, что получится в двойственной
задаче.

00:46:38.796 --> 00:46:42.992
Итак, предлагаю записать систему
ограничений для того, чтоб перейти можно

00:46:43.192 --> 00:46:44.430
было к следующему слайду.

00:49:56.687 --> 00:50:00.084
Итак, мы с вами записали систему
ограничений, пошли дальше.

00:50:00.844 --> 00:50:04.561
Каков же экономический смысл переменных в
двойственные задаче?

00:50:05.000 --> 00:50:08.717
Переменные gek и T — двойственные задачи в
литературе могут иметь

00:50:09.402 --> 00:50:15.968
Различные названия: учётные, неявные,
теневые, объективно

00:50:16.088 --> 00:50:20.212
обусловленные оценки, двойственные оценки
или цены ресурсов.

00:50:20.972 --> 00:50:24.936
Эти две задачи образуют пару
взаимно-двойственных задач.

00:50:25.343 --> 00:50:28.299
Любая из которых может рассматриваться как
исходная.

00:50:28.779 --> 00:50:34.692
Решение одной задачи даёт оптимальный план
производства продукции, а решение другой —

00:50:35.331 --> 00:50:39.846
оптимальную систему оценки сырья,
используемого для производства этой

00:50:40.046 --> 00:50:40.725
продукции.

00:50:43.258 --> 00:50:47.820
Двойственные задачи линейного
программирования называют симметричными,

00:50:48.101 --> 00:50:51.503
если они удовлетворяют следующим
свойствам.

00:50:52.383 --> 00:50:57.826
Первое, число переменных в двойственной
задаче равно числу ограничений исходной

00:50:57.946 --> 00:50:58.467
задачи.

00:50:59.009 --> 00:51:04.211
А число ограничений двойственной задачи
равно числу переменных в исходной.

00:51:04.412 --> 00:51:11.376
Второе. В одной задаче идёт в данном
случае целевая функция направлена на

00:51:11.416 --> 00:51:14.217
максимум, а в другой — на минимум.

00:51:14.945 --> 00:51:19.305
Третье. Коэффициенты при переменных в
целевой функции одной задачи являются

00:51:19.505 --> 00:51:23.546
свободными членами системы ограничений
другой задачи.

00:51:25.106 --> 00:51:29.707
Четвёртое. В каждой задаче система
ограничений задаётся в виде неравенства

00:51:30.470 --> 00:51:35.465
Причём, э-э, в задаче на отыскание
максимума все неравенства вида «меньше

00:51:35.625 --> 00:51:40.939
либо равно», а в задаче на отыскание
минимума все неравенства в виде больше

00:51:41.419 --> 00:51:43.057
либо равно. Пятое.

00:51:43.737 --> 00:51:47.973
Матрица коэффициентов системы ограничений
получается одна из другой путём

00:51:48.053 --> 00:51:49.092
транспонирования.

00:51:50.201 --> 00:51:53.003
Транспонирование — это замена строк
столбцами.

00:51:53.163 --> 00:51:55.285
То есть строчки переходят в столбцы.

00:51:55.725 --> 00:52:01.770
Шестое. Каждому ограничению одной задачи
соответствует переменная другой задачи.

00:52:02.130 --> 00:52:05.292
Номер переменной совпадает с номером
ограничения.

00:52:06.053 --> 00:52:07.574
Седьмое, условие.

00:52:08.540 --> 00:52:12.378
Неотрицательности переменных сохраняются в
обеих задачах.

00:52:15.417 --> 00:52:18.136
Решение симметричных двойственных задач.

00:52:19.096 --> 00:52:22.174
Итак, запишем первую теорему
двойственности.

00:52:22.734 --> 00:52:26.173
Если одна из двойственных задач имеет
оптимальное решение

00:52:27.090 --> 00:52:30.886
То оптимальное решение имеет и другая
задача.

00:52:31.085 --> 00:52:35.361
При этом значения целевых функций задач
равны между собой.

00:52:35.960 --> 00:52:40.475
Если целевая функция одной из задач не
ограничена, то другая задача вообще не

00:52:40.635 --> 00:52:41.634
имеет решения.

00:52:47.525 --> 00:52:50.684
Экономическое содержание первой теоремы
двойственности.

00:52:51.963 --> 00:52:58.680
Если задача определённая оптимального
плана, максимизирующего

00:52:58.840 --> 00:53:04.917
выпуск продукции, разрешима, то разрешима
задача определения оценок ресурсов.

00:53:05.430 --> 00:53:09.626
Причём цена продукции, полученного в
результате реализации оптимального плана,

00:53:09.706 --> 00:53:12.663
совпадает с суммарной оценкой ресурсов.

00:53:13.582 --> 00:53:19.137
Совпадение значений целевых функций для
соответствующих решений пары двойственных

00:53:19.217 --> 00:53:22.894
задач достаточно для того, чтобы эти
решения были оптимальными.

00:53:24.015 --> 00:53:29.057
Решая задачу линейного программирования
Simplex Metod'ом, мы одновременно решаем и

00:53:29.177 --> 00:53:31.577
исходную двойственную задачу.

00:53:34.618 --> 00:53:38.139
Метод одновременного решения пары
двойственных задач.

00:53:38.219 --> 00:53:42.340
Обратите внимание, исходная задача,
которую мы в начале лекции записали и

00:53:42.420 --> 00:53:45.141
ввели новую переменную, она стремится к
максимуму.

00:53:45.689 --> 00:53:50.446
Двойственная задача F со звёздочкой,
целевая функция стремится к минимуму.

00:53:50.606 --> 00:53:55.404
При этом опять же у нас не система
ограничений, а система равенств.

00:53:58.362 --> 00:54:02.360
Число переменных в задачах одинаково и
равно M + N.

00:54:03.412 --> 00:54:08.531
В исходной задаче базисными переменными
являются вспомогательные неотрицательные

00:54:08.771 --> 00:54:14.969
переменные: X+ X N+ 2; X N+ N и так далее.

00:54:15.209 --> 00:54:20.368
А в двойственной задаче — вспомогательные
неотрицательные переменные: X + 1, gek N +

00:54:20.488 --> 00:54:22.407
2 и так далее, X + N.

00:54:23.702 --> 00:54:28.018
Базисные переменной одной задачи
соответствуют свободные переменные другой

00:54:28.138 --> 00:54:31.975
задачи и наоборот. То есть идёт
транспонирование матриц.

00:54:34.293 --> 00:54:40.767
И в данном случае я предлагаю вам записать
эту таблицу, где показаны решения.

00:54:41.860 --> 00:54:45.464
Переменные исходных задачи, основные
переменные: X1.x2.

00:54:45.544 --> 00:54:51.592
XN, как переходит в дополнительные и
дополнительные, как переходят в основные:

00:54:51.632 --> 00:54:54.276
X-1, igrek 2 и так далее, грек N.

00:54:54.596 --> 00:54:57.079
И получаем переменные двойственные задачи.

00:54:57.429 --> 00:55:00.606
Итак, данную табличку также прошу вас
переписать.

00:57:49.628 --> 00:57:53.786
Мы с вами записали таблицу, как переменные
исходной задачи переходят к переменной

00:57:53.906 --> 00:57:55.266
двойственной задачи.

00:57:56.346 --> 00:57:59.544
При решении задач линейного
программирования табличным

00:57:59.664 --> 00:58:04.223
симплекс-методом решение двойственной
задачи содержится в последней строке

00:58:04.343 --> 00:58:06.102
таблицы: это дельта жита.

00:58:06.885 --> 00:58:11.086
Причём основные переменные двойственной
задачи содержатся в столбцах,

00:58:11.406 --> 00:58:14.848
соответствующих дополнительным переменным
исходной задачи.

00:58:15.248 --> 00:58:18.849
А дополнительные переменные двойственной
задачи содержатся в столбцах,

00:58:18.889 --> 00:58:24.051
соответствующих основным первоначальным
переменным исходной задачи.

00:58:26.405 --> 00:58:30.766
Пример. Продолжаем мы решать, сформулиров
модель задачи двойственных к задаче из

00:58:30.886 --> 00:58:35.768
примера два начала лекции: найти максимум
функции.

00:58:35.968 --> 00:58:40.450
В данном случае вы уже переписывали эту
систему ограничений, где целевая функция F

00:58:40.730 --> 00:58:44.651
равна 9.1 + 10 X 2 + 16 X 3

00:58:45.484 --> 00:58:49.964
И система ограничений, состоящая из трёх
уравнений.

00:58:50.124 --> 00:58:56.644
При этом запас сырья первого вида
составлял 360 кг, второго вида — 192 кг и

00:58:57.364 --> 00:58:59.884
третьего вида — 180 кг.

00:59:01.604 --> 00:59:04.764
Нам была задана таблица в начале лекции.

00:59:05.572 --> 00:59:08.053
Вид сырья, цена одного изделия.

00:59:08.373 --> 00:59:15.297
В данном случае 9,10,16 денежных единиц,
запасы мы с вами рассмотрели, и нормы

00:59:15.417 --> 00:59:18.179
затрат сырья в килограммах на одно
изделие.

00:59:18.299 --> 00:59:20.540
В данном случае изделие ABC.

00:59:20.941 --> 00:59:25.463
Была исходная матрица, обратите внимание,
матрица составляется из коэффициентов

00:59:26.497 --> 00:59:27.898
Нормы затрат сырья.

00:59:28.378 --> 00:59:31.421
Транспонирование строчки переходит в
столбцы.

00:59:31.541 --> 00:59:37.026
Первая строка становится первым столбцом,
вторая — строка — вторым столбцом, третья

00:59:37.106 --> 00:59:38.587
— третьим столбцом.

00:59:38.667 --> 00:59:41.710
То есть, в данном случае ведётся
транспонирование матрицы.

00:59:44.692 --> 00:59:50.247
Переменные исходной задачи: X1.x2.x 3 —
это количество изделий AB и C.

00:59:50.727 --> 00:59:56.281
Введём двойственные переменные для задачи:
Xрек 1.2.3.

00:59:56.561 --> 00:59:59.918
И мы должны найти минимум функции F со
звёздочкой.

01:00:00.757 --> 01:00:07.471
То есть 360 + 192 игрек 2, 180 игрек-3, и
она будет стремиться к

01:00:07.551 --> 01:00:10.148
минимуму при наших ограничениях.

01:00:10.468 --> 01:00:15.503
Итак, я прошу вас записать целевую функцию
F со звёздочкой и ограничения.

01:00:15.583 --> 01:00:17.422
При этом обратите внимание, что у нас знак

01:00:18.337 --> 01:00:21.261
Меньше либо равно мы поменяли на большее
либо равно.

01:00:21.782 --> 01:00:23.425
Даю вам также несколько минут.

01:04:13.650 --> 01:04:16.409
Мы с вами записали систему ограничений.

01:04:18.289 --> 01:04:21.528
Теперь мы рассмотрим последнюю таблицу
исходной задачи.

01:04:22.288 --> 01:04:26.768
Она у вас есть. В данном случае у нас
прибыль составляет 400 единиц.

01:04:26.807 --> 01:04:30.767
В четвёртой строке у нас все коэффициенты
положительные, следовательно, мы составили

01:04:30.847 --> 01:04:32.207
синлекс-таблицу верно.

01:04:33.244 --> 01:04:40.125
И также у вас есть таблица, которая
показывает переход переменной исходной

01:04:40.205 --> 01:04:42.646
задачи к переменным двойственным задач.

01:04:44.606 --> 01:04:50.647
Значение igrek 1 в последней строке
столбца P4, то есть X1 равное 29, значение

01:04:50.727 --> 01:04:53.408
igrek 2 — 53 в последней строке столбца.

01:04:53.990 --> 01:04:58.913
П5, а значение igrek 3 равно нулю в
последней строке столбца П6.

01:04:59.033 --> 01:05:02.435
Остальные значения находим в столбцах 123.

01:05:02.595 --> 01:05:08.998
То есть игрек у нас составляет вектор 29,
5 третьих, пять ноль.

01:05:09.119 --> 01:05:12.240
При этом значение целевой функции равно
400.

01:05:14.645 --> 01:05:21.122
Это минимальные затраты на всю продукцию:
29 и 53 — это теневые цены сырья первого и

01:05:21.282 --> 01:05:23.521
второго видов соответственно.

01:05:25.601 --> 01:05:32.438
Итак, мы с вами рассмотрели решение в

01:05:32.598 --> 01:05:33.078
данном случае

01:05:35.975 --> 01:05:40.303
Прямой и двойственной задачей финансовой
математике и их решения.

01:05:42.227 --> 01:05:44.431
Переходим к транспортной задаче.

01:05:59.408 --> 01:06:03.605
Итак. В данном случае

01:06:09.682 --> 01:06:11.681
транспортная задача.

01:06:11.921 --> 01:06:12.720
Тема три.

01:06:50.843 --> 01:06:57.764
Предлагаю вам сделать десятиминутный
перерыв, чтобы я смогла настроить наш

01:06:57.884 --> 01:07:01.084
лекционный материал. Итак, пишу 10 минут
перерыва.

