WEBVTT

00:00:12.177 --> 00:00:18.693
Постановка задачи, основные определения
закрытая и открытая транспортная

00:00:18.813 --> 00:00:23.930
задача, мы с вами говорили на прошлой
лекции: метод северо-западного угла, метод

00:00:24.010 --> 00:00:26.728
минимального тарифа и метод потенциалов.

00:00:26.968 --> 00:00:30.366
Ну, наиболее, конечно, эффективный — это
метод потенциалов.

00:00:32.522 --> 00:00:34.399
Какова же цель транспортной задачи?

00:00:34.599 --> 00:00:40.952
Это разработка наиболее рациональных путей
и способов транспортировки товаров,

00:00:41.032 --> 00:00:45.267
устранение чрезмерно дальних встречных и
повторных перевозок.

00:00:52.063 --> 00:00:55.260
Исторические этапы исследований
транспортной задачи.

00:00:55.419 --> 00:01:00.814
Первый этап — задача национального плана
перевозок, позволяющего минимизировать

00:01:01.014 --> 00:01:05.769
суммарный километраж в железнодорожных
перевозках при наличии не более двух

00:01:05.849 --> 00:01:07.088
поставщиков.

00:01:09.525 --> 00:01:10.444
Второй этап.

00:01:11.661 --> 00:01:17.220
Одну из разновидностей транспортной задачи
в сорок первом году поставил американец

00:01:17.380 --> 00:01:23.459
Хичкок, детально разработал Чарльз
Кумпанс, который разработал, работал

00:01:23.539 --> 00:01:27.538
членом Объединённого Комитета перевозок во
время Второй Мировой войны.

00:01:32.525 --> 00:01:38.124
Третий этап, первый общий законченный
метод решения транспортной задачи и метод

00:01:38.204 --> 00:01:42.844
потенциала разработал Контарович.

00:01:51.682 --> 00:01:55.124
На практике существуют три основные
постановки транспортной задачи.

00:01:55.284 --> 00:01:59.886
Первая: необходимо найти оптимальную
структуру транспортных средств,

00:02:00.206 --> 00:02:06.049
обеспечивающую минимизацию издержек на
транспортировку.

00:02:07.729 --> 00:02:12.652
То есть эксплуатационные и экономические
показатели зависят от состава транспорта.

00:02:17.795 --> 00:02:21.913
На практике существуют опять же три
основные постановки транспортной задачи.

00:02:22.033 --> 00:02:27.111
Второе: необходимо установить такое
распределение грузов между имеющимися в

00:02:27.191 --> 00:02:28.710
хозяйстве видами транспорта.

00:02:29.252 --> 00:02:34.486
При котором затраты на перевозки всего
объёма грузов были бы минимальными.

00:02:35.684 --> 00:02:40.318
То есть необходима эффективность
использования различного вида транспорта

00:02:40.518 --> 00:02:44.393
на одной и той же работе, при этом она не
всегда одинакова.

00:02:47.051 --> 00:02:51.494
Третье. Задачи прикрепления потребителей к
поставщикам.

00:02:52.015 --> 00:02:56.578
Экономичный план перевозок однородного
груза из пункта производства к пункту

00:02:56.738 --> 00:03:03.704
потребления. И вот

00:03:03.864 --> 00:03:07.627
в данном случае представлены вам критерии
оптимизации транспортной задачи.

00:03:07.747 --> 00:03:08.107
Первое.

00:03:08.898 --> 00:03:11.858
Минимум денежно-материальных затрат на
перевозки.

00:03:12.058 --> 00:03:15.658
Второе — минимум затрат времени на
перевозки.

00:03:16.098 --> 00:03:22.458
Третье — минимум объёма транспортных работ
и четвёртое — минимум приведённых

00:03:22.618 --> 00:03:29.098
затрат. Содержательная

00:03:29.218 --> 00:03:30.338
постановка задачи.

00:03:31.487 --> 00:03:38.052
Однородный продукт, сосредоточенный в M
пунктах отправления и количествах A12 и

00:03:38.172 --> 00:03:43.616
так далее. AN-единиц, соответственно,
необходимо доставить в каждый из Not

00:03:43.736 --> 00:03:47.938
назначения в количествах Б1, Б2 и так
далее, БН-единиц соответственно.

00:03:49.240 --> 00:03:53.959
Стоимость расстояния перевозки единицы
продукта из этого пункта отправления в

00:03:54.039 --> 00:04:00.358
житый пункт назначения равна Ц и житому,
стоимость доставки и известна для каждого

00:04:00.438 --> 00:04:06.038
маршрута. Пусть X и житое — количество
продукта, перевозимого из этого пункта

00:04:06.158 --> 00:04:08.357
отправления в сжитый пункт назначения.

00:04:09.595 --> 00:04:13.996
В данном случае задача заключается в
определении таких величин икс и ж для всех

00:04:14.076 --> 00:04:18.596
маршрутов, при которых суммарная стоимость
или расстояние перевозок были бы

00:04:18.796 --> 00:04:20.116
минимальными.

00:04:23.756 --> 00:04:26.397
Математическая постановка транспортной
задачи.

00:04:27.040 --> 00:04:32.680
Обозначения, которые вам необходимо
записать M — это количество пунктов

00:04:32.880 --> 00:04:37.840
отправления поставщиков — номер
поставщика; Н — количество пунктов

00:04:38.040 --> 00:04:41.240
назначения потребителя; Ж — номер
потребителя.

00:04:41.600 --> 00:04:45.600
А — объём однородного груза итого
поставщика запасы.

00:04:46.182 --> 00:04:52.426
Б и объём однородного груза, требуемого
ужитому потребителю спрос и Ц и сжитая —

00:04:52.506 --> 00:04:58.670
стоимость доставки единицы груза итого
поставщика и сжитого к житому потребителю.

00:04:58.870 --> 00:05:05.794
Так. Предлагаю вам записать аббревиатуру
МЕНGАИ,

00:05:05.834 --> 00:05:07.555
Б., Ц и сжитое.

00:06:28.405 --> 00:06:33.850
Я немножко поднимусь и C — это общие
затраты на перевозки.

00:06:35.051 --> 00:06:41.656
То есть вы записали: М, и N, G, A, Б,
итое, Ц и житое; X и-житое —

00:06:41.736 --> 00:06:47.141
количество груза доставляемого от итого
поставщика к житому потребителю, и Ц —

00:06:47.221 --> 00:06:48.582
общие затраты перевозки.

00:06:48.662 --> 00:06:49.783
Также это запишите.

00:10:37.013 --> 00:10:38.454
Продолжим.

00:10:44.255 --> 00:10:50.416
Представлена вашему виду таблица, где
сверху у нас на таблице «потребители».

00:10:51.776 --> 00:10:52.217
Слева

00:10:53.095 --> 00:10:55.056
Поставщики, спрос.

00:10:55.376 --> 00:11:01.338
При этом обратите внимание, сумма A равна
сумме B, то есть запас и

00:11:02.738 --> 00:11:05.299
требуемая продукции равны друг другу.

00:11:07.900 --> 00:11:12.342
Стоимость доставки единицы груза от этого
поставщика к житому потребителю.

00:11:16.900 --> 00:11:23.863
Стоимость перевозок можно выразить
следующим образом: Ц равно C11 на X1 и так

00:11:23.983 --> 00:11:26.344
далее ЦМ на XM.

00:11:26.504 --> 00:11:29.986
При этом мы предполагаем, что стоимость
должна быть минимальной.

00:11:30.266 --> 00:11:32.427
Или более компактно записано: Ц равно

00:11:33.365 --> 00:11:37.442
Э-э, в сумме Ц и житое на x и житое
стремится к минимуму.

00:11:38.361 --> 00:11:41.918
В данном случае это целевая функция,
которая позволяет определить численное

00:11:42.038 --> 00:11:46.833
значение критерия оптимальности на всех
этапах расчётов и оптимальном плане.

00:11:47.033 --> 00:11:49.551
Я вам предлагаю вот записать именно эту
формулу.

00:11:50.701 --> 00:11:53.187
которая представлена в более компактном
виде

00:12:23.792 --> 00:12:28.271
Нам необходимо найти минимальное значение
целевой функции при следующих возможных

00:12:28.391 --> 00:12:33.590
условиях. Первое условие — вывоз всего
груза от каждого поставщика представлен в

00:12:33.630 --> 00:12:39.989
виде матрицы или записано, опять же, в
более компактной форме, где сумма X и жита

00:12:40.149 --> 00:12:41.188
равна Atom.

00:12:41.714 --> 00:12:48.676
Где жи изменяется от единицы до Nimo также
найти

00:12:48.796 --> 00:12:55.159
второе условие удовлетворения спроса
каждого потребителя, где сумма X и жито

00:12:55.359 --> 00:12:56.720
равна Biтому.

00:13:02.622 --> 00:13:05.182
Третье условие — равенство запаса и
спроса.

00:13:05.942 --> 00:13:11.063
Если сумма аитого равна сумму б-житому,
вот эту формулу также я предлагаю вам

00:13:11.223 --> 00:13:16.664
записать. Равенство запаса и спроса есть
необходимое и достаточное условие

00:13:17.104 --> 00:13:19.105
совместимости и, следовательно,

00:13:19.819 --> 00:13:22.222
Разрешимости транспортной задачи.

00:13:42.413 --> 00:13:47.054
Существует две модели транспортной задачи:
закрытая и открытая модель.

00:13:47.334 --> 00:13:51.974
Закрытая модель транспортной задачи — это
спрос равен запасу.

00:13:52.854 --> 00:13:57.735
Открытая модель транспортной задачи —
спрос не равен запасу, то есть AI не равно

00:13:57.895 --> 00:13:58.735
Б житам.

00:14:08.147 --> 00:14:10.307
Модель закрытой транспортной задачи.

00:14:11.187 --> 00:14:13.466
Целевая функция стремится к минимуму.

00:14:13.546 --> 00:14:19.985
При этом даны ограничения: сумма X и
сжитое равно Ama X и жжитое равно

00:14:20.105 --> 00:14:24.784
Б-житому и переменная X и сжитое больше
либо равна нулю.

00:14:25.518 --> 00:14:31.329
Я вам её предлагаю переписать эту модель
для того, чтобы в дальнейшем мы смогли

00:14:31.410 --> 00:14:32.091
решать задачу.

00:17:43.230 --> 00:17:46.907
Итак, мы с вами записали значение целевой
функции — ограничение.

00:17:48.986 --> 00:17:51.304
Открытая модель транспортной задачи.

00:17:51.544 --> 00:17:56.781
Если запас превышает спрос, то сумма aita
больше суммы Б-житого.

00:17:57.181 --> 00:18:01.978
И если спрос превышает запас, то сумма
AITA меньше суммы Б-житого.

00:18:02.057 --> 00:18:03.457
Также запишите эти формулы.

00:18:06.416 --> 00:18:09.542
То есть, это относится к открытой модели
транспортных задач.

00:19:01.131 --> 00:19:05.088
Первое: если запас превышает спрос, то
целевая функция у нас стремится к

00:19:05.128 --> 00:19:11.803
минимуму. При ограничениях, если Aставлена
вам

00:19:11.963 --> 00:19:17.478
система ограничений: сумма X и житое
меньше либо равно Aтого и сумма X и житое

00:19:17.718 --> 00:19:18.837
равна Б-житому.

00:19:19.755 --> 00:19:24.398
В данном случае не требуется весь
имеющийся груз вывозить от поставщика.

00:19:24.718 --> 00:19:28.921
После удовлетворения спроса часть его
может оставаться невывезенной.

00:19:29.521 --> 00:19:34.164
Потребности и спрос каждого потребителя
необходимо удовлетворить полностью.

00:19:42.048 --> 00:19:48.527
Решение. Если мы возьмём разность сумм A и
B-житое, то мы получим Bn +

00:19:48.727 --> 00:19:51.046
1. Это фиктивный потребитель.

00:19:51.126 --> 00:19:55.405
То есть вводим в систему фиктивного
потребителя, который предполагается, что

00:19:55.485 --> 00:19:56.725
равен нулю.

00:19:57.325 --> 00:20:01.963
При введении фиктивного потребителя
открытая модель преобразуется в закрытую.

00:20:04.923 --> 00:20:06.267
Запишите данную форму.

00:20:30.107 --> 00:20:32.549
Второе: спрос превышает запас.

00:20:32.829 --> 00:20:38.034
Целевая функция у нас стремится к
минимуму, но ограничение в данном случае —

00:20:38.114 --> 00:20:40.797
сумма Aita меньше Бжитого.

00:20:41.397 --> 00:20:47.043
И представлена система ограничений: сумма
X и-житое равна аитому.

00:20:47.448 --> 00:20:50.845
...и сумма X и житого меньше либо равна
Бжитому.

00:20:52.603 --> 00:20:57.879
В данном случае решение у нас, если от
поставщика вычитаем потребителя сумма

00:20:57.999 --> 00:21:01.436
Бжитого минус аитое равна AM + N.

00:21:01.556 --> 00:21:02.834
Фиктивный поставщик.

00:21:02.874 --> 00:21:04.513
В данном случае у нас появляется...

00:21:05.921 --> 00:21:07.186
Запишем эту формулу.

00:21:47.495 --> 00:21:49.977
И переходим к изучению транспортной
задачи.

00:21:50.097 --> 00:21:52.259
Это метод Северо-Западного угла.

00:21:52.940 --> 00:21:54.181
Рассмотрим пример.

00:21:54.741 --> 00:21:59.945
С трёх баз требуется доставить в магазины
однородный товар, пусть на базе A1 имеется

00:22:00.105 --> 00:22:03.508
50 единиц груза, на базе А2 — 40 единиц.

00:22:03.989 --> 00:22:05.870
На базе A320 единиц.

00:22:06.070 --> 00:22:12.395
Указанный товар нужно отгрузить четырём
потребителям: Б1, Б2, Б3, Б4, потребности

00:22:12.595 --> 00:22:17.920
которых составляют, соответственно, 35,
25, 30 и 25 единиц товара.

00:22:18.280 --> 00:22:22.083
Стоимость перевозки от базы до потребителя
представлена в таблице.

00:22:24.087 --> 00:22:28.652
Требуется составить такой план перевозок,
который обеспечит минимальные транспортные

00:22:28.732 --> 00:22:33.257
расходы. Ну и как в Simplex-методе, и
опять же предлагаю, чтобы понять решение

00:22:33.457 --> 00:22:40.425
задачи, перепишите данную таблицу, в
которой у нас Б1, Б2, Б3, Б4

00:22:40.825 --> 00:22:40.985
— это

00:22:43.277 --> 00:22:47.111
Потребители: A1, A2, A3 — поставщики.

00:22:48.509 --> 00:22:53.262
Цифры в клетках — это, э-э, соответственно
стоимости на перевозку продукции.

00:27:21.334 --> 00:27:25.017
Итак, я думаю, что вы переписали таблицу,
пошли дальше.

00:27:25.457 --> 00:27:26.939
Что у нас происходит?

00:27:28.220 --> 00:27:30.221
Э-э, первый этап решения.

00:27:30.782 --> 00:27:33.064
Теперь мы составляем распределительную
таблицу.

00:27:33.144 --> 00:27:37.268
Обратите внимание, это то же самое, что
таблица предыдущая.

00:27:39.043 --> 00:27:45.805
Вот только добавляется строчка:
потребность в товаре 30, 25, 30 и 25

00:27:46.045 --> 00:27:50.005
единиц и наличие товара: 50, 40—20 единиц.

00:27:50.445 --> 00:27:55.206
Потребность товара и наличие товара,
соответственно, равно 110 единиц.

00:27:55.866 --> 00:28:01.962
Добавьте, пожалуйста, в вашу таблицу
строчку и столбик для того, чтобы мы могли

00:28:02.002 --> 00:28:02.884
перейти к решению.

00:29:57.005 --> 00:29:58.885
Второй этап — составления модели.

00:29:59.005 --> 00:30:02.885
Целевая функция, стоимость всей перевозки
у нас будет стремиться к минимуму.

00:30:02.965 --> 00:30:08.364
Обратите внимание, что коэффициенты
берутся вернусь, то есть умножаем

00:30:10.804 --> 00:30:12.484
числа, которые находятся в клетках.

00:30:14.572 --> 00:30:19.733
3246 231 23274 и так далее.

00:30:20.773 --> 00:30:24.133
Вот. И стремиться к минимуму.

00:30:24.853 --> 00:30:30.253
Задача у нас количество товара равно,
количеству запаса равно количеству спроса.

00:30:31.717 --> 00:30:35.801
И у нас в данном случае что получается?

00:30:35.961 --> 00:30:42.327
Что запас 110 единиц и спрос 110 единиц
продукции.

00:30:42.968 --> 00:30:47.972
Ограничение по поставщикам и ограничение
по потребителям.

00:30:48.749 --> 00:30:50.290
Запишите систему равенства.

00:32:45.187 --> 00:32:50.067
Итак, первое: построение опорных решений
системы, а также преобразование этих

00:32:50.107 --> 00:32:52.468
решений будут производиться в таблицах.

00:32:52.788 --> 00:32:54.308
Это обязательное условие.

00:32:54.708 --> 00:32:58.469
Второе, если базисные неизвестные X и жита
равно A

00:32:59.127 --> 00:33:03.642
То это число записывается в
соответствующие клетки изжитой, и эта

00:33:03.722 --> 00:33:05.441
клетка называется загруженной.

00:33:05.680 --> 00:33:09.157
Если же переменная не базисная, то икс
изжитое равно нулю.

00:33:09.357 --> 00:33:12.314
И соответствующая клетка остаётся
свободной.

00:33:14.552 --> 00:33:15.032
Третье.

00:33:15.698 --> 00:33:20.460
Метод северо-западного угла заключается в
том, что заполнение таблицы начинается с

00:33:20.500 --> 00:33:26.623
левого верхнего угла и двигаясь далее по
строке вправо либо по столбцу

00:33:27.344 --> 00:33:30.625
вниз, мы получаем решение.

00:33:31.426 --> 00:33:35.868
Вот так получается у нас в наличии 50
единиц товара.

00:33:36.859 --> 00:33:41.537
Смотрим первую клетку, которая находится в
левом верхнем углу.

00:33:42.657 --> 00:33:47.175
Нам требуется, обратите внимание, 30
единиц только завести.

00:33:47.735 --> 00:33:51.893
Берём, заводим, пишем число 30.

00:33:53.984 --> 00:33:55.904
Со стоимостью 3 единицы.

00:33:57.065 --> 00:34:01.226
30 единиц завезли, всё, мы полностью
удовлетворили спрос.

00:34:01.466 --> 00:34:06.027
Далее, э-э, у нас осталось в наличии 20
единиц продукции.

00:34:06.508 --> 00:34:09.628
Двигаемся по порядку, по строке сначала.

00:34:10.272 --> 00:34:15.436
Далее. Осталось 20 единиц, значит, во
второй столбец мы можем завести 20 единиц

00:34:15.636 --> 00:34:17.797
продукции 20.

00:34:17.997 --> 00:34:21.040
Но 5 единиц нужно ещё завести.

00:34:25.283 --> 00:34:26.884
Итак, мы завесли в первую

00:34:28.087 --> 00:34:33.093
Первому потребителю 30 единиц, полностью
удовлетворили спрос, второму потребителю

00:34:33.253 --> 00:34:36.216
20 единиц, осталось 5 единиц продукции.

00:34:36.897 --> 00:34:41.302
Наличие товара в данном случае 50 единиц
мы полностью израсходовали.

00:34:41.502 --> 00:34:45.026
Откуда же берём оставшиеся 5 единиц из
второй строки?

00:34:45.603 --> 00:34:50.802
В наличии 40 единиц мы берём от второго
поставщика 5 единиц и переводим во второй

00:34:50.922 --> 00:34:57.439
столбец. Итак, полностью завели продукцию
мы второму потребителю, но осталось

00:34:57.639 --> 00:34:59.359
35 единиц.

00:35:02.518 --> 00:35:03.797
Ещё раз показываю.

00:35:04.447 --> 00:35:09.323
Из первой строчки мы завезли 30 и 20
единиц потребителям.

00:35:09.443 --> 00:35:14.080
Из второй строки — 5 единиц полностью
удовлетворили спрос.

00:35:14.280 --> 00:35:17.878
Осталось 35 единиц продукции.

00:35:18.038 --> 00:35:23.954
Нужно завести третьему потребителю, это B3
и третий столбец, 30 единиц продукции.

00:35:24.034 --> 00:35:24.434
Завозим

00:35:30.590 --> 00:35:33.629
И у нас в запасе остаётся пять единиц
продукции.

00:35:34.269 --> 00:35:41.226
5 единиц мы завозим э-э в четвёртый
столбец Б4 и оставшиеся 20

00:35:41.786 --> 00:35:43.025
единиц.

00:35:45.984 --> 00:35:50.102
То есть полностью мы удовлетворили спрос
от потребителя.

00:35:50.604 --> 00:35:56.196
И в результате у нас получилась вот такая
таблица, которую я вам предлагаю записать.

00:35:56.356 --> 00:35:59.991
Итак, в наличии товара 50—40—20 единиц.

00:36:01.110 --> 00:36:04.145
Потребность 30, 25, 30 и 25.

00:36:04.225 --> 00:36:05.104
Ещё раз повторюсь.

00:36:06.486 --> 00:36:08.164
Смотрим сразу на первую строчку.

00:36:08.284 --> 00:36:13.078
В наличии товара 50 единиц, начинаем
развозить: 30 единиц завезли, полностью

00:36:13.158 --> 00:36:16.793
удовлетворили спрос, затем оставшиеся 20.

00:36:17.233 --> 00:36:19.070
Наличие товара исчезло.

00:36:19.789 --> 00:36:21.108
Переходим ко второму.

00:36:21.694 --> 00:36:23.173
Поставщику A2.

00:36:23.333 --> 00:36:27.452
Забираем 5 единиц продукции, полностью
удовлетворили Б2, да?

00:36:28.331 --> 00:36:30.810
Потребителю.

00:36:31.130 --> 00:36:33.369
Потребителю B3 нужно 30 единиц.

00:36:33.489 --> 00:36:37.487
Завезли 30 единиц, значит, в запасе у нас
осталось 5 единиц.

00:36:38.367 --> 00:36:44.368
Оставшиеся пять единиц переводим в вектор
Б4 потребителю B4 и оставшиеся 20.

00:36:44.488 --> 00:36:51.129
Итак, получается, считаем: 30 + 20 — 50
единиц израсходовали наличие товара, 5 30

00:36:51.489 --> 00:36:53.569
+ 5 — 40 единиц товара.

00:36:54.027 --> 00:36:55.987
И 20—2.

00:36:56.667 --> 00:37:02.867
По теперь по потребителям: 30 единиц, 20 +
5, 25 единиц, 30 и 25

00:37:03.067 --> 00:37:07.508
единиц. То есть мы удовлетворили
потребности.

00:37:09.039 --> 00:37:11.236
...при преимуществе наличия товара.

00:37:11.356 --> 00:37:14.912
Эту таблицу я предлагаю вам переписать,
чтобы в дальнейшем мы могли сами

00:37:15.191 --> 00:37:20.185
самостоятельно просчитать и перевести
товар методом северо-западного угла.

00:37:20.305 --> 00:37:21.464
Даю вам несколько минут.

00:42:13.818 --> 00:42:19.700
Итак, вы в первоначальную таблицу записали
данные и перевезли продукцию от поставщика

00:42:19.820 --> 00:42:21.340
к потребителю.

00:42:22.820 --> 00:42:25.021
Каковы же условия разрешимости задачи?

00:42:25.141 --> 00:42:30.022
Первое условие — число загруженных клеток
должно быть, смотрите, M + N -1.

00:42:30.142 --> 00:42:30.822
Возвращаюсь.

00:42:32.254 --> 00:42:35.931
М-количество поставщиков и потребителей.

00:42:36.131 --> 00:42:41.927
Три плюс четыре семь должно быть
заполненных клеток.

00:42:42.047 --> 00:42:44.325
Раз, два, три, четыре, пять, шесть.

00:42:44.725 --> 00:42:46.604
Заполнили таблицу правильно.

00:42:47.283 --> 00:42:47.803
Второе.

00:42:48.345 --> 00:42:51.420
Загруженные клетки не должны образовывать
замкнутого цикла.

00:42:57.440 --> 00:42:59.801
Итак, теперь мы считаем цену на перевозку.

00:42:59.921 --> 00:43:03.283
Она равна 265 денежных единиц.

00:43:03.363 --> 00:43:07.524
Каким образом считается? Считается по
клеткам, в которые перевезены продукция:

00:43:07.764 --> 00:43:14.527
30 умножаем на 3 построчно: 20 на 2 + 5 на
3, + 30 на 1, + 5 на 2

00:43:14.767 --> 00:43:16.007
+ 20 на 4.

00:43:16.448 --> 00:43:21.692
То есть по заполненным клеткам мы считаем
количество перевезённой продукции и

00:43:21.892 --> 00:43:26.655
стоимость на перевозку составляет 265
денежных единиц.

00:43:28.377 --> 00:43:30.098
Запишите цену на перевозку.

00:44:32.938 --> 00:44:36.501
Далее переходим к другому методу — метод
минимального тарифа.

00:44:37.937 --> 00:44:42.651
Увеличивает величины затрат на
грузоперевозки, позволяет найти опорный

00:44:42.731 --> 00:44:47.165
план транспортной задачи, при котором
общая стоимость перевозок груза меньше,

00:44:47.245 --> 00:44:51.520
чем стоимость перевозок при плане
северо-западного угла.

00:44:52.315 --> 00:44:57.394
То есть мы можем улучшить план перевозки и
цену заплатить намного меньше, дешевле,

00:44:57.474 --> 00:45:02.674
чем в предыдущем решении 265 ₽.

00:45:02.954 --> 00:45:07.753
Либо там что угодно, там удельных единиц.

00:45:11.282 --> 00:45:13.003
Этапы метода минимального тарифа.

00:45:13.123 --> 00:45:17.646
Этап первый. Выбирается клетка, имеющая
минимальную стоимость перевозок.

00:45:17.726 --> 00:45:21.769
Вот я вам, как вам говорила, что вот в
этих клеточках — это цена на перевозку.

00:45:22.969 --> 00:45:27.012
В этих, если таких клеток более одной, то
выбирается первая по порядку.

00:45:27.092 --> 00:45:29.733
Вот смотрим. В данном первом варианте у
нас

00:45:30.397 --> 00:45:34.119
Единица минимальная цена на перевозку,
значит, будем работать именно с этой

00:45:34.199 --> 00:45:37.200
клеткой. Это записывать необязательно.

00:45:37.560 --> 00:45:42.162
А во втором случае обратите, у нас двойка
встречается раз, два, три, четыре раза.

00:45:42.722 --> 00:45:49.085
И смотрим построчно, построчно смотрим и
выбираем клетку в строке первая попавшаяся

00:45:49.205 --> 00:45:50.886
минимальная стоимость — число два.

00:45:51.501 --> 00:45:53.140
Работаем именно с ней.

00:45:54.938 --> 00:46:01.210
Этап два. В клетку с наименьшим тарифом
помещаем наименьшее число атое либо житое.

00:46:01.290 --> 00:46:04.806
Смотрим запасы, спрос.

00:46:05.925 --> 00:46:08.362
Единица стоит у нас во второй строчке.

00:46:08.972 --> 00:46:15.728
В третьем столбике это наименьшая цена на
перевозку, она равна одной удельной

00:46:15.848 --> 00:46:22.525
единице. Смотрим, мы можем перевезти 30
кг, либо что там тонн

00:46:24.444 --> 00:46:25.204
продукции.

00:46:26.005 --> 00:46:32.523
Перевозим Затем из рассмотрения
исключается строка,

00:46:32.603 --> 00:46:37.522
соответствующая поставщику, либо запасы
которого полностью израсходованы, или

00:46:37.682 --> 00:46:41.602
столбец, соответствующий потребителю,
спрос которого полностью удовлетворён.

00:46:42.188 --> 00:46:47.551
Смотрим, мы удовлетворили вектор Б3,
третий столбец.

00:46:47.951 --> 00:46:53.595
Обратили внимание, что ставим чёрточки,
всё, мы уже с ценами 4,7 не работаем.

00:46:54.516 --> 00:47:00.079
Поработали с единицей, ещё раз перевезли
30 единиц продукции, полностью столбик B3

00:47:00.319 --> 00:47:01.080
мы заполнены.

00:47:01.617 --> 00:47:03.735
Больше перевозить продукции не нужно.

00:47:03.974 --> 00:47:09.328
Осталось 10 единиц в строке A2.

00:47:09.927 --> 00:47:16.600
И теперь опять же из этих коэффициентов
оставшихся 326, 232, 324

00:47:17.514 --> 00:47:20.076
Ищем минимальную стоимость.

00:47:23.840 --> 00:47:28.485
Из оставшихся клеток таблицы снова
выбирается клетка с наименьшим тарифом, и

00:47:28.605 --> 00:47:33.170
процесс распределения запасов продолжается
до тех пор, пока все они не будут

00:47:33.210 --> 00:47:33.771
распределены

00:47:34.399 --> 00:47:35.799
А спрос удовлетворён.

00:47:35.959 --> 00:47:40.517
Итак, как ранее говорилось, у нас двойки:
раз, два, три, четыре двойки.

00:47:40.597 --> 00:47:46.715
Выбираем первую наименьшую стоимость, так
как единицу мы уже с вами задействовали и

00:47:46.915 --> 00:47:53.432
берём из запасов, где 50 удельных единиц,
привозим 25 единиц продукции.

00:47:56.832 --> 00:48:01.108
Опять же, из оставшихся клеток таблицы
снова выбирается клетка с наименьшим

00:48:01.188 --> 00:48:06.782
тарифом, и процесс распределения запасов
продолжается до тех пор, пока все они не

00:48:06.902 --> 00:48:10.059
будут распределены, а спрос удовлетворён.

00:48:10.339 --> 00:48:13.016
Итак, когда мы 25 единиц перевезли

00:48:14.562 --> 00:48:16.482
Полностью удовлетворили спрос.

00:48:16.882 --> 00:48:23.843
Обратите внимание, что э-э столбец B2 мы
поставили чёрточки, то есть полностью

00:48:23.963 --> 00:48:29.284
закрыли, 30 единиц завезли продукции, 25
завезли, начинаем.

00:48:29.605 --> 00:48:33.565
И у нас во второй строчке осталось 10
единиц, соответственно.

00:48:34.048 --> 00:48:38.928
Мы завозим оставшихся 10 единиц в столбец
B1.

00:48:43.688 --> 00:48:46.448
Я быстро листаю, затем вы запишите.

00:48:47.208 --> 00:48:47.688
Завезли

00:48:48.200 --> 00:48:51.481
Обратите внимание, A2 полностью
удовлетворилось.

00:48:51.561 --> 00:48:56.523
То есть мы вывезли полностью 40 единиц
продукции 10 + 30.

00:48:57.323 --> 00:49:04.005
Затем мы должны в столбец Б1 завести ещё
30 единиц продукции берём из

00:49:04.925 --> 00:49:06.406
строчки A1.

00:49:07.420 --> 00:49:14.298
Завозим и остаётся у нас пять единиц
продукции.

00:49:14.737 --> 00:49:21.615
Итак, B1 — столбец спрос полностью
удовлетворён: 30 единиц продукции завезли,

00:49:21.854 --> 00:49:24.253
столбец B2 полностью завезли.

00:49:25.791 --> 00:49:30.753
Опять же ищем, обратите внимание, раз мы
поставили чёрточки, то всё уже, не можем

00:49:30.833 --> 00:49:33.554
столбец Б1 трогать, Б2 и Б3.

00:49:33.675 --> 00:49:36.636
Работаем со столбцом Б4.

00:49:41.838 --> 00:49:44.039
А в Б4 у нас что получается?

00:49:44.439 --> 00:49:46.680
У нас только ещё раз вернусь.

00:49:48.484 --> 00:49:54.886
Так. Так как полностью мы вывезли 40
единиц продукции, то 6,4.

00:49:54.966 --> 00:49:57.087
Минимальная стоимость равна четвёрке.

00:49:57.327 --> 00:50:03.209
Следовательно, 20 единиц продукции мы
завезём из третьей строчки и 5 единиц из

00:50:03.369 --> 00:50:04.169
первой строки.

00:50:05.812 --> 00:50:10.612
И в результате посмотрите, давайте начнём
ещё раз повторим.

00:50:11.612 --> 00:50:17.253
Перед нами таблица, в которой пока
представляем, что клетки не закрыты.

00:50:17.373 --> 00:50:21.213
То есть нет цен: 20, 25, 5, 10, 30 и 20.

00:50:21.968 --> 00:50:24.086
Пока видны запасы и спрос.

00:50:25.685 --> 00:50:30.681
Из цен мы ищем минимальную стоимость — это
30 единиц продукции.

00:50:30.761 --> 00:50:32.320
В данном случае единица.

00:50:33.399 --> 00:50:36.677
Единица находится во второй строчке, в
третьем столбике.

00:50:37.237 --> 00:50:41.673
Смотрим, мы можем привезти в данном случае
завезти только 30 единиц продукции.

00:50:41.753 --> 00:50:42.273
Завезли.

00:50:44.097 --> 00:50:47.975
Полностью удовлетворили спрос, закрыли
клетки.

00:50:48.174 --> 00:50:50.573
То есть вычёркиваем данный столбец.

00:50:51.252 --> 00:50:55.530
Дальше смотрим. Ещё следующая минимальная
стоимость — это двойки.

00:50:55.610 --> 00:50:59.327
Первая попавшаяся двойка — это в первой
строке, вот она у нас.

00:51:00.325 --> 00:51:02.445
Нам нужно завести 25 единиц.

00:51:02.525 --> 00:51:09.404
Завозим 25, остаётся в запасах 25 единиц,
во вторых запасах 20 единиц.

00:51:09.844 --> 00:51:11.684
Закрыли полностью столбец.

00:51:12.084 --> 00:51:14.723
Далее. Смотрим.

00:51:15.461 --> 00:51:19.339
Вычеркнули мы первый столбик, вернее,
второй, третий столбец.

00:51:19.579 --> 00:51:25.857
Остаётся у нас первый столбик, где у нас
есть опять же двойка первая попавшаяся,

00:51:25.897 --> 00:51:27.296
да, во второй строчке.

00:51:27.896 --> 00:51:32.374
У нас в данном случае, так как мы заранее
30 единиц уже вывезли, осталось 10 единиц.

00:51:32.494 --> 00:51:33.134
Закрываем.

00:51:33.552 --> 00:51:36.589
Цену на перевозку 10 единиц.

00:51:37.508 --> 00:51:42.103
Вычёркиваем вторую строчку, второй и
третий столбец.

00:51:42.263 --> 00:51:46.299
Остаются у нас коэффициенты 3.4.

00:51:47.898 --> 00:51:51.494
Цены наименьшие — 3.634, естественно
тройка.

00:51:52.627 --> 00:51:55.188
Первая у нас тройка, потому что она в
первой строке.

00:51:55.508 --> 00:52:02.271
Завозим 20 единиц продукции, то есть спрос
опять мы удовлетворили: 20 + 10 — 30.

00:52:02.551 --> 00:52:05.512
И осталось в данном случае 5 единиц
продукции.

00:52:05.952 --> 00:52:08.793
Вычёркиваем мы первый столбец, второй,
третий

00:52:09.219 --> 00:52:10.498
И вторую строчку.

00:52:10.898 --> 00:52:13.496
Остаются числа 6 и 4.

00:52:13.816 --> 00:52:16.813
Минимальная стоимость в данном случае — 4.

00:52:17.493 --> 00:52:23.848
Завозим от последнего поставщика A3 20
единиц продукции и оставшиеся 5 единиц

00:52:24.287 --> 00:52:26.965
запасов. 25 удовлетворили.

00:52:29.701 --> 00:52:34.824
Опять в завершении проверяется число
загруженных клеток M + N -1.

00:52:34.944 --> 00:52:40.747
Считаем. Потребителей-поставщиков семь:
раз, два, три, четыре, пять, шесть, семь —

00:52:40.827 --> 00:52:43.388
минус один. Шесть должно быть загруженных
клеток.

00:52:43.508 --> 00:52:45.670
Считаем построчно: раз, два, три

00:52:46.346 --> 00:52:47.787
Четыре, пять, шесть.

00:52:48.068 --> 00:52:50.190
Следовательно, мы решили верно.

00:52:51.151 --> 00:52:53.793
Итак, предлагаю записать эту таблицу.

00:52:54.233 --> 00:53:00.119
До этого она у вас была, только этот метод
называется метод минимального тарифа.

00:53:00.919 --> 00:53:02.281
Поэтому перепишите и

00:53:03.164 --> 00:53:06.767
Запишите в данном случае загруженности
клеток.

00:53:06.927 --> 00:53:10.530
И будем перейдём дальше к решению задач.

00:58:02.784 --> 00:58:04.906
Итак, мы заполнили шесть клеток.

00:58:05.387 --> 00:58:10.311
Если число загруженных клеток будет
меньше, то следует загрузить нулём клетку

00:58:10.431 --> 00:58:15.356
с наименьшим тарифом, но такую, чтобы она
не образовывалась замкнутого цикла.

00:58:18.158 --> 00:58:20.401
Оптимальный опорный план грузоперевозок.

00:58:20.441 --> 00:58:23.443
В данном случае опять же считается цена по
закрытым клеткам.

00:58:24.418 --> 00:58:30.978
Построчно: 20 умножить на 3, 25 на 2, плюс
10 на 2, плюс 30 на 1, плюс

00:58:31.378 --> 00:58:33.659
5 на 6 и 20 на 4.

00:58:35.179 --> 00:58:39.179
270 удельных единиц оплата за перевозку.

00:58:39.499 --> 00:58:41.179
Запишите цену на перевозку.

00:59:33.257 --> 00:59:36.776
Метод потенциалов. Процесс
последовательного улучшения исходного

00:59:36.896 --> 00:59:40.095
плана грузоперевозок до оптимального.

00:59:41.334 --> 00:59:48.371
Извините.

00:59:48.811 --> 00:59:51.250
Следующую теорему, которую вам необходимо
записать.

00:59:51.938 --> 00:59:56.494
Если для некоторого плана транспортной
задачи можно выбрать систему из M + N

00:59:56.694 --> 01:00:03.528
чисел UI, называемых потенциалами
поставщика и выжитая, называемыми

01:00:03.648 --> 01:00:07.765
потенциалами потребителя, то удовлетворяют
следующие условия.

01:00:08.813 --> 01:00:12.328
Тогда план оптимальный. Прошу записать эти
ограничения.

01:02:42.544 --> 01:02:44.862
Каков же экономический смысл данного
выражения?

01:02:45.142 --> 01:02:51.736
Вжитое минус Oтое равно Ц ижитому, то есть
Co — это цена на перевозку, если X и житое

01:02:51.856 --> 01:02:57.212
больше нуля. Для поставщиков и
потребителей, между которыми запланированы

01:02:57.372 --> 01:02:58.931
перевозки, разность потенциалов

01:03:00.366 --> 01:03:06.123
В ЖТ и УИТ совпадает с затратами на
транспортную единицу груза Ц и

01:03:06.243 --> 01:03:13.119
ЖТлях остальных пар

01:03:13.479 --> 01:03:17.077
поставщиков и покупателей, между которыми
перевозки не запланированы

01:03:18.060 --> 01:03:21.939
То есть нет закрытых клеток, в которых мы
перевозили товар.

01:03:22.219 --> 01:03:27.377
Разность потенциалов не превосходят
затраты на транспортировку, то есть В-ЖТ

01:03:27.577 --> 01:03:31.176
минус УИТ меньше либо равно Ц и ж.

01:03:39.824 --> 01:03:45.940
Если план перевозок оптимален, то можно
присвоить грузам в пунктах отправления и

01:03:46.060 --> 01:03:51.256
пунктам назначения потенциалы, при которых
перевозки из любого пункта отправления в

01:03:51.376 --> 01:03:54.733
любой пункт назначения не могла дать
прибыль.

01:03:55.140 --> 01:04:00.618
И чтобы в то же время перевозки, внесённые
в план, являлись безубыточными.

01:04:05.536 --> 01:04:07.016
Определение первое.

01:04:07.575 --> 01:04:12.053
Набор — это произвольная совокупность
клеток матрицы перевозок.

01:04:12.876 --> 01:04:14.397
Второе. Цепь.

01:04:14.597 --> 01:04:18.760
Последовательный набор клеток, в котором
каждые две соседние клетки расположены в

01:04:18.800 --> 01:04:21.122
одном ряду, в строке или столбце.

01:04:23.083 --> 01:04:27.927
Цикл — замкнутая цепь — последняя клетка,
которая расположена в одном ряду с первой.

01:04:31.911 --> 01:04:35.947
Первый шаг. После того, как найден
исходный опорный план перевоза каждому

01:04:36.067 --> 01:04:42.661
поставщику AIT ставится в соответствии
потенциала U, а каждому потребителю Бжитое

01:04:42.741 --> 01:04:45.939
ставится в соответствии потенциал Vita.

01:04:47.377 --> 01:04:48.137
Следующее.

01:04:48.887 --> 01:04:55.213
Числа U и выжитое выбираются так, чтобы в
любой загруженной клетке сумма потенциалов

01:04:55.413 --> 01:05:00.057
равнялась стоимости житому перевозке в
этой клетке.

01:05:06.943 --> 01:05:08.505
Итак, обратите внимание.

01:05:09.363 --> 01:05:11.163
Стоимость перевозки.

01:05:13.083 --> 01:05:19.003
Первая строчка — первый столбик: «Витое»
должно равняться трём.

01:05:20.603 --> 01:05:27.483
Дальше. Первая строчка — выитое, второй
столбик U1 + В два

01:05:27.683 --> 01:05:28.963
равно должно двум.

01:05:30.579 --> 01:05:32.058
По закрытым клеткам считаем.

01:05:32.217 --> 01:05:37.252
Дальше первая строчка — U, и четвёртый
столбец В четвёртое.

01:05:37.452 --> 01:05:40.129
Цена на перевозку должна равняться шести.

01:05:41.408 --> 01:05:47.442
Также по второй строке: U +, вот здесь
ошибка.

01:05:48.321 --> 01:05:49.839
Должна равняться двум.

01:05:51.038 --> 01:05:55.634
Дальше, U2 и Vi должно равняться единице.

01:05:56.034 --> 01:06:01.988
И последняя строчка: U3 + V четвёртое
должна равняться четырём.

01:06:02.468 --> 01:06:04.226
Запишите цену на перевозку.

01:07:39.352 --> 01:07:44.393
Итак, для того чтобы заполнялись клетки,
предполагается, что Uе равно нулю.

01:07:44.713 --> 01:07:48.794
Можно, конечно, взять любое другое число:
единицу, двойку, тройку и так далее, но

01:07:48.914 --> 01:07:52.035
обычно работать с нулём удобнее.

01:07:52.235 --> 01:07:56.356
И получается U нулю, U2 нулю, U3 -2.

01:07:56.790 --> 01:07:59.431
И так далее, по строчке к столбику.

01:08:00.631 --> 01:08:02.592
То есть что у нас получается?

01:08:03.272 --> 01:08:09.674
Мы смотрели по закрытым клеткам, что у нас
должны коэффициенты получиться: 3, 2,

01:08:10.114 --> 01:08:12.955
6, 2, 1 и 4.

01:08:14.047 --> 01:08:16.928
А теперь проверяем открытые клетки.

01:08:17.648 --> 01:08:19.328
Цена на перевозку.

01:08:22.208 --> 01:08:24.769
И вот клетка 1—3, смотрим.

01:08:25.289 --> 01:08:29.689
Первая строчка, первое число — это номер
строки, второе число — номер столбца —

01:08:29.809 --> 01:08:31.450
1—3. 1—3.

01:08:31.772 --> 01:08:34.414
Цена на перевозку равна четырём.

01:08:35.215 --> 01:08:38.177
А у нас должно быть меньше либо равно этой
сумме.

01:08:38.457 --> 01:08:42.620
Дальше. 2, два, вторая строчка, второй
столбик.

01:08:42.860 --> 01:08:47.743
Цена на перевозку у нас получается двум
меньше трёх.

01:08:47.823 --> 01:08:48.183
Хорошо.

01:08:49.002 --> 01:08:55.758
И так далее. Для каждой свободной клетки

01:08:55.878 --> 01:09:01.874
вычисляется оценка разности между тарифом
клетки и её основным тарифом.

01:09:04.153 --> 01:09:08.710
План оптимален тогда, когда по каждой
свободной клетке эта оценка не

01:09:08.910 --> 01:09:09.790
отрицательна.

01:09:27.319 --> 01:09:30.881
И в результате, когда мы находили дельта,
у нас получилась одна отрицательная

01:09:31.002 --> 01:09:37.767
оценка. Это клетка C.4 минус клетка, опять
же из первого плана, из второго

01:09:37.887 --> 01:09:40.730
Ц со штрихом 2.4.

01:09:40.930 --> 01:09:44.813
Минус 4. То есть получается, что
полученный план перевозок не является

01:09:45.414 --> 01:09:48.096
оптимальным, то есть его можно улучшить.

01:09:57.194 --> 01:10:02.797
Так как среди оценок Дельта и Жита имеется
отрицательная оценка A2.4.

01:10:05.679 --> 01:10:10.282
Четвёртый шаг. Если есть хотя бы одна
отрицательная оценка, то план надо

01:10:10.442 --> 01:10:13.043
улучшить, то есть построить новый план
перевозки.

01:10:14.197 --> 01:10:17.280
И загружается та клетка, у которой оценка
отрицательная.

01:10:17.440 --> 01:10:21.683
Если будет несколько отрицательных оценок,
то выбирается клетка для загрузки, у

01:10:21.763 --> 01:10:26.166
которой отрицательная оценка наибольшая по
абсолютной величине.

01:10:28.048 --> 01:10:29.969
Итак, мы загружаем, вот показано.

01:10:30.741 --> 01:10:36.465
В данном случае клетку с перевозкой,
равной, э-э, цене на перевозку, равной

01:10:36.545 --> 01:10:39.868
двум, оценка отрицательная у нас -4.

01:10:43.671 --> 01:10:48.754
Для выбранной клетки строится замкнутый
цикл, то есть замкнутый путь, соединяющий

01:10:48.835 --> 01:10:51.356
выбранную незаполненную клетку с неже

01:10:52.662 --> 01:10:55.384
И проходящие через заполненные клетки.

01:10:55.504 --> 01:10:58.788
Для каждой свободной клетки существует
только один цикл.

01:10:58.988 --> 01:11:03.152
Итак, мы начинаем работать с клетки, где у
нас цена на перевозку 2, потому что там у

01:11:03.232 --> 01:11:07.797
нас отрицательный был коэффициент, и
двигаемся строго по закрытым клеткам.

01:11:09.064 --> 01:11:12.067
По закрытым. Можем перешагнуть через
закрытую клетку.

01:11:12.108 --> 01:11:16.432
Вот, допустим, если бы мы пошли от пятёрки
к двадцати пяти, дальше у нас все клетки

01:11:16.512 --> 01:11:20.997
открытые. Нет. Мы не можем повернуть,
поворачиваем по закрытым клеткам.

01:11:21.157 --> 01:11:25.562
То есть мы можем от пяти перейти к
двадцати двадцать единиц перевозки.

01:11:25.602 --> 01:11:26.043
Затем у нас

01:11:26.659 --> 01:11:33.064
Э-э, в этот, э-э, в данном случае, в A3
строку мы не можем зайти, потому что тут

01:11:33.304 --> 01:11:35.266
нет у нас перевезённой продукции.

01:11:35.386 --> 01:11:39.870
Строго идём по закрытым клеткам,
следовательно, от двадцати идём к десяти и

01:11:39.991 --> 01:11:44.595
возвращаемся к клетке, с которой мы начали
работать.

01:11:45.869 --> 01:11:48.151
Двигаемся строго по закрытым клеткам.

01:11:48.271 --> 01:11:53.076
Через клетку закры- закрытую можно
перешагнуть, но поворачиваем строго в

01:11:53.116 --> 01:11:54.558
закрытых клетках.

01:11:58.201 --> 01:12:03.927
В каждой клетке цикла начинается свободно,
проставляются поочерёдно знаки плюс и

01:12:04.007 --> 01:12:04.368
минус.

01:12:04.914 --> 01:12:07.913
В клетках со знаком плюс.

01:12:09.193 --> 01:12:15.032
Либо минус в данном случае выбирается
наименьший груз, который перемещается по

01:12:15.112 --> 01:12:16.991
клеткам замкнутого цикла.

01:12:17.071 --> 01:12:21.670
То есть прибавляется к поставщикам X и
житое в клетках со знаком плюс

01:12:21.830 --> 01:12:24.190
прибавляется данная цена на перевозку.

01:12:25.609 --> 01:12:27.891
А со знаком минус вычитается.

01:12:27.971 --> 01:12:30.293
И смотрим мы на нашу табличку.

01:12:30.373 --> 01:12:31.774
Мы решили пойти.

01:12:31.935 --> 01:12:37.419
Вот я её предлагаю вам записать эти знаки,
где плюс мы будем прибавлять товар, где

01:12:37.539 --> 01:12:39.101
минус вычитать.

01:12:39.661 --> 01:12:40.702
Среди минусов

01:12:41.545 --> 01:12:46.824
Мы смотрим минимальную перевозку — 5
единиц продукции.

01:12:47.104 --> 01:12:51.543
То есть теперь, где плюс мы будем
прибавлять 5 единиц, где минус вычитать.

01:12:51.583 --> 01:12:53.543
То есть, в данном случае тут будет ноль.

01:12:54.062 --> 01:12:57.822
20 + 5 — 25, 10 -5 — пять единиц.

01:12:59.106 --> 01:13:03.515
В результате такого перемещения груза по
циклу получен новый план перевозок.

01:13:43.802 --> 01:13:45.443
Итак, мы строим новый план.

01:13:45.724 --> 01:13:51.410
Как я вам говорила, мы перевезли груз, где
было минус, мы добавили, вычли пять

01:13:51.410 --> 01:13:54.973
единиц, где плюс добавили и смотрим, в
результате

01:13:57.051 --> 01:14:02.457
Нашего цикла замкнутого у нас получилось в
первой строке 25—25 единиц, во второй — 5

01:14:02.698 --> 01:14:04.780
35 и в третьей — 20.

01:14:04.980 --> 01:14:06.903
Смотрим количество заполненных клеток.

01:14:06.983 --> 01:14:11.588
Должно быть 6. По формуле M + N - 1.

01:14:13.189 --> 01:14:16.671
Три поставщика и четыре потребителя: семь
минус один шесть.

01:14:16.751 --> 01:14:21.073
Считаем: раз, два, три, четыре, пять,
шесть по закрытым клеткам.

01:14:24.435 --> 01:14:28.877
Далее вычисления по методу потенциала
повторяются с первого этапа, то есть

01:14:29.702 --> 01:14:33.784
Идётся опять же подсчёт по закрытым
клеткам, что цена на перевозку должна

01:14:33.904 --> 01:14:37.105
соответствовать строчке и столбику.

01:14:39.226 --> 01:14:45.550
Вот. Далее мы проверяем по закрытым
клеткам и ищем

01:14:45.670 --> 01:14:47.110
отрицательный коэффициент.

01:14:55.375 --> 01:14:59.370
Опять же смотрим, что полученный план
перевозок не является оптимальным, потому

01:14:59.530 --> 01:15:02.846
что у нас появилась отрицательная оценка.

01:15:05.483 --> 01:15:09.039
Причём их две: Дельта 3.1 и Дельта 3—2.

01:15:09.319 --> 01:15:11.556
Посмотрим. 3.1.

01:15:12.728 --> 01:15:17.807
У нас смотрим третья строчка — первый
столбик.

01:15:19.287 --> 01:15:24.766
Первый столбик. Сумма на перевозку у нас
четыре единицы, а запланировано — три

01:15:24.886 --> 01:15:26.126
единицы на перевозку.

01:15:26.246 --> 01:15:27.965
Значит, у нас мы

01:15:29.435 --> 01:15:34.392
Переплатили за перевозку продукции, и
дальше 3,2.

01:15:34.792 --> 01:15:36.791
3,2 смотрим.

01:15:39.550 --> 01:15:44.868
Опять же, мы должно быть U3 + B2 должно
быть у нас две единицы, а получилось

01:15:45.068 --> 01:15:45.947
четыре единицы.

01:15:47.377 --> 01:15:49.377
То есть две отрицательных оценки.

01:15:52.018 --> 01:15:55.938
То есть план необходимо опять же улучшить
и построить новый.

01:15:57.258 --> 01:16:01.819
И в нашем случае загружается та клетка, у
которой оценка отрицательная.

01:16:02.219 --> 01:16:05.859
Ну, в данном случае две отрицательных
оценки, но мы смотрим по минимальной

01:16:05.939 --> 01:16:06.579
стоимости.

01:16:11.441 --> 01:16:14.560
И опять же обратите внимание, строим план
на перевозку.

01:16:14.640 --> 01:16:19.559
Начинаем с пустой клетки, то есть ставим
знак плюс и начинаем двигаться по закрытым

01:16:19.639 --> 01:16:23.839
клеткам. И при этом должно быть
чередование знаков: плюс, минус, плюс,

01:16:23.919 --> 01:16:28.118
минус. Среди минусов выбираем минимальный
товар, который был перевезён.

01:16:28.554 --> 01:16:30.193
Опять же, 5 единиц.

01:16:30.593 --> 01:16:36.310
Там, где стоит знак минус, мы должны
вычислить пять единиц, где знак плюс

01:16:36.430 --> 01:16:37.869
прибавить 5 единиц.

01:16:38.189 --> 01:16:41.627
Клетки, которые мы не трогали, остаются
без изменений.

01:16:45.625 --> 01:16:46.984
Построили новый план.

01:16:47.975 --> 01:16:51.699
В данном случае опять же считаем
количество загруженных клеток: раз, два,

01:16:51.859 --> 01:16:53.861
три, четыре, пять, шесть.

01:16:58.426 --> 01:17:05.192
И опять же ищем потенциалы: U 1, 2, 3, V
1, 2, 3, 4.

01:17:08.653 --> 01:17:13.374
И по пустым клеткам определяем значение на
перевозку.

01:17:13.694 --> 01:17:16.534
И обратите внимание, что у нас
коэффициенты все получились

01:17:16.614 --> 01:17:22.214
положительными. Следовательно, полученный
план перевозок является оптимальным, так

01:17:22.414 --> 01:17:26.134
как среди оценок Дельта и Житого нет
отрицательных оценок.

01:17:32.194 --> 01:17:38.034
Вот в нашем случае мы видим таблицу
оптимального плана перевозки на продукцию,

01:17:38.314 --> 01:17:44.033
где количество либо цена на перевозку
составляет 250 денежных единиц.

01:17:44.273 --> 01:17:49.793
Опять же, это мы смотрим по закрытым
клеткам: 25 умножить на 3, 25 на 2.

01:17:50.267 --> 01:17:57.028
Дальше построчно: 30 умножить на 1, плюс
10 на два, плюс 5 умножить на три и

01:17:57.188 --> 01:17:58.589
15 на 4.

01:17:59.629 --> 01:18:03.909
В результате суммы произведений получаем,
что цена на перевозку у нас в результате

01:18:04.069 --> 01:18:05.510
получилась 250.

01:18:06.193 --> 01:18:07.991
Денежных единиц.

01:18:12.307 --> 01:18:15.344
Итак, наша сегодняшняя лекция подошла к
концу.

01:18:15.584 --> 01:18:20.420
Спасибо за внимание. С вами была Романова
Татьяна Николаевна, доцент кафедры

01:18:20.499 --> 01:18:23.617
информатики, математики и
естественно-научных дисциплин.

