Математическое моделирование в менеджменте и маркетинге

Размещено на http://www.allbest.ru/

Индивидуальное домашнее задание

по дисциплине «Математическое моделирование в менеджменте и маркетинге»

выполнил:

студент 5курса гр122с «экономическая кибернетика»

Морозов Павел Григорьевич

Сдал:01 мая 2017г



1. Дать ответ на теоретический вопрос. Математическое моделирование. Этапы, методы

С середины XX в. в самых различных областях человеческой деятельности стали широко применять математические методы и ЭВМ. Возникли такие новые дисциплины, как «математическая экономика», «математическая химия», «математическая лингвистика» и т. д., изучающие математические модели соответствующих объектов и явлений, а также методы исследования этих моделей.

Математическая модель -- это приближенное описание какого-либо класса явлений или объектов реального мира на языке математики. Основная цель моделирования -- исследовать эти объекты и предсказать результаты будущих наблюдений. Однако моделирование -- это еще и метод познания окружающего мира, дающий возможность управлять им.

Математическое моделирование и связанный с ним компьютерный эксперимент незаменимы в тех случаях, когда натурный эксперимент невозможен или затруднен по тем или иным причинам. Например, нельзя поставить натурный эксперимент в истории, чтобы проверить, «что было бы, если бы...» Невозможно проверить правильность той или иной космологической теории. В принципе возможно, но вряд ли разумно, поставить эксперимент по распространению какой-либо болезни, например чумы, или осуществить ядерный взрыв, чтобы изучить его последствия. Однако все это вполне можно сделать на компьютере, построив предварительно математические модели изучаемых явлений.

Классификация математических моделей.

Математические модели могут быть детерменированными и стохастическими.

Детерменированные модели- это модели, в которых установлено взаимно-однозначное соответствие между переменными описывающими объект или явления.

Такой подход основан на знании механизма функционирования объектов. Часто моделируемый объект сложен и расшифровка его механизма может оказаться очень трудоемкой и длинной во времени. В этом случае поступают следующим образом: на оригинале проводят эксперименты, обрабатывают полученные результаты и, не вникая в механизм и теорию моделируемого объекта с помощью методов математической статистики и теории вероятности, устанавливают связи между переменными, описывающими объект. В этом случае получают стахостическую модель. В стахостической модели связь между переменными носит случайный характер, иногда это бывает принципиально. Воздействие огромного количества факторов, их сочетание приводит к случайному набору переменных описывающих объект или явление. По характеру режимов модель бывают статистическими идинамическими.

Статистическая модель включает описание связей между основными переменными моделируемого объекта в установившемся режиме без учета изменения параметров во времени.

В динамической модели описываются связи между основными переменными моделируемого объекта при переходе от одного режима к другому.

Модели бывают дискретными и непрерывными, а также смешанного типа. В непрерывных переменные принимают значения из некоторого промежутка, в дискретных переменные принимают изолированные значения.

Линейные модели- все функции и отношения, описывающие модель линейно зависят от переменных и не линейные в противном случае.

Требования,предъявляемые к моделям.

1. Универсальность - характеризует полноту отображения моделью изучаемых свойств реального объекта.

2. Адекватность - способность отражать нужные свойства объекта с погрешностью не выше заданной.

2. Точность - оценивается степенью совпадения значений характеристик реального объекта и значения этих характеристик полученных с помощью моделей.

3. Экономичность - определяется затратами ресурсов ЭВМ памяти и времени на ее реализацию и эксплуатацию.

Основные этапы математического моделирования

1) Построение модели. На этом этапе задается некоторый «нематематический» объект -- явление природы, конструкция, экономический план, производственный процесс и т. д. При этом, как правило, четкое описание ситуации затруднено. Сначала выявляются основные особенности явления и связи между ними на качественном уровне. Затем найденные качественные зависимости формулируются на языке математики, то есть строится математическая модель. Это самая трудная стадия моделирования.

2) Решение математической задачи, к которой приводит модель. На этом этапе большое внимание уделяется разработке алгоритмов и численных методов решения задачи на ЭВМ, при помощи которых результат может быть найден с необходимой точностью и за допустимое время.

3) Интерпретация полученных следствий из математической модели. Следствия, выведенные из модели на языке математики, интерпретируются на языке, принятом в данной области.

4) Проверка адекватности модели. На этом этапе выясняется, согласуются ли результаты эксперимента с теоретическими следствиями из модели в пределах определенной точности.

5) Модификация модели. На этом этапе происходит либо усложнение модели, чтобы она была более адекватной действительности, либо ее упрощение ради достижения практически приемлемого решения.

Классификация моделей

Классифицировать модели можно по разным критериям. Например, по характеру решаемых проблем модели могут быть разделены на функциональные и структурные. В первом случае все величины, характеризующие явление или объект, выражаются количественно. При этом одни из них рассматриваются как независимые переменные, а другие -- как функции от этих величин. Математическая модель обычно представляет собой систему уравнений разного типа (дифференциальных, алгебраических и т. д.), устанавливающих количественные зависимости между рассматриваемыми величинами. Во втором случае модель характеризует структуру сложного объекта, состоящего из отдельных частей, между которыми существуют определенные связи. Как правило, эти связи не поддаются количественному измерению. Для построения таких моделей удобно использовать теорию графов. Граф -- это математический объект, представляющий собой некоторое множество точек (вершин) на плоскости или в пространстве, некоторые из которых соединены линиями (ребрами).

По характеру исходных данных и результатов предсказания модели могут быть разделены на детерминистические и вероятностно-статистические. Модели первого типа дают определенные, однозначные предсказания. Модели второго типа основаны на статистической информации, а предсказания, полученные с их помощью, имеют вероятностный характер.

Методы исследования математических моделей

Все методы математического моделирования можно разделить на четыре класса:

-аналитические (априорные);

-имитационные (априорно-апостериорные) модели;

-эмпирико-статистические (апостериорные) модели;

-модели, в которых в той или иной форме представлены идеи искусственного интеллекта (самоорганизация, эволюция, нейросетевые конструкции и т.д.).

Аналитические модели (англ. analytical models) - один из классов математического моделирования, широко используемый в экологии. При построении таких моделей исследователь сознательно отказывается от детального описания экосистемы, оставляя лишь наиболее существенные, с его точки зрения, компоненты и связи между ними, и использует достаточно малое число правдоподобных гипотез о характере взаимодействия компонентов и структуры экосистемы. Аналитические модели служат, в основном, целям выявления, математического описания, анализа и объяснения свойств или наблюдаемых феноменов, присущих максимально широкому кругу экосистем. Так, например, широко известная модель конкуренции Лотки-Вольтерра позволяет указать условия взаимного сосуществования видов в рамках различных сообществ.

Имитационные модели (англ. simulation models) - один из основных классов математического моделирования. Целью построения имитаций является максимальное приближение модели к конкретному (чаще всего уникальному) экологическому объекту и достижение максимальной точности его описания. Имитационные модели претендуют на выполнение как объяснительных, так и прогнозных функций, хотя выполнение первых для больших и сложных имитаций проблематично (для удачных имитационных моделей можно говорить лишь о косвенном подтверждении непротиворечивости положенных в их основу гипотез). Имитационные модели реализуются на ЭВМ с использованием блочного принципа, позволяющего всю моделируемую систему разбить на ряд подсистем, связанных между собой незначительным числом обобщенных взаимодействий и допускающих самостоятельное моделирование с использованием своего собственного математического аппарата (в частности, для подсистем, механизм функционирования которых неизвестен, возможно построение регрессионных или самоорганизующихся моделей). Такой подход позволяет также достаточно просто конструировать, путем замены отдельных блоков, новые имитационные модели. Если имитационные модели реализуются без блочного принципа, можно говорить о квазиимитационном моделировании. Основная цель построения этих моделей состоит в следующем: упорядочение или агрегирование информации; поиск, количественная оценка и содержательная интерпретация причинно-следственных отношений между переменными системы; оценка достоверности и продуктивности различных гипотез о взаимном влиянии наблюдаемых явлений и воздействующих факторов; идентификация параметров расчетных уравнений различного назначения. Часто эмпирико-статистические модели являются "сырьем" и обоснованием подходов к построению моделей других типов (в первую очередь, имитационных). Важным методологическим вопросом является определение характера зависимости между факторами и результативными показателями: функциональная она или стохастическая, прямая или обратная, прямолинейная или криволинейная и т.д. Здесь используются теоретико- статистические критерии, практический опыт, а также способы сравненияпараллельных и динамичных рядов, аналитических группировок исходной информации, графические методы и др. Детерминированный анализ представляет собой методику исследования влияния факторов, связь которых с результативным показателем носит явно выраженный функциональный характер, т.е. когда результативный показатель представляется в виде произведения, частного или алгебраической суммы исходных факторов. Стохастический анализ представляет собой обширный класс методов, опирающихся на теоретико-вероятностные представления, теоремы, критерии и методы параметрической и непараметрической статистики. Искусственный интеллект ИИ (artificial intelligence) обычно трактуется как свойство автоматических систем брать на себя отдельные функции мыслительной способности человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий. Речь идет, в первую очередь, о системах, в основу которых положены принципы обучения, самоорганизации и эволюции при минимальном участии человека, но привлечении его в качестве учителя и партнёра, гармоничного элемента человеко-машинной систем

математический моделирование транспортный задача

2. Решить задачу графическим методом

Необходимо найти максимальное значение целевой функции L(x)= 2x₁+2x₂ > max, при системе ограничений:

6x₁+8x₂?48, (1)

8x₁+11x₂?88, (2)

x₁-x₂?1, (3)

x₁?7, (4)

x₁ ? 0, (5)

x₂ ? 0, (6)

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом)- рис 2.1,рис2.2.

Рисунок 2.1 Опредение полуплоскостей, заданных неравенствами

или

Рисунок 2.2 Опредение полуплоскостей, заданных неравенстсвами

Далее, найдем границы области допустимых решений.

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений - рис.2.3.

Рисунок 2.3 Обозначение границ области многоугольника решений

Рассмотрим целевую функцию задачи L(x)= 2x₁+2x₂ > max.

Для этого построим прямую, отвечающую значению функции L(x)= 0:L(x) = 2x₁+2x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации L(X). Начало вектора - точка (0; 0), конец - точка (2; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией - рис 2.4.

Рисунок 2.4 Целевая функция в ее максимальном значении.

Прямая L(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

6x₁+8x₂=48

x₁-x₂=1

Решив систему уравнений, получим: x₁ = 4, x₂ = 3

Откуда найдем максимальное значение целевой функции:

L(X) = 2*4 + 2*3 = 14

Ответ: максимальное значение целевой функции 14.



3. Решить транспортную задачу. Опорный план найти тремя методами

a\b	25	40	50	30	45
20	7	3	4	8	6
60	5	7	2	3	5
45	1	4	10	2	6
70	3	4	2	7	8

Допустим, стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	Запасы
1	7	3	4	8	6	20
2	5	7	0	2	3	60
3	1	4	10	2	6	45
4	3	4	2	7	8	70
Потребности	25	40	50	30	45

1. Решим задачу методом минимального элемента

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 20 + 60 + 45 + 70 = 195

?b = 25 + 40 + 50 + 30 + 45 = 190

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 5 (195--190). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	6	Запасы
1	7	3	4	8	6	0	20
2	5	7	0	2	3	0	60
3	1	4	10	2	6	0	45
4	3	4	2	7	8	0	70
Потребности	25	40	50	30	45	5

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.

Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Искомый элемент равен c₂₃=0. Для этого элемента запасы равны 60, потребности 50. Поскольку минимальным является 50, то вычитаем его.



x₂₃ = min(60,50) = 50.

7	3	x	8	6	0	20
5	7	0	2	3	0	60 - 50 = 10
1	4	x	2	6	0	45
3	4	x	7	8	0	70
25	40	50 - 50 = 0	30	45	5

Искомый элемент равен c₃₁=1. Для этого элемента запасы равны 45, потребности 25. Поскольку минимальным является 25, то вычитаем его.

x₃₁ = min(45,25) = 25.

x	3	x	8	6	0	20
x	7	0	2	3	0	10
1	4	x	2	6	0	45 - 25 = 20
x	4	x	7	8	0	70
25 - 25 = 0	40	0	30	45	5

Искомый элемент равен c₂₄=2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.

x₂₄ = min(10,30) = 10.

x	3	x	8	6	0	20
x	x	0	2	x	x	10 - 10 = 0
1	4	x	2	6	0	20
x	4	x	7	8	0	70
0	40	0	30 - 10 = 20	45	5

Искомый элемент равен c₃₄=2. Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₃₄ = min(20,20) = 20.

x	3	x	8	6	0	20
x	x	0	2	x	x	0
1	x	x	2	x	x	20 - 20 = 0
x	4	x	7	8	0	70
0	40	0	20 - 20 = 0	45	5

Искомый элемент равен c₁₂=3. Для этого элемента запасы равны 20, потребности 40. Поскольку минимальным является 20, то вычитаем его.

x₁₂ = min(20,40) = 20.

x	3	x	8	x	x	20 - 20 = 0
x	x	0	2	x	x	0
1	x	x	2	x	x	0
x	4	x	7	8	0	70
0	40 - 20 = 20	0	0	45	5

Искомый элемент равен c₄₂=4. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₄₂ = min(70,20) = 20.

x	3	x	8	x	x	0
x	x	0	2	x	x	0
1	x	x	2	x	x	0
x	4	x	7	8	0	70 - 20 = 50
0	20 - 20 = 0	0	0	45	5

Искомый элемент равен c₄₅=8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.

x₄₅ = min(50,45) = 45.

x	3	x	8	x	x	0
x	x	0	2	x	x	0
1	x	x	2	x	x	0
x	4	x	7	8	0	50 - 45 = 5
0	0	0	0	45 - 45 = 0	5

Искомый элемент равен c₄₆=0. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₄₆ = min(5,5) = 5.

x	3	x	8	x	x	0
x	x	0	2	x	x	0
1	x	x	2	x	x	0
x	4	x	7	8	0	5 - 5 = 0
0	0	0	0	0	5 - 5 = 0

Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.

Ранее были вычеркнуты 1, 2, 3, 5-столбцы и 1, 2, 3, 4-строки, поэтому поиск ведется среди не вычеркнутых (см. таблицу).

7	3	4	8	6	0	20[0]
5	7	0	2	3	0	60[0]
1	4	10	2	6	0	45[0]
3	4	2	7	8	0	70[0]
25[0]	40[0]	50[0]	30[0]	45[0]	5[0]

Искомый элемент равен c₄₄=7, но т.к. ограничения выполнены, то x₄₄=0.

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50]	2[10]	3	0	60
3	1[25]	4	10	2[20]	6	0	45
4	3	4[20]	2	7[0]	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*20 + 0*50 + 2*10 + 1*25 + 2*20 + 4*20 + 8*45 + 0*5 = 585

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₄ + v₂ = 4; 3 + u₄ = 4; u₄ = 1

u₄ + v₄ = 7; 1 + v₄ = 7; v₄ = 6

u₂ + v₄ = 2; 6 + u₂ = 2; u₂ = -4

u₂ + v₃ = 0; -4 + v₃ = 0; v₃ = 4

u₃ + v₄ = 2; 6 + u₃ = 2; u₃ = -4

u₃ + v₁ = 1; -4 + v₁ = 1; v₁ = 5

u₄ + v₅ = 8; 1 + v₅ = 8; v₅ = 7

u₄ + v₆ = 0; 1 + v₆ = 0; v₆ = -1

	v1=5	v2=3	v3=4	v4=6	v5=7	v6=-1
u1=0	7	3[20]	4	8	6	0
u2=-4	5	7	0[50]	2[10]	3	0
u3=-4	1[25]	4	10	2[20]	6	0
u4=1	3	4[20]	2	7[0]	8[45]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;5): 0 + 7 > 6; ?₁₅ = 0 + 7 - 6 = 1

(4;1): 1 + 5 > 3; ?₄₁ = 1 + 5 - 3 = 3

(4;3): 1 + 4 > 2; ?₄₃ = 1 + 4 - 2 = 3

max(1,3,3) = 3

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50]	2[10]	3	0	60
3	1[25][-]	4	10	2[20][+]	6	0	45
4	3[+]	4[20]	2	7[0][-]	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (4,1 > 4,4 > 3,4 > 3,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50]	2[10]	3	0	60
3	1[25]	4	10	2[20]	6	0	45
4	3[0]	4[20]	2	7	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₄ + v₂ = 4; 3 + u₄ = 4; u₄ = 1

u₄ + v₁ = 3; 1 + v₁ = 3; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₄ = 2; -1 + v₄ = 2; v₄ = 3

u₂ + v₄ = 2; 3 + u₂ = 2; u₂ = -1

u₂ + v₃ = 0; -1 + v₃ = 0; v₃ = 1

u₄ + v₅ = 8; 1 + v₅ = 8; v₅ = 7

u₄ + v₆ = 0; 1 + v₆ = 0; v₆ = -1

	v1=2	v2=3	v3=1	v4=3	v5=7	v6=-1
u1=0	7	3[20]	4	8	6	0
u2=-1	5	7	0[50]	2[10]	3	0
u3=-1	1[25]	4	10	2[20]	6	0
u4=1	3[0]	4[20]	2	7	8[45]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;5): 0 + 7 > 6; ?₁₅ = 0 + 7 - 6 = 1

(2;5): -1 + 7 > 3; ?₂₅ = -1 + 7 - 3 = 3

max(1,3) = 3

Выбираем максимальную оценку свободной клетки (2;5): 3

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50]	2[10][-]	3[+]	0	60
3	1[25][-]	4	10	2[20][+]	6	0	45
4	3[0][+]	4[20]	2	7	8[45][-]	0[5]	70
Потребности	25	40	50	30	45	5



Цикл приведен в таблице (2,5 > 2,4 > 3,4 > 3,1 > 4,1 > 4,5).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[20]	2	7	8[35]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₄ + v₂ = 4; 3 + u₄ = 4; u₄ = 1

u₄ + v₁ = 3; 1 + v₁ = 3; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₄ = 2; -1 + v₄ = 2; v₄ = 3

u₄ + v₅ = 8; 1 + v₅ = 8; v₅ = 7

u₂ + v₅ = 3; 7 + u₂ = 3; u₂ = -4

u₂ + v₃ = 0; -4 + v₃ = 0; v₃ = 4

u₄ + v₆ = 0; 1 + v₆ = 0; v₆ = -1



	v1=2	v2=3	v3=4	v4=3	v5=7	v6=-1
u1=0	7	3[20]	4	8	6	0
u2=-4	5	7	0[50]	2	3[10]	0
u3=-1	1[15]	4	10	2[30]	6	0
u4=1	3[10]	4[20]	2	7	8[35]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;5): 0 + 7 > 6; ?₁₅ = 0 + 7 - 6 = 1

(4;3): 1 + 4 > 2; ?₄₃ = 1 + 4 - 2 = 3

max(1,3) = 3

Выбираем максимальную оценку свободной клетки (4;3): 2

Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[50][-]	2	3[10][+]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[20]	2[+]	7	8[35][-]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 35. Прибавляем 35 к объемам грузов, стоящих в плюсовых клетках и вычитаем 35 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[15]	2	3[45]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[20]	2[35]	7	8	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₄ + v₂ = 4; 3 + u₄ = 4; u₄ = 1

u₄ + v₁ = 3; 1 + v₁ = 3; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₄ = 2; -1 + v₄ = 2; v₄ = 3

u₄ + v₃ = 2; 1 + v₃ = 2; v₃ = 1

u₂ + v₃ = 0; 1 + u₂ = 0; u₂ = -1

u₂ + v₅ = 3; -1 + v₅ = 3; v₅ = 4

u₄ + v₆ = 0; 1 + v₆ = 0; v₆ = -1

	v1=2	v2=3	v3=1	v4=3	v5=4	v6=-1
u1=0	7	3[20]	4	8	6	0
u2=-1	5	7	0[15]	2	3[45]	0
u3=-1	1[15]	4	10	2[30]	6	0
u4=1	3[10]	4[20]	2[35]	7	8	0[5]



Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

Анализ оптимального плана.

Из 1-го склада необходимо часть груза (20) направить в 2-й магазин.

Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)

Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)

Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)

На 4-ом складе остался невостребованным груз в количестве 5 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₆=0.

2 Метод северо-западного угла

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен c₁₁=7. Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.

x₁₁ = min(20,25) = 20.

7	x	x	x	x	x	20 - 20 = 0
5	7	0	2	3	0	60
1	4	10	2	6	0	45
3	4	2	7	8	0	70
25 - 20 = 5	40	50	30	45	5

Искомый элемент равен c₂₁=5. Для этого элемента запасы равны 60, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₂₁ = min(60,5) = 5.

7	x	x	x	x	x	0
5	7	0	2	3	0	60 - 5 = 55
x	4	10	2	6	0	45
x	4	2	7	8	0	70
5 - 5 = 0	40	50	30	45	5

Искомый элемент равен c₂₂=7. Для этого элемента запасы равны 55, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x₂₂ = min(55,40) = 40.

7	x	x	x	x	x	0
5	7	0	2	3	0	55 - 40 = 15
x	x	10	2	6	0	45
x	x	2	7	8	0	70
0	40 - 40 = 0	50	30	45	5

Искомый элемент равен c₂₃=0. Для этого элемента запасы равны 15, потребности 50. Поскольку минимальным является 15, то вычитаем его.



x₂₃ = min(15,50) = 15.

7	x	x	x	x	x	0
5	7	0	x	x	x	15 - 15 = 0
x	x	10	2	6	0	45
x	x	2	7	8	0	70
0	0	50 - 15 = 35	30	45	5

Искомый элемент равен c₃₃=10. Для этого элемента запасы равны 45, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x₃₃ = min(45,35) = 35.

7	x	x	x	x	x	0
5	7	0	x	x	x	0
x	x	10	2	6	0	45 - 35 = 10
x	x	x	7	8	0	70
0	0	35 - 35 = 0	30	45	5

Искомый элемент равен c₃₄=2. Для этого элемента запасы равны 10, потребности 30. Поскольку минимальным является 10, то вычитаем его.

x₃₄ = min(10,30) = 10.

7	x	x	x	x	x	0
5	7	0	x	x	x	0
x	x	10	2	x	x	10 - 10 = 0
x	x	x	7	8	0	70
0	0	0	30 - 10 = 20	45	5

Искомый элемент равен c₄₄=7. Для этого элемента запасы равны 70, потребности 20. Поскольку минимальным является 20, то вычитаем его.

x₄₄ = min(70,20) = 20.

7	x	x	x	x	x	0
5	7	0	x	x	x	0
x	x	10	2	x	x	0
x	x	x	7	8	0	70 - 20 = 50
0	0	0	20 - 20 = 0	45	5

Искомый элемент равен c₄₅=8. Для этого элемента запасы равны 50, потребности 45. Поскольку минимальным является 45, то вычитаем его.

x₄₅ = min(50,45) = 45.

7	x	x	x	x	x	0
5	7	0	x	x	x	0
x	x	10	2	x	x	0
x	x	x	7	8	0	50 - 45 = 5
0	0	0	0	45 - 45 = 0	5

Искомый элемент равен c₄₆=0. Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x₄₆ = min(5,5) = 5.

7	x	x	x	x	x	0
5	7	0	x	x	x	0
x	x	10	2	x	x	0
x	x	x	7	8	0	5 - 5 = 0
0	0	0	0	0	5 - 5 = 0

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[40]	0[15]	2	3	0	60
3	1	4	10[35]	2[10]	6	0	45
4	3	4	2	7[20]	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₂ + v₁ = 5; 7 + u₂ = 5; u₂ = -2

u₂ + v₂ = 7; -2 + v₂ = 7; v₂ = 9

u₂ + v₃ = 0; -2 + v₃ = 0; v₃ = 2

u₃ + v₃ = 10; 2 + u₃ = 10; u₃ = 8

u₃ + v₄ = 2; 8 + v₄ = 2; v₄ = -6

u₄ + v₄ = 7; -6 + u₄ = 7; u₄ = 13

u₄ + v₅ = 8; 13 + v₅ = 8; v₅ = -5

u₄ + v₆ = 0; 13 + v₆ = 0; v₆ = -13

	v1=7	v2=9	v3=2	v4=-6	v5=-5	v6=-13
u1=0	7[20]	3	4	8	6	0
u2=-2	5[5]	7[40]	0[15]	2	3	0
u3=8	1	4	10[35]	2[10]	6	0
u4=13	3	4	2	7[20]	8[45]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 9 > 3; ?₁₂ = 0 + 9 - 3 = 6

(3;1): 8 + 7 > 1; ?₃₁ = 8 + 7 - 1 = 14

(3;2): 8 + 9 > 4; ?₃₂ = 8 + 9 - 4 = 13

(4;1): 13 + 7 > 3; ?₄₁ = 13 + 7 - 3 = 17

(4;2): 13 + 9 > 4; ?₄₂ = 13 + 9 - 4 = 18

(4;3): 13 + 2 > 2; ?₄₃ = 13 + 2 - 2 = 13

max(6,14,13,17,18,13) = 18

Выбираем максимальную оценку свободной клетки (4;2): 4

Для этого в перспективную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[40][-]	0[15][+]	2	3	0	60
3	1	4	10[35][-]	2[10][+]	6	0	45
4	3	4[+]	2	7[20][-]	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[20]	0[35]	2	3	0	60
3	1	4	10[15]	2[30]	6	0	45
4	3	4[20]	2	7	8[45]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₂ + v₁ = 5; 7 + u₂ = 5; u₂ = -2

u₂ + v₂ = 7; -2 + v₂ = 7; v₂ = 9

u₄ + v₂ = 4; 9 + u₄ = 4; u₄ = -5

u₄ + v₅ = 8; -5 + v₅ = 8; v₅ = 13

u₄ + v₆ = 0; -5 + v₆ = 0; v₆ = 5

u₂ + v₃ = 0; -2 + v₃ = 0; v₃ = 2

u₃ + v₃ = 10; 2 + u₃ = 10; u₃ = 8

u₃ + v₄ = 2; 8 + v₄ = 2; v₄ = -6

	v1=7	v2=9	v3=2	v4=-6	v5=13	v6=5
u1=0	7[20]	3	4	8	6	0
u2=-2	5[5]	7[20]	0[35]	2	3	0
u3=8	1	4	10[15]	2[30]	6	0
u4=-5	3	4[20]	2	7	8[45]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 9 > 3; ?₁₂ = 0 + 9 - 3 = 6

(1;5): 0 + 13 > 6; ?₁₅ = 0 + 13 - 6 = 7

(1;6): 0 + 5 > 0; ?₁₆ = 0 + 5 - 0 = 5

(2;5): -2 + 13 > 3; ?₂₅ = -2 + 13 - 3 = 8

(2;6): -2 + 5 > 0; ?₂₆ = -2 + 5 - 0 = 3

(3;1): 8 + 7 > 1; ?₃₁ = 8 + 7 - 1 = 14

(3;2): 8 + 9 > 4; ?₃₂ = 8 + 9 - 4 = 13

(3;5): 8 + 13 > 6; ?₃₅ = 8 + 13 - 6 = 15

(3;6): 8 + 5 > 0; ?₃₆ = 8 + 5 - 0 = 13

max(6,7,5,8,3,14,13,15,13) = 15

Выбираем максимальную оценку свободной клетки (3;5): 6

Для этого в перспективную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[20][-]	0[35][+]	2	3	0	60
3	1	4	10[15][-]	2[30]	6[+]	0	45
4	3	4[20][+]	2	7	8[45][-]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[5]	0[50]	2	3	0	60
3	1	4	10	2[30]	6[15]	0	45
4	3	4[35]	2	7	8[30]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₂ + v₁ = 5; 7 + u₂ = 5; u₂ = -2

u₂ + v₂ = 7; -2 + v₂ = 7; v₂ = 9

u₄ + v₂ = 4; 9 + u₄ = 4; u₄ = -5

u₄ + v₅ = 8; -5 + v₅ = 8; v₅ = 13

u₃ + v₅ = 6; 13 + u₃ = 6; u₃ = -7

u₃ + v₄ = 2; -7 + v₄ = 2; v₄ = 9

u₄ + v₆ = 0; -5 + v₆ = 0; v₆ = 5

u₂ + v₃ = 0; -2 + v₃ = 0; v₃ = 2

	v1=7	v2=9	v3=2	v4=9	v5=13	v6=5
u1=0	7[20]	3	4	8	6	0
u2=-2	5[5]	7[5]	0[50]	2	3	0
u3=-7	1	4	10	2[30]	6[15]	0
u4=-5	3	4[35]	2	7	8[30]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 9 > 3; ?₁₂ = 0 + 9 - 3 = 6

(1;4): 0 + 9 > 8; ?₁₄ = 0 + 9 - 8 = 1

(1;5): 0 + 13 > 6; ?₁₅ = 0 + 13 - 6 = 7

(1;6): 0 + 5 > 0; ?₁₆ = 0 + 5 - 0 = 5

(2;4): -2 + 9 > 2; ?₂₄ = -2 + 9 - 2 = 5

(2;5): -2 + 13 > 3; ?₂₅ = -2 + 13 - 3 = 8

(2;6): -2 + 5 > 0; ?₂₆ = -2 + 5 - 0 = 3

max(6,1,7,5,5,8,3) = 8

Выбираем максимальную оценку свободной клетки (2;5): 3

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».



	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7[5][-]	0[50]	2	3[+]	0	60
3	1	4	10	2[30]	6[15]	0	45
4	3	4[35][+]	2	7	8[30][-]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (2,5 > 2,2 > 4,2 > 4,5).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5]	7	0[50]	2	3[5]	0	60
3	1	4	10	2[30]	6[15]	0	45
4	3	4[40]	2	7	8[25]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₂ + v₁ = 5; 7 + u₂ = 5; u₂ = -2

u₂ + v₃ = 0; -2 + v₃ = 0; v₃ = 2

u₂ + v₅ = 3; -2 + v₅ = 3; v₅ = 5

u₃ + v₅ = 6; 5 + u₃ = 6; u₃ = 1

u₃ + v₄ = 2; 1 + v₄ = 2; v₄ = 1

u₄ + v₅ = 8; 5 + u₄ = 8; u₄ = 3

u₄ + v₂ = 4; 3 + v₂ = 4; v₂ = 1

u₄ + v₆ = 0; 3 + v₆ = 0; v₆ = -3

	v1=7	v2=1	v3=2	v4=1	v5=5	v6=-3
u1=0	7[20]	3	4	8	6	0
u2=-2	5[5]	7	0[50]	2	3[5]	0
u3=1	1	4	10	2[30]	6[15]	0
u4=3	3	4[40]	2	7	8[25]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(3;1): 1 + 7 > 1; ?₃₁ = 1 + 7 - 1 = 7

(4;1): 3 + 7 > 3; ?₄₁ = 3 + 7 - 3 = 7

(4;3): 3 + 2 > 2; ?₄₃ = 3 + 2 - 2 = 3

max(7,7,3) = 7

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5[5][-]	7	0[50]	2	3[5][+]	0	60
3	1[+]	4	10	2[30]	6[15][-]	0	45
4	3	4[40]	2	7	8[25]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7[20]	3	4	8	6	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[5]	4	10	2[30]	6[10]	0	45
4	3	4[40]	2	7	8[25]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₃ + v₁ = 1; 7 + u₃ = 1; u₃ = -6

u₃ + v₄ = 2; -6 + v₄ = 2; v₄ = 8

u₃ + v₅ = 6; -6 + v₅ = 6; v₅ = 12

u₂ + v₅ = 3; 12 + u₂ = 3; u₂ = -9

u₂ + v₃ = 0; -9 + v₃ = 0; v₃ = 9

u₄ + v₅ = 8; 12 + u₄ = 8; u₄ = -4

u₄ + v₂ = 4; -4 + v₂ = 4; v₂ = 8

u₄ + v₆ = 0; -4 + v₆ = 0; v₆ = 4

	v1=7	v2=8	v3=9	v4=8	v5=12	v6=4
u1=0	7[20]	3	4	8	6	0
u2=-9	5	7	0[50]	2	3[10]	0
u3=-6	1[5]	4	10	2[30]	6[10]	0
u4=-4	3	4[40]	2	7	8[25]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 8 > 3; ?₁₂ = 0 + 8 - 3 = 5

(1;3): 0 + 9 > 4; ?₁₃ = 0 + 9 - 4 = 5

(1;5): 0 + 12 > 6; ?₁₅ = 0 + 12 - 6 = 6

(1;6): 0 + 4 > 0; ?₁₆ = 0 + 4 - 0 = 4

(4;3): -4 + 9 > 2; ?₄₃ = -4 + 9 - 2 = 3

max(5,5,6,4,3) = 6

Выбираем максимальную оценку свободной клетки (1;5): 6

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7[20][-]	3	4	8	6[+]	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[5][+]	4	10	2[30]	6[10][-]	0	45
4	3	4[40]	2	7	8[25]	0[5]	70
Потребности	25	40	50	30	45	5



Цикл приведен в таблице (1,5 > 1,1 > 3,1 > 3,5).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7[10]	3	4	8	6[10]	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3	4[40]	2	7	8[25]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₃ + v₁ = 1; 7 + u₃ = 1; u₃ = -6

u₃ + v₄ = 2; -6 + v₄ = 2; v₄ = 8

u₁ + v₅ = 6; 0 + v₅ = 6; v₅ = 6

u₂ + v₅ = 3; 6 + u₂ = 3; u₂ = -3

u₂ + v₃ = 0; -3 + v₃ = 0; v₃ = 3

u₄ + v₅ = 8; 6 + u₄ = 8; u₄ = 2

u₄ + v₂ = 4; 2 + v₂ = 4; v₂ = 2

u₄ + v₆ = 0; 2 + v₆ = 0; v₆ = -2



	v1=7	v2=2	v3=3	v4=8	v5=6	v6=-2
u1=0	7[10]	3	4	8	6[10]	0
u2=-3	5	7	0[50]	2	3[10]	0
u3=-6	1[15]	4	10	2[30]	6	0
u4=2	3	4[40]	2	7	8[25]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;4): -3 + 8 > 2; ?₂₄ = -3 + 8 - 2 = 3

(4;1): 2 + 7 > 3; ?₄₁ = 2 + 7 - 3 = 6

(4;3): 2 + 3 > 2; ?₄₃ = 2 + 3 - 2 = 3

(4;4): 2 + 8 > 7; ?₄₄ = 2 + 8 - 7 = 3

max(3,6,3,3) = 6

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7[10][-]	3	4	8	6[10][+]	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[+]	4[40]	2	7	8[25][-]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (4,1 > 4,5 > 1,5 > 1,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3	4	8	6[20]	0	20
2	5	7	0[50]	2	3[10]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[40]	2	7	8[15]	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₅ = 6; 0 + v₅ = 6; v₅ = 6

u₂ + v₅ = 3; 6 + u₂ = 3; u₂ = -3

u₂ + v₃ = 0; -3 + v₃ = 0; v₃ = 3

u₄ + v₅ = 8; 6 + u₄ = 8; u₄ = 2

u₄ + v₁ = 3; 2 + v₁ = 3; v₁ = 1

u₃ + v₁ = 1; 1 + u₃ = 1; u₃ = 0

u₃ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₄ + v₂ = 4; 2 + v₂ = 4; v₂ = 2

u₄ + v₆ = 0; 2 + v₆ = 0; v₆ = -2

	v1=1	v2=2	v3=3	v4=2	v5=6	v6=-2
u1=0	7	3	4	8	6[20]	0
u2=-3	5	7	0[50]	2	3[10]	0
u3=0	1[15]	4	10	2[30]	6	0
u4=2	3[10]	4[40]	2	7	8[15]	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(4;3): 2 + 3 > 2; ?₄₃ = 2 + 3 - 2 = 3

Выбираем максимальную оценку свободной клетки (4;3): 2

Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	3	4	8	6[20]	0	20
2	5	7	0[50][-]	2	3[10][+]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[40]	2[+]	7	8[15][-]	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (4,3 > 4,5 > 2,5 > 2,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3	4	8	6[20]	0	20
2	5	7	0[35]	2	3[25]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[40]	2[15]	7	8	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₅ = 6; 0 + v₅ = 6; v₅ = 6

u₂ + v₅ = 3; 6 + u₂ = 3; u₂ = -3

u₂ + v₃ = 0; -3 + v₃ = 0; v₃ = 3

u₄ + v₃ = 2; 3 + u₄ = 2; u₄ = -1

u₄ + v₁ = 3; -1 + v₁ = 3; v₁ = 4

u₃ + v₁ = 1; 4 + u₃ = 1; u₃ = -3

u₃ + v₄ = 2; -3 + v₄ = 2; v₄ = 5

u₄ + v₂ = 4; -1 + v₂ = 4; v₂ = 5

u₄ + v₆ = 0; -1 + v₆ = 0; v₆ = 1

	v1=4	v2=5	v3=3	v4=5	v5=6	v6=1
u1=0	7	3	4	8	6[20]	0
u2=-3	5	7	0[35]	2	3[25]	0
u3=-3	1[15]	4	10	2[30]	6	0
u4=-1	3[10]	4[40]	2[15]	7	8	0[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 5 > 3; ?₁₂ = 0 + 5 - 3 = 2

(1;6): 0 + 1 > 0; ?₁₆ = 0 + 1 - 0 = 1

max(2,1) = 2

Выбираем максимальную оценку свободной клетки (1;2): 3

Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	3[+]	4	8	6[20][-]	0	20
2	5	7	0[35][-]	2	3[25][+]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[40][-]	2[15][+]	7	8	0[5]	70
Потребности	25	40	50	30	45	5

Цикл приведен в таблице (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 5) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	3[20]	4	8	6	0	20
2	5	7	0[15]	2	3[45]	0	60
3	1[15]	4	10	2[30]	6	0	45
4	3[10]	4[20]	2[35]	7	8	0[5]	70
Потребности	25	40	50	30	45	5

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₄ + v₂ = 4; 3 + u₄ = 4; u₄ = 1

u₄ + v₁ = 3; 1 + v₁ = 3; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₄ = 2; -1 + v₄ = 2; v₄ = 3

u₄ + v₃ = 2; 1 + v₃ = 2; v₃ = 1

u₂ + v₃ = 0; 1 + u₂ = 0; u₂ = -1

u₂ + v₅ = 3; -1 + v₅ = 3; v₅ = 4

u₄ + v₆ = 0; 1 + v₆ = 0; v₆ = -1

	v1=2	v2=3	v3=1	v4=3	v5=4	v6=-1
u1=0	7	3[20]	4	8	6	0
u2=-1	5	7	0[15]	2	3[45]	0
u3=-1	1[15]	4	10	2[30]	6	0
u4=1	3[10]	4[20]	2[35]	7	8	0[5]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450

Анализ оптимального плана.

Из 1-го склада необходимо часть груза (20) направить в 2-й магазин.

Из 2-го склада необходимо груз направить в 3-й магазин (15), в 5-й магазин (45)

Из 3-го склада необходимо груз направить в 1-й магазин (15), в 4-й магазин (30)

Из 4-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (20), в 3-й магазин (35)

На 4-ом складе остался невостребованным груз в количестве 5 ед.