147246 (758481), страница 2
Текст из файла (страница 2)
Алгоритм вычислений симплекс-методом состоит в следующем.
Шаг 1. Выбираем в индексной строке наибольшее отрицательное число. Ему соответствует ключевой столбец. В таблице 2 это столбец х32 с числом 17.
Шаг 2. Определяем ключевую строку. Для этого разделим числа столбца свободных членов на соответствующие им положительные числа ключевого столбца: 10/0 = ∞; 15/1 = 15; 150/0= ∞; 200/17 = 11,76; 250/0 = ∞. Из всех полученных частных выбираем наименьшее (200/17 = 11,76). Оно определяет ключевую строку.
На пересечении ключевой строки и ключевого столбца находится ключевое число (17).
Шаг 3. Переходим к построению следующей симплекс-таблицы, в которой в первую очередь заполняется главная строка. Главная строка располагается там, где в предыдущей симплекс-таблице находилась ключевая строка, а числа главной строки определяются путем деления чисел ключевой строки на ключевое число. Вместо прежнего переменного в столбце переменных записывается переменное соответствующего ключевого столбца. Поэтому для главной строки таблицы 3 в столбце переменных указано 11,76.
В том столбце, который в предыдущей таблице был ключевым, все клетки заполняются нулями, за исключением клетки, где находилось ключевое число. Там всегда будем иметь 1 по расчету чисел главной строки. Те столбцы, у которых в клетках ключевой строки (см. табл. 2) записаны нули, переписываются без изменений. Аналогично правило и для строк. Если в ключевом столбце строке соответствует нуль, то она переписывается в следующую таблицу без изменений.
Для остальных клеток (в столбце свободных членов клетка строки х2, х3, х2, х5, х2 и в индексной строке клетка столбца х32) определяются производные числа (Пр) по правилу:
Пр = Вч – КсКст/Кч,
где Вч – выбранное число;
Кс – соответствующее число в ключевой строке;
Кст – соответствующее число в ключевом столбце;
Кч – ключевое число.
Теперь известны все числа, и построение симплекс-таблицы (см. табл. 2) закончено. Так как в индексной строке еще сохранились отрицательные числа, то решение продолжается, повторяются все операции, описанные выше. Вычисления проводятся до той поры, пока в индексной строке одной из таблиц не окажутся числа больше или равные нулю. Опуская промежуточные решения, покажем сразу матрицу оптимального распределения (таблица 4).
В заключение можно отметить, что изложенным методом можно решать и другие задачи. Например, можно определить минимальное число автомобилей, необходимое для перевозки запланированного количества грузов. Для этого нужно отбросить ограничения по количеству автомобилей и ввести расчет по изложенной схеме до тех пор, пока не будет вывезен весь запланированный груз.
Исходная симплекс-таблица Таблица 2
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||||
| Х1 | 10 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | ||
| Х2 | 15 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | ||
| Х3 | 150 | 14 | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ||
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||
| Х5 | 200 | 0 | 0 | 0 | 0 | 15 | 17 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ||
| Х6 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| Индексная строка | ___ | -14 | -15 | -7 | -5 | -15 | -17 | -9 | -9 | 0 | 0 | 0 | 0 | 0 | 0 | ||
Промежуточная симплекс-таблица Таблица 3
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||
| Х1 | 10 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| Х2 | 3,24 | 0 | 1 | 0 | 1 | -0,88 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | -0,06 | 0 |
| Х3 | 150 | 14 | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Х32 | 11,76 | 0 | 0 | 0 | 0 | 0,88 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0,06 | 0 |
| Х6 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 1 |
| Индексная строка | __ | -14 | -15 | -7 | -5 | 0 | 0 | -9 | -9 | 0 | 0 | 0 | 0 | 0 | 0 |
Оптимальная симплекс-таблица Таблица 4
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||
| Х41 | 2,76 | 0 | 0 | 1 | 1,07 | 0,06 | 0 | 1 | 1,07 | 1 | 1,07 | -0,07 | 0 | -0,064 | 0 |
| Х12 | 3,24 | 0 | 1 | 0 | 1 | -0,82 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | -0,06 | 0 |
| Х11 | 7,25 | 1 | 0 | 0 | -1,07 | 0,94 | 0 | 0 | -1,07 | 0 | -1,07 | 0,07 | 0 | 0,064 | 0 |
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Х32 | 11,76 | 0 | 0 | 0 | 0 | 0,88 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0,06 | 0 |
| Х6 | 225,16 | 0 | 0 | -9 | -9,63 | -0,54 | 0 | 9 | -0,63 | -9 | -9,63 | -0,63 | 0 | 0,576 | 1 |
| Индексная строка | __ | 0 | 0 | 2 | 34,63 | 0,54 | 0 | 0 | 0,63 | 9 | 9,63 | 0,37 | 0 | 0,424 | 0 |
Литература
-
В.И. Николин, Е.Е. Витвицкий, С.М. Мочалин, Н.И. Ланьков «Основы теории автотранспортных систем ( грузовые автомобильные перевозки )»
-
В.И. Николин «Автотранспортный процесс и оптимизация его элементов»
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
