организация пассажирских перевозок в дальнем и местном сообщении. пояснительная записка. Компанииперевозчики могут осуществлять такие виды услуг
 Скачать 126.77 Kb.
|
 min Следовательно, если осваивать пассажиропоток поездами, обращающимися между соседними станциями, их число будет строго соответствовать густоте пассажиропотока по каждому участку, а суммарные затраты на выполнение перевозок могут быть оценены в 118,1 стоимостную единицу. Однако этот вариант может быть улучшен. Дальнейшие решения целесообразно выполнять в симплекс-таблицах. Симплекс-метод. Решение прямой задачи линейного программирования симплексным методом, с использованием симплексной таблицы . Определяется минимальное значение целевой функции: F(X) = 5,1х1+4,8х2+3,5х3+2,7х4+3,2х5+2,8х6+0,9х7+3,4х8+2,7х9+1,8х10 При следующих условиях-ограничений: 0,8х1+0,9х2+1х3+1,2х4 ≥ 22,1 0,8х1 + 0,9х2+1х3+0,9х5+0,7х6+1,1х7 ≥ 30,8 0,8х1+0,9х2+0,9х5+0,7х6+1,1х8+1,3х9 ≥ 31,8 0,8х1+0,9х5+0,9х8+1,3х10 ≥ 23,5 Для построения первого опорного плана систему неравенств необходимо привести к системе уравнений путем введения дополнительных переменных. В первом, втором, третьем и четвертом неравенстве смысла (≥) вводится базисная переменная x11, x12, x13, x14 со знаком минус, соответственно. 0,8x1 + 0,9x2 + 1x3 + 1,2x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 -1x11 + 0x12 + + 0x13 + 0x14 = 22,1 0,8x1 + 0,9x2 + 1x3 + 0x4 + 0,9x5 +0,7x6 + 1,1x7 + 0x8 + 0x9 + 0x10 + 0x11-1x12 + + 0x13 + 0x14 = 30,8 0,8x1 + 0,9x2 + 0x3 + 0x4 + 0,9x5 + 0,7x6 + 0x7 + 1,1x8 + 1,3x9 + 0x10 + 0x11 + + 0x12 - 1x13 + 0x14 =31,8 0,8x1 + 0x2 + 0x3 + 0x4 + 0,9x5 + 0x6 + 0x7 + 1,1x8 + 0x9 + 1,2x10 + 0x11 + 0x12 + + 0x13-1x14 = 23,5 Все строки умножаются на (-1) и выбирается первоначальный опорный план. -0,8x1- 0,9x2 -1x3- 1,2x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 1x11 + 0x12 + 0x13+ +0x14 = -22,1 – 0,8x1-0,9x2-1x3 + 0x4-0,9x5-0,7x6-1,1x7 + 0x8 + 0x9 + 0x10 + 0x11 + 1x12 + 0x13 + + 0x14 = -30,8 – 0,8x1-0,9x2 + 0x3 + 0x4-0,9x5-0,7x6 + 0x7-1,1x8-1,3x9 + 0x10 + 0x11 + 0x12 + 1x13 + +0x14 =-31,8 – 0,8x1 + 0x2 + 0x3 + 0x4-0,9x5 + 0x6 + 0x7-1,1x8 + 0x9-1,2x10 + 0x11 + 0x12 + 0x13 + +1x14 = -23,5 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид таблицы 1.3. Таблица 1.3
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Необходимо решить систему уравнений относительно базисных переменных: x11, x12, x13, x14. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0;0;0;0;0;0;0;0;0;0;-22,1;-30,8;-31,8;-23,5) Базисное решение, представлено в таблице 1.4, называется допустимым, если оно неотрицательно. Таблица 1.4
1. Проверка критерия оптимальности. План 0 в симплексной таблице является псевдопланом, поэтому определяются ведущие строка и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных требуется выбрать наибольший по модулю. Ведущей будет вторая строка, а переменную x13 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует девятому столбцу, т.е. переменную x9 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (1,3), представленный в таблице 1.5. Таблица 1.5
4. Пересчет симплекс-таблицы 1.6. Выполняется преобразование симплексной таблицы методом Жордано-Гаусса. Таблица 1.6
1. Проверка критерия оптимальности. План 1 в симплексной таблице является псевдопланом, поэтому определяются ведущие строка и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных требуется выбрать наибольший по модулю. Ведущей будет вторая строка, а переменную x12 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x4 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1,1) представленный в таблице 1.7. Таблица 1.7
4. Пересчет симплекс-таблицы 1.8. Выполняется преобразование симплексной таблицы методом Жордано-Гаусса. Таблица 1.8
1. Проверка критерия оптимальности. План 2 в симплексной таблице является псевдопланом, поэтому определяются ведущие строка и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных требуется выбрать наибольший по модулю. Ведущей четвертая строка, а переменную x14 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует десятому столбцу, т.е. переменную x10 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1,2) представленный в таблице 1.9. Таблица 1.9
4. Пересчет симплекс-таблицы 1.10. Выполняется преобразование симплексной таблицы методом Жордано-Гаусса. Таблица 1.10
1. Проверка критерия оптимальности. План 3 в симплексной таблице является псевдопланом, поэтому определяются ведущие строка и столбец. 2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных требуется выбрать наибольший по модулю. Ведущей будет первая строка, а переменную x11 следует вывести из базиса. 3. Определение новой базисной переменной. Минимальное значение θ соответствует четвертому столбцу, т.е. переменную x4 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1,2) представленный в таблице 1.11. Таблица 1.11
4. Пересчет симплекс-таблицы 1.12. Выполняется преобразование симплексной таблицы методом Жордано-Гаусса. Таблица 1.12
В базисном столбце все элементы положительные. Основной алгоритм симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбирается максимальный по модулю элемент. В качестве ведущего выберется столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычисляется значение Di по строкам как частное от деления: bi / ai6 и из них выбирается наименьшее: |