Меню Главная Юридпсихология Этика эстетика Электротехника Эктеория Физика Управление персоналом Уголовный процесс Уголовное право Схемотехника Стратегический менеджмент САПР Ресторанно-гостиничный бизнес бытовое обслуживан Реклама и PR Режущий инструмент Неопределено Метрология Матметоды в эк-ке Исторические личности Искусство и культура Информатика Иностранные языки Гражданское процессуальное право Гражданское право Государственное регулирование и налогообложение Сонник Карта сайта Поиск По всему сайту Статьи Комментарии Файлы Форум Гостевая Ссылки Новости	Решение задач симплекс-методом 3-я итерация cj p0 x0 x1 х2 х3 х4 х5 х6 х7 0 х4 0.6 0.0 0.0 0.0 1.0 -0.1 -0.6 0.4 8 х1 26.3 1.0 0.0 0.0 0.0 -0.2 -0.3 0.4 15 х2 24.3 0.0 1.0 0.0 0.0 0.1 -0.3 0.0 10 х3 3.6 0.0 0.0 1.0 0.0 -0.1 0.4 -0.6 Zj - Cj 537.2 0.0 0.0 0.0 0.0 -1.7 -1.2 -1.9 Подставив значения неизвестных в исходные неравенства, получаем: 1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50 4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140 1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127 0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80 Стоимость сырья при этом будет минимальной и составит: F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2 ЗАДАЧА 3 Составить оптимальный план перевозок пищевых продуктов от 4-х по­ставщиков к 6-ти потребителям. Поставщики (П),  потребители (М), объемы вы­воза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице. Поставщики Потребители Объемы вывоза, т М1 М2 М3 М4 М5 М6 П1 24 30 42 15 39 21 144 П2 9 24 30 33 27 29 148 П3 24 22 20 45 21 23 76 П4 11 36 27 40 30 8 132 Объемы завоза, т 92 84 80 112 96 36   Решение задачи начинается с распределения у имеющихся у поставщиков объемов вывоза между потребителями с учетом объемов завоза. Для первоначального распределения используются способы: северо-западного угла, наименьшего элемента по строке, наименьшего элемента по столбцу, наименьшего элемента матрицы. Способ северо-западного угла состоит в том, что распре­деление объемов вывоза производится, начиная с верхнего лево­го угла таблицы и кончая нижним углом ее. Результаты распреде­ления показаны в таблице.
Поставщики и объемы вывоза, т		Потребители и объемы завоза						Потенциалы строк
		М1	М2	М3	М4	М5	М6
		92	84	80	112	96	36
П1	144	24	30	42	15	39	21	0
		92	52
П2	148	9	24	30	33	27	29	-6
			32	80	36
П3	76	24	22	20	45	21	23	6
					76	0
П4	132	11	36	27	40	30	8	15
						96	36
Потенциалы столбцов		24	30	36	39	15	-7

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

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

Для решения задач методом потенциалов исходный план дол­жен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчи­тать потенциалы, а без них нельзя проверить план на оптималь­ность.

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

Элемент заполненной клетки должен равняться сумме потен­циалов строки и столбца, на пересечении которых находится эта заполненная клетка.

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

Обозначив потенциалы строк ui, потенциалы столбцов Vj, элементы заполнения клеток , можно записать порядок расчета потенциалов для общего случая.

Из основного требования  = ui + Vj вытекает:

ui =  - Vj;       Vj =  - ui

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

Потенциалы показаны в таблице.

После того, как по строкам и столбцам определены потенциа­лы, с их помощью выясняется, является ли план оптимальным, и если нет, то как его можно улучшить. С этой целью для каждой свободной клетки вычисляется сумма потенциалов строк и столбцов, на пересечении которых находится эта клетка.

Сравнение суммы потенциалов с величиной элемента в свобод­ных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.

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

Иными словами, если характеристика, значение которой равно разности  - (ui + Vj), положительная, то свободная мет­ка не заполняется при решении задачи на минимум функции.

Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неиз­менным.

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

Шифры клеток

П1-М3

П1-М4

П1-М5

П1-M6

П2-М1

П2-М5

П2-М6

П3-М1

П3-М2

П3-М3

П3-М6

П4-М1

П4-М2

П4-М3

П4-М4

Суммы потенциалов

36

39

15

-7

18

9

-13

30

36

42

-1

39

45

51

54

Значение элементов

42

15

39

21

9

27

29

24

22

20

23

11

36

Страницы: 1, 2, 3, 4, 5, 6

     Наверх    

© 2009 Все права защищены.