Учебное пособие: Организация пассажирских перевозок
Дальнейшие решения целесообразно выполнять в симплекс-таблицах (табл.1.3-1.6).
При этом, в базисном решении свободные неизвестные следует расположить по вертикали таблицы (их количество совместно с целевой функцией соответствует числу строк таблицы), а остальные неизвестные - по горизонтали таблицы ( 
).
3. Внести коэффициенты при неизвестных в уравнениях и целевой функции в верхние ячейки клеток табл.1.3 (исходный план).
4. Выбрать генеральный элемент. Для этого:
· найти в верхней строке симплекс-таблицы максимальный положительный элемент (4,04). Если в верхней строке симплекс-таблицы нет положительных элементов, то записанное в данной симплекс-таблице базисное решение будет оптимальным, т.е. уменьшить значение целевой функции при переходе от одного допустимого базисного решения к другому не представляется возможным;
· составить отношение свободных членов (первый столбец табл.1.3) к положительным коэффициентам выбранного столбца. В задаче: 23,60/1,20=19,67; 18,92/1,00=18,92; 12,08/0,92=13,13;
· выбрать среди найденных отношений наименьшее (13,13). Если наименьшее отношение достигается при нескольких значениях, то можно выбрать любое. Элемент выбранного столбца, которому соответствует наименьшее отношение, - генеральный элемент (в табл.1.3 клетка выделена жирной линией).
5. Найти значение, обратное генеральному элементу, внести его в правый угол клетки, содержащей генеральный элемент (1/0,92=1,09).
6. Все коэффициенты из верхних отделений строки, где расположен генеральный элемент, умножить на значение, обратное генеральному элементу, и поместить полученные произведения в соответствующие правые углы клеток той же строки (12,08´1,09=13,13; 0,62´1,09=0,67 и т.д.).
7. Умножить на значение, обратное генеральному элементу, со знаком «-» все коэффициенты (кроме генерального элемента) из левых углов клеток столбца, где расположен генеральный элемент, и поместить полученные произведения в соответствующие правые углы клеток этого же столбца (4,04´1,09= -4,39; 1,20´1,09= -1,30 и т.д.).
8. Выделить числа, находящиеся в левых углах клеток строки, где расположен генеральный элемент, и в правых углах клеток столбца, в котором содержится генеральный элемент.
9. Заполнить оставшиеся правые углы клеток числами, полученными перемножением соответствующих выделенных чисел (-4,39´12,08= -53,03; -4,39´0,62= -2,72;.....-1,30´12,08= -15,70 и т.д.).
10. Перейти к новому набору свободных неизвестных. Для этого:
- из правых углов клеток строки и столбца, на пересечении которых находится генеральный элемент, перенести все числа в левые углы соответствующей строки и столбца последующей таблицы (первая итерация - табл.1.4);
- в левые углы остальных клеток последующей таблицы записать числа, равные алгебраической сумме чисел из левого и правого углов соответствующей клетки предыдущей таблицы (-53,03+205,20=152,17; -2,72+1,91= -0,81;...…. –15,70+23,60=7,90 и т.д.);
- поменять местами переменные на пересечении строки и столбца, где расположен генеральный элемент ( х 5 и х 10 ).
11. Если в верхней строке новой таблицы все коэффициенты при свободных неизвестных отрицательны, то полученный результат является оптимальным, план не подлежит улучшению, а целевая функция принимает свое наименьшее значение. В противном случае решение задачи следует продолжить для чего необходимо вновь перейти к п.4.
При решении задачи оптимальный план формирования пассажирских поездов был получен после второй итерации (табл.1.6). Он предусматривает следующие назначения:
- А-Г (х 2 ) - 8 поездов;
- А-В (х 3 ) - 1 поезд;
- А-Б (х 4 ) - 9 поездов;
- Б-Д (х 5 ) - 13 поездов.
Таблица 1.3
Базисное решение
| -x1 | -x2 | -x3 | -x5 | -x6 | -x8 | |||||||||
| F | 205,2 | 1,91 | 2,12 | 1,29 | 4,04 | 2,10 | 1,32 | |||||||
| -53,03 | -2,72 | 0 | 0 | -4,39 | 0 | -4,39 | ||||||||
| x4 | 15,00 | 0,62 | 0,69 | 0,77 | 0 | 0 | 0 | |||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||
| x7 | 23,60 | 0,80 | 0,90 | 1,00 | 1,20 | 1,10 | 0 | |||||||
| -15,70 | -0,81 | 0 | 0 | -1,30 | 0 | -1,30 | ||||||||
| x9 | 18,92 | 0,67 | 0,75 | 0 | 1,00 | 0,92 | 1,08 | |||||||
| -13,18 | -0,68 | 0 | 0 | -1,09 | 0 | -1,09 | ||||||||
| x10 | 12,08 | 0,62 | 0 | 0 | 0,92 | 0 | 1,00 | |||||||
| 13,13 | 0,67 | 0 | 0 | 1,09 | 0 | 1,09 | ||||||||
Таблица 1.4
Первая итерация
| -x1 | -x2 | -x3 | -x10 | -x6 | -x8 | ||||||||||
| F | 152,17 | -0,81 | 2,12 | 1,29 | -4,39 | 2,10 | 3,07 | ||||||||
| -16,47 | 0,03 | -2,87 | 0 | 3,13 | 2,64 | 0,03 | |||||||||
| x4 | 15,00 | 0,62 | 0,69 | 0,77 | 0 | 0 | 0 | ||||||||
| -5,28 | 0,01 | -0,92 | 0 | 1,00 | -0,85 | 0,01 | |||||||||
| x7 | 7,90 | 0,80 | 0,90 | 1,00 | -1,30 | 1,10 | -1,30 | ||||||||
| -6,89 | 0,01 | 1,20 | 0 | 1,30 | -1,10 | 0,01 | |||||||||
| x9 | 5,74 | -0,01 | 0,75 | 0 | -1,09 | 0,92 | -0,01 | ||||||||
| 7,65 | -0,01 | 1,33 | 0 | -1,45 | 1,23 | -0,01 | |||||||||
| x5 | 13,13 | 0,67 | 0 | 0 | 1,09 | 0 | 1,09 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||||
Таблица 1.5
Вторая итерация
| -x1 | -x9 | -x3 | -x10 | -x6 | -x8 | ||||||||||
| F | 135,70 | -0,78 | -2,87 | 1,29 | -1,26 | -0,54 | -3,04 | ||||||||
| -1,30 | -1,04 | 1,55 | -1,29 | 0 | 0 | 1,66 | |||||||||
| x4 | 9,72 | 0,63 | -0,92 | 0,77 | 1,00 | -0,85 | 0,01 | ||||||||
| -0,78 | -0,63 | 0,92 | -0,77 | 0 | 0 | 0,99 | |||||||||
| x7 | 1,01 | 0,81 | -1,25 | 1,00 | 0 | 0 | -1,29 | ||||||||
| 1,01 | 0,81 | -1,27 | 1,00 | 0 | 0 | -1,29 | |||||||||
| x2 | 7,65 | -0,01 | 1,33 | 0 | -1,45 | 1,23 | -0,01 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||||
| x5 | 13,13 | 0,67 | 0 | 0 | 1,09 | 0 | 1,09 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||||
При этом целевая функция уменьшится на 70,8 и составит 134,4 стоимостных единицы.