Знание — сила. Библиотека научных работ. ~ Портал библиофилов и любителей литературы ~

Меню Главная Биология и химия Иностранные языки и языкознание История и исторические личности Коммуникации связь цифровые приборы и радиоэлектроника Краеведение и этнография Кулинария и продукты питания Маркетинг реклама и торговля Мировая экономика МЭО Не Российское законодательство Немецкий Неопределено Нотариат Общениеэтика семья брак Основы права Охрана окружающей среды экология Философия Финансовое право Финансовый менеджмент финансовая математика Финансы деньги кредит Французский Хозяйственное право Цифровые устройства Этика эстетика Блог Карта сайта Поиск По всему сайту Статьи Комментарии Файлы Форум Гостевая Ссылки Новости	Решение задач симплекс-методом 0.0 0 х7 -6.4 0.0 0.0 -1.8 0.0 0.2 -0.8 1.0 Zj - Cj 525.3 0.0 0.0 -3.3 0.0 -1.3 -2.7 0.0 После преобразования элементов в итоговом столбце осталось еще одно отрицательное число в строке х7. Эта строка будет принята за ключевую для по­следующего расчета. Ключевой столбец определяется по наименьшему отноше­нию элементов целевой строки к элементам ключевой строки. Им будет столбец х3. Вводим этот вид сырья в программу вместо неизвестного х7. По общим пра­вилам преобразуем элементы матрицы. В таблице записаны преобразованные числа, полученные на 3-й итерации. В итоговом столбце все отрицательные числа исчезли, значит полученный план является допустимым и одновременно оптимальным. Вывод о том, что план по­лучен оптимальный, позволяют сделать элементы целевой строки. Все они отри­цательны или равны нулю, что свидетельствует об оптимальности результата при решении задач на минимум целевой функции. 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

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

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

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

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

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

     Наверх    

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