|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Оптимизация сетевого графика по критериям «время – стоимость»
В реальных проектах каждая работа характеризуется не только временем, но и стоимостью выполнения. В этом случае полная стоимость проекта будет равна сумме стоимостей всех входящих в него работ. Могутбыть поставлены и решены следующие две задачи оптимизации сетевого графика по критериям «время-стоимость»: 1. Минимизация стоимости проекта при сохранении времени его выполнения tkp. 2. Минимизация времени выполнения tkp при заданной стоимости проекта. При оптимизации сетевого графика предполагается: 1) уменьшение продолжительности работ ведет к увеличению их стоимости; 2) для каждой работы (i, j) ее продолжительность t(i, j) лежит в пределах a(i, j) ≤ t (i, j) ≤ b(i, j), где а(i, j) – минимально возможная продолжительность работы; b(i, j)– максимально допустимая продолжительность выполнения работы; 3) стоимость С(i, j) работы заключена в пределах C max(i, j) и C min(i, j).
C(t)
Cmax(i, j)
C(i, j)
Cmin(i, j) ∆ C(i, j)
a(i, j) t(i, j) b(i, j) t
Рис. 3.3. Зависимость стоимости от времени выполнения проекта
Обычно применяют линейную модель зависимости затрат от времени (рис. 3.3). Тогда изменение стоимости работы ∆ С(i, j) при увеличении ее продолжительности на величину ∆ t(i, j) определяется соотношением ∆ С(i, j) = h(i, j) ⋅ ∆ t(i, j), (3.1) где h(i, j) показывает изменение затрат при изменении времени выполнения работы (i, j) на единицу и вычисляется по формуле
h (i, j) = tgα = Cmax (i, j) - Cmin (i, j)
b(i, j) - a(i, j)
. (3.2) Более точной будет нелинейная модель вида
или линейная логарифмическая модель
(3.3) ln C ( i , j ) = ln a − bln t ij . (3.4) Ниже будет использоваться линейная модель (3.1). Задача минимизации стоимости проекта Минимизация стоимости проекта при сохранении tkp достигается увеличением продолжительности выполнения некритических работ на основе использования их свободных резервов времени, т.к. они не влияют на ранние сроки начала последующих работ. Увеличение продолжительности работы (i, j) осуществляется на величину ∆ t ij до тех пор, пока не будет исчерпан весь свободный резерв времени, или не будет достигнуто максимально допустимое значение продолжительности работы в (i, j), т.е.
∆ t ij = min{ b ij − t ij , R c ( i , j )},
(3.5) ∆ C ij = h ij ⋅ ∆ t ij .
Полная стоимость проекта С = ∑ С(i, j) увеличивается на величину ∆ С = ∑ ∆ Cij. Пример 3. Провести минимизацию стоимости проекта, сетевой график которого при заданных значениях продолжительности а(i, j), tij, b(i, j), стоимости С(i, j) и коэффициентов затрат на ускорение hij представлен на рис. 3.4. Первоначальная стоимость проекта 1216 усл. р.
Рис. 3.4. Сетевой график проекта Решение. Исходные и расчетные значения представлены в табл. 3.3. Заметим, что в таблице приводятся только те работы, для которых Rс(i, j) > 0. В результате оптимизации стоимость нового проекта при том же времени выполнения снизилась на 293 единицы и стала равна 923, т.е. уменьшилась почти на 25%. В результате снижения стоимости проекта появились новые критические пути с tкр = 61: 0-1-3-4-7-10-11, 0-3-5-8-9-11, 0-1-3-4-6-7-10-11, 0-3-5-6-8-9-11 и т.д. В новом графике из 64 полных путей 28 путей будут критическими.
Таблица 3.3
Задача минимизации времени выполнения проекта Минимизация времени выполнения проекта возможна только за счет сокращения продолжительности выполнения работ, лежащих на критическом пути Lkp. При этом стоимость этих работ и всего проекта увеличится согласно соотношениям (3.1) и (3.6). Для решения этой задачи проводится расчет исходного сетевого графика, а затем выполняется его оптимизация. В начальном сетевом графике продолжительность всех работ может считаться равной максимальному значению (tij = bij). Далее выполняются следующие действия. 10. Составляется список всех полных путей ( алгоритм перебора). 20. Определяется длительность каждого полного пути. 30. Начиная с критических путей, строятся линейные графы всех полных путей с упорядочиванием по убыванию их длительности: T kp = T 1 > T 2 > T 3 > … > T n–1 > T n. Сверху над каждой работой записывается h ij, а снизу – (t ij – a ij) (возможное сокращение ее длительности). 40. Начиная с k = 1, на каждом шаге k составляется список всех критических путей {L k kp}. Обозначается их длительность через T к , а kp стоимость сетевого графика обозначается через Ск. Если все tij = aij, то расчеты на данном шаге закончены. Переход к 60. 50. Для путей списка {Lkkp} определяются работы, подлежащие сокращению по двум возможным вариантам 5.1 и 5.2. Вариант 5.1. Есть работы, общие для всех путей {Lkkp}. В этом случае выбирается одна общая работа для всех путей в {Lkkp}, для которой минимальна величина hij и продолжительность ее выполнения не равна минимальному сроку:
k
(3.7) ( i , j )∈ { I L kp , t ij > a ij }.
Определяется время сокращения длительности выбранной общей работы (р, q) в каждом пути {L k kp}по формуле
– T 2}, (3.8) т.е. сокращение длительности работы не больше ее минимального времени выполнения и не превышает длительности ближайшего к критическому пути T 2 (шаг 30), не вошедшего в список{L k kp}. Определяется новая
выбранной работы: рq = tрq – ∆ t. (3.9) Согласно (3.9), длительность всех путей {L k kp}, содержащих работу (р, q),
путей в {L k kp}: кр = Т кр – ∆ t. (3.10) С учетом изменения времени выполнения работ проводится пересчет длин всех полных путей:
> T 2 > T 3 > … > T n–1 > T n). Определяется новая стоимость сетевого графика Ск + 1 = Ск + hpq ∆ t. (3.11) Зависимость стоимости сетевого графика от длительности критического пути определяется по формуле
кр < t < Т к кр.
= a pq, то при решении задач (3.7) исключается работа (p, q), поскольку она не имеет больше резерва снижения. Увеличиваем шаг на единицу, т.е. полагаем k равным k + 1 и осуществляем переход к шагу 40 до тех пор, пока k ≠ n. Иначе идем к 60. Вариант 5.2. В списке {L k kp} нет общих работ. В каждом пути {L k kp} выбирается по одной работе с минимальным значением h ij;
, ( i , j )∈ { L k kp , t ij > a ij }. (3.13) Список этих работ обозначим через Q = {(p, q)}.Определяется длительность сокращения выбранных работ ∆ t по формуле (3.8) для всего списка Q.
для путей {L k kp} по формуле (3.10).
= T 1 > T 2 > T 3 > … > > Tn–1 > Tn) с учетом изменения времени выполнения работ. Определяется новая стоимость сетевого графика С k +1 = C k + ∆ t ⋅ ∑ h pq , (3.14) pq где сумма берется по всем выбранным работам. Зависимость стоимости сетевого графика от длительности критического пути определяется по формуле С (t) = C + (T k − t) ⋅ ∑ h pq , где Т
k kp pq
= a pq, исключаются при решении задачи (3.13), поскольку они не имеют больше резерва снижения. Увеличиваем шаг k на 1 (k + 1) и осуществляем переход к 40 до тех пор, пока k ≠ n. Иначе идем к 60. 60. На основе формул (3.12) и (3.15) строится график зависимости стоимости сетевого графика от длительности критического пути С = С(t). 70. Для определения минимального времени выполнения t* по заданной стоимости С* проекта решается уравнение вида C(t*) = С*. Сделаем ряд замечаний к данному алгоритму. Дополнительные затраты, связанные с сокращением времени выполнения проекта с t1 до t2, равны C(t2) – C(t1). Для учета шагов алгоритма следует вести таблицу длительности и стоимости работ и длительности полных путей. Другим вариантом данного алгоритма является случай, когда начальный сетевой график построен при минимальных сроках выполнения каждой работы, а затем последовательно увеличивают длину критического пути, увеличивая сроки выполнения некритических, а затем и критических работ по критерию максимума коэффициента напряженности hij. Пример 4. Провести минимизацию времени выполнения проекта при заданных затратах на его осуществление и построить зависимость стоимости от критического времени С = С(t). Исходные данные задачи сведены в табл. 3.4. Таблица 3.4.
Находим все полные пути сетевого графика и их длины: L1: 0 – 1 – 3 – 4 – 6 – 7 – 8, t(L1) = t кр = 99; L 2: 0 – 1 – 3 – 5 – 6 – 7 – 8, t(L 2) = 89; L 3: 0 – 1 – 2 – 7 – 8, t(L 3) = 50; L 4: 0 – 2 – 7 – 8, t(L 4) = 50. Для удобства дальнейших расчетов представим эти пути графически в виде цепочек, в которых цифры над каждой работой показывают коэффициенты затрат на ускорение работ hij, а под стрелками – максимально возможные величины уменьшения продолжительности работ ∆ t ij = b ij – a ij. h ij i j b ij – a ij
Ниже построены схемы всех полных путей.
10. Первоначальная стоимость проекта С = 300. Критическим является путь L2, его длина tкр = 99. Уменьшение продолжительности выполнения комплекса можно только за счёт сокращения продолжительности работ пути L2. Из работ критического пути L2 наименьший коэффициент hij имеет работа (3, 4): h34 = 2. Продолжительность работы (3, 4) можно сократить не более чем на 10 суток. Действительно, ∆ t = min{b 34 – a 34, T kp – T 1} = min{10, 99 – 89} = 10. При этом изменяется длина только критического пути L 2 (с 99 до 89 суток), единственного пути, проходящего через работу (3, 4). Стоимость всего проекта за счет ускорения работы (3, 4) возрастет на 2⋅ 10 = 20 единиц и станет равной 300 + 20 = 320. Итак, согласно (3.15) получаем С(t) = 300 + 2(99 − t), 89 ≤ t ≤ 99. Новые длины путей равны t(L1) = t(L2) = 89, t(L3) = t(L4) = 50, tкр = 89. 20. Есть два критических пути L1 и L2 и сократить срок выполнения проекта можно за счет одновременного сокращения их продолжительности, изменяя продолжительность работ, лежащих на этих путях: либо (0, 1), либо (1, 3), либо (6, 7), либо (7, 8). Остановимся на работе (6, 7), поскольку при этом обеспечивается минимум затрат на ускорение. Действительно, из работ критических путей L1 и L2 наименьший коэффициент h67 = 5 имеет работа (6, 7). Продолжительность работы (6, 7) можно уменьшить не более чем на 5 дней. Действительно, ∆ t = min{b 67 – a 67, T kp – T 2} = min{5, 89 – 50} = 5. На эту величину уменьшатся длины критических путей t(L 1) и t(L 2), а следовательно, и срок выполнения проекта. При этом стоимость работы (6, 7) возрастет на 5⋅ 5 = 25 усл. единиц, а для всего проекта она увеличится с 320 до 345 усл.ед. Согласно (3.15), получаем С (t) = 320 + 5(89 − t), 84 ≤ t ≤ 89. 30. С = 345; t(L 2) = t(L 1) = 84; t(L 3) = t(L 4) = 50; t кр = 84. Критическими являются пути L1 и L2, tкр = 84, {Lkkp} = {L1, L2 }. Из работ на критических путях L1 и L2 наименьший коэффициент hij имеет работа (0, 1): h01 = 6. Действительно, hmin(i, j) = min(h(0, 1), h(1, 3), h(7, 8)) = min(6, 8, 9) = 6. Продолжительность общей работы (0, 1) на этих путях можно сократить на 10 дней: ∆ t = min{b 01 – a 01, T kp – T 2} = min{10, 84 – 50} = 10. Согласно (3.15) получаем С(t) = 345 + 6(84 − t), 74 ≤ t ≤ 84. Стоимость работы (0, 1) и всего проекта возрастет на 6⋅ 10 = 60 единиц, С 01 = 35 + 60 = 95. Новые значения стоимости проекта и длин критических путей: С = 345 + 6⋅ 10 = 405, t(L 1) = t(L 2) = 74. 40. С = 405, t(L 1) = t(L 2) = 74, t(L 3) = 40, t(L 4) = 50. Критическими являются пути L 1 и L 2. t кр = 74, {L k kp} = {L 1, L 2}. h min(i, j) = min(h(1, 3), h(7, 8)) = min(8, 9) = 8, h min = h(1, 3) = 8. Продолжительность общей работы (1, 3) сокращается на 5 дней: ∆ t = min{b 13 – a 13, T kp – T 2} = min{5, 74–50} = 5. Согласно (3.15) получаем С(t) = 405 + 8(74 − t), 69 ≤ t ≤ 74. Стоимость работы (1, 3) и всего проекта возрастет на 8⋅ 5 = 40 единиц, С 13 = 10 + 40 = 50. Новое значение С = 405 + 8⋅ 5 = 445, t(L 1) = t(L 2) = 69. 50. С = 445, t(L 1) = t(L 2) = 69, t(L 3) = 40, t(L 4) = 50. Критическим являются пути L1 и L2. tкр = 69, {Lkkp} = {L1, L2}. hmin(i, j) = h(7, 8) = 9. Продолжительность общей работы (7, 8) сокращается на 5 дней: ∆ t = min{b 78 – a 78, T kp – T 2} = min{5, 69–50} = 5. Согласно (3.15) получаем С(t) = 445 + 9(69 − t), 64 ≤ t ≤ 69. Стоимость работы (7, 8) и всего проекта возрастет на 9⋅ 5 = 45 единиц, С 78 = 20 + 45 = 65. Новое значение С = 445 + 9⋅ 5 = 490, t(L 1) =t(L 2) = 64. 60. С = 490, t(L 1) = t(L 2) = 64, t(L 3) = 35, t(L 4) = 45. Критическими являются пути L1 и L2. tкр = 64, {Lkkp} = {L1, L2}. Общих работ на этих путях нет. Можно сократить работы (3, 5) и (5, 6) пути L1 на 5 дней и работу (4, 6) пути L2 на 10 дней. Одновременно можно сократить на 5 дней продолжительность работы (5, 6) пути L1 и работы (4, 6) пути L2. Действительно, ∆ t = min{b 46 – a 46, b 56 – a 56, T kp – T 2} = min{10, 5, 64 – 50} = 5. Коэффициенты напряженности этих работ равны соответственно h(5, 6) = 4, h(4, 6) = 4. Коэффициент затрат на ускорение работ равен h(5, 6) + + h(4, 6) = 4 + 4 = 8. Согласно (3.15) получаем С(t) = 490 + 8(64 − t ), 59 ≤ t ≤ 64. Стоимость работы (4, 6) возрастет на 4⋅ 5 = 20, а работы (5, 6) на 4⋅ 5 = 20 единиц: С 46 = 40 + 20 = 60, С 56 = 30 + 20 = 50. Новые значения С = 490 + 8⋅ 5 = = 530, t(L 1) = t(L 2) = 59.
70. С = 530, t(L1) = t(L2) = 59, t(L3) = 35, t(L4) = 45. Критическими являются пути L1 и L2. tкр = 59, {Lkkp} = {L1, L2 }. Общих работ нет. Теперь можно одновременно сократить на 5 дней продолжительность работы (3, 5) пути L 1 и работы (4, 6) пути L 2: ∆ t = min{b 35 – a 35, b 46 – a 46 , T kp – T 2} = min{5, 5, 59–50} = 5. Коэффициенты напряженности этих работ равны h(3, 5) = 6, h(4, 6) = 4 соответственно. Коэффициент затрат на ускорение обеих работ будет равен h(3, 5) + h(4, 6) = 6 + 4 = 10. Следовательно, С(t) = 530 + 10(59 − t), 54 ≤ t ≤ 59. Стоимость работы (3, 5) возрастет на 6⋅ 5 = 30, а работы (4, 6) – на 4⋅ 5 = 20 единиц: С 35 = 15 + 30 = 45, С 46 = 60 + 20 = 80. Новые значения С = 530 + 10⋅ 5 = = 580, t(L 1) = t(L 2) = 54. Алгоритм продолжается до тех пор, пока есть t ij > a ij. Шаги алгоритма представим в табл. 3.5.
Таблица длительности / стоимости работ Таблица 3.5
Ниже представлены длительности полных путей на различных шагах алгоритма (табл. 3.6.)
Таблица длительности полных путей Таблица 3.6
Теперь, построив функцию С(t), можно определить время выполнения проекта t* для любых затрат С* и наоборот.
59 64 69 74 84 89 99 t Например, из шага 30 следует, что при стоимости проекта С* = 375 усл. р. минимальная продолжительность проекта будет равна t* = 79 дней, а из шага 70 видно, что при стоимости С* = 540 усл. р. t* = 55 дней. С помощью функции С(t) можно оценить и дополнительные затраты, связанные с сокращением сроков завершения проекта. Так, сокращение продолжительности проекта с 79 до 55 дней потребует дополнительно 540 – – 375 = 165 усл. р.
В заключение сделаем следующее замечание. При линейной зависимости стоимости работ от их продолжительности задача оптимизации сетевого графика может быть поставлена в виде задачи линейного программирования, в которой необходимо минимизировать стоимость проекта при двух группах ограничений. Первая группа ограничений- ограничения на время выполнения работ, вторая группа ограничений показывает, что продолжительность всех полных путей не должна превышать заданного времени выполнения проекта. Однако решать такие задачи линейного программирования классическими методами неэффективно. 9. Общая постановка задачи линейного программирования Формы записи ЗЛП.
Задача линейного программирования (ЗЛП) в общей постановке имеет три формы: произвольную, симметричную и каноническую.
1. Произвольная форма ЗЛП имеет вид Выражение ∑ c j ⋅ x j j =1 называется целевой функцией (или критерием) задачи. Величины (Х1, Х2, …, Хn) – переменные задачи. Система неравенств в задаче (4.2) определяет область допустимых значений (планов) задачи D, которая имеет форму выпуклого многогранника. Неравенства и равенства в задаче (4.2) называются ограничениями. Каждое неравенство определяет полупространство, а равенство – плоскость в пространстве переменных (Х1, Х2, …, Хn). Решение задачи (4.2) называется оптимальным решением (или оптимальным планом) и обозначается как Х* = (Х*1, Х*2, …, Х*n). Оптимальные решения лежат на границе области D. Если область D ограничена, то задача ЛП имеет либо единственное, либо бесконечно много решений. Если решение единственно, то оно совпадает с одной из вершин многогранника D. Если градиент целевой функции c = (с1, с2, …, сn) коллинеарен градиенту одного из ограничений, то задача имеет бесконечно много решений, лежащих на данном ограничении. Если ограничения несовместны, или целевая функция неограниченна, то задача (4.2) не имеет решения. Если область области D не ограничена, то решение может существовать либо быть неограниченным. Всякая задача на минимум может быть сведена к задаче на максимум и наоборот, умножением целевой функции на –1. Оптимальный план задачи при этом не изменится, а значение целевой функции изменит знак. После решения надо снова изменить знак целевой функции. 2. Симметричная форма ЗЛП на максимум имеет вид n max
n ∑ c j ⋅ x j , j =1
(4.3) ∑ a ij ⋅ x j ≤ b i , j =1 x j ≥ 0, ( j = 1,..., n ). Симметричная форма задачи на минимум имеет вид n min
n ∑ c j ⋅ x j , j =1 ∑ a ij ⋅ x j ≥ b i , j =1 (4.4) x j ≥ 0, ( j = 1,..., n ). Если все b i ≥ 0, то з адача (4.3) обычно имеет следующий экономический смысл: x j − объемы производства j-го вида продукции, c i − цены или прибыль единицы продукции, a ij − нормативы затрат i-го вида ресурса на производство единицы j-го вида продукции, b i − имеющийся запас i-го вида ресурса. Надо определить план производства продукции Х* = (Х*1, Х*2, …, Х*n), который дает максимальную выручку или прибыль, при заданных ограничениях на имеющиеся ресурсы. Ограничения, на которых в оптимальном плане достигнуто равенство, соответствуют дефицитным ресурсам, остальные ресурсы называются недефицитными. 3. Каноническая форма ЗЛП представлена ниже: n max (min)
n ∑ c j ⋅ x j , j =1 ∑ a ij ⋅ x j = b i , j =1 (i = 1,..., m ), (4.5)
x j ≥ 0, ( j = 1,..., n ), Из линейной алгебры известно, что количество линейно независимых уравнений не может быть больше числа неизвестных. Поэтому в (4.5) можно считать, что n ≥ m. Определение. Если в ограничении задачи (4.5) есть переменная с коэффициентом, равным единице, отсутствующая в других ограничениях, то она называется базисной, остальные переменные ограничения называются свободными. Если базисные переменные есть во всех ограничениях, то такая форма ЗЛП называется канонической с базисными переменными. Каноническая форма с базисными переменными является исходной для решения задачи симплексным алгоритмом. Опорным планом называется любой вектор Х = (Х1, Х2, …, Хn), удовлетворяющий условиям (4.5) и имеющий не более чем m ненулевых компонент. Если в канонической форме все b i ≥ 0, то задача (4.5) имеет опорный план, в котором базисные переменные равны b i, а остальные (свободные) переменные равны 0. Такой план называется начальным опорным планом. Балансовой называется переменная, которая добавляется или вычитается из левой части неравенства для получения равенства. В задачах (4.3), (4.4) балансовые переменные будут базисными. Любая форма ЗЛП приводится к канонической форме с помощью следующих преобразований: • замена переменной, которая принимает произвольные значения, на разность двух новых положительных переменных; • введение балансовых переменных. Искусственная переменная вводится, когда в канонической форме ЗЛП в ограничении нет базисной переменной. В этом случае целевая функция изменяется путем вычитания искусственной переменной с коэффициентом М в задаче на максимум и путем прибавления – в задаче на минимум. Коэффициент М считается большим положительным числом. При вводе искусственных переменных и корректировке целевой функции измененная задача называется М-задачей.
10. Примеры задач ЛП
Пример 4.1. Пусть задача ЛП имеет вид max 2 x1 + 10 x2 − 8x3, 2 x1 − x3 ≤ 2, x1 + 2 x2 − 2 x3 ≥ 3, 2 x1 − x3 = 5, x1, x3 ≥ 0, x2 − произвольное. (4.6) Чтобы привести ее к канонической форме, сделаем подстановку x2 = x2 − x2, а в неравенства введем балансовые переменные x4, x5 и 1 2 искусственную переменную x6. Тогда М-задача для (4.6) будет иметь вид
− 10 x 2 − 8 x 3 − M ⋅ x 6, 2 x 1 − x 3 + x 4 1 = 2, 2 0, 5 x 1 + x 2 − x 2 − x 3 − 0, 5 x 5 =1, 5, (4.7) 2 x 1 − x 3 1 + x 6 2 = 5, x 1, x 2 , x 2 , x 3 , x 4 , x 5 , x 6
11. Симплексный метод решения ЗЛП. Существует несколько форм симплекс-алгоритма: с короткой матрицей, с расширенной матрицей, двойственный алгоритм, модифицированный. При рассмотрении алгоритма с короткой матрицей будем считать, что задача дана на максимум целевой функции. Если задача дана на минимум, то ее можно привести к задаче на максимум, изменив знак целевой функции. Для применения симплекс-алгоритма ЗЛП должна быть представлена в канонической форме (4.5):
Если в системе ограничений (4.5) m < n и все уравнения линейно независимы, то эту систему можно разрешить относительно тех m переменных, которым в матрице ограничений соответствуют линейно независимые столбцы. Пусть независимыми будут первые m столбцов, тогда ограничения задачи (4.5) можно разрешить относительно Х1, Х2, …, Хm:
Переменные Х1, Х2, …, Хm будут базисными, а переменные Хm + 1, Хm + 2, …, Хn – свободными. Целевую функцию надо выразить через свободные переменные:
Симплекс-алгоритм носит итеративный характер и состоит в построении и последовательном преобразовании симплексной таблицы, в результате которого от начального плана можно за конечное число шагов получить оптимальный план, либо установить, что ЗЛП не имеет решения.
В F-строке записаны коэффициенты модифицированной целевой функции с обратными знаками, b0 – это значение функции при нулевых значениях свободных переменных. Если в столбце свободных членов все коэффициенты bio ≥ 0, то вектор Х = (Х1 = b10, Х2 = b20, …, Хm = bm0, Хm + 1 = 0, ..., Хn = 0) называется начальным опорным планом. Значение целевой функции равно элементу В-столбца в F-строке. Решение задачи линейного программирования симплексным методом проводится в два этапа. Сначала находится начальное базисное решение, а затем проводится направленный перебор базисных решений для получения оптимального плана. Алгоритм построения начального опорного плана 1. Отыскание разрешающего столбца. В столбце свободных членов отыскивается отрицательный элемент. Если такого нет, текущее решение является опорным. Далее переходят к алгоритму нахождения оптимального плана. Если среди элементов столбца свободных членов несколько отрицательных, то выбирается минимальный из них. По минимальному отрицательному элементу этой строки выбирается разрешающий столбец (r). Если просматриваемая строка не содержит отрицательных элементов, задача несовместна и не имеет решения. 2. Выбор разрешающей строки. Находятся симплексные отношения элементов столбца свободных членов к элементам разрешающего столбца (кроме F-строки). Рассматриваются только положительные отношения. По наименьшему положительному симплексному отношению определяется разрешающая строка (s). 3. Выбор разрешающего элемента. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент (asr). 4. Симплексные преобразования таблицы: - х-переменные разрешающих столбца и строки меняются местами; - разрешающий элемент заменяется обратной величиной; - остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; - остальные элементы разрешающей строки делятся на разрешающий элемент; - все прочие элементы таблицы вычисляются по методу прямоугольника по формуле
В результате выполнения этого шага переменная xr становится базисной, а переменная xs выводится из базиса и становится свободной. После чего переходят к шагу 1. Алгоритм нахождения оптимального плана 1. Проверка базисного решения на оптимальность. Если все элементы F-строки неотрицательны, то базисное решение оптимально. В противном случае оно может быть улучшено. Если все элементы F-строки положительны, то полученный оптимальный план будет единственным, если в F-строке есть нулевые элементы, то существует бесконечно много оптимальных планов. 2. Выбор разрешающего столбца. Разрешающий столбец выбирают по минимальному отрицательному элементу F-строки. Пусть r – номер разрешающего столбца. Если в F-строке есть отрицательный элемент, в столбце которого нет положительных элементов, то целевая функция неограниченна и решения ЗЛП не существует. 3. Вычисление симплексного отношения и выбор разрешающей строки. Разрешающая строка определяется по минимальному положительному симплексному отношению. Симплексное отношение – это отношение элементов столбца свободных членов к положительным элементам разрешающего столбца. Пусть s – номер разрешающей строки. 4. Выбор разрешающего элемента. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Обозначим его через bsr. 5. Симплексное преобразование таблицы. Выполняется точно так же, как и в предыдущем алгоритме. После чего осуществляется переход к шагу 1.
12. Понятие двойственности. Построение двойственных задач, их свойства. Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам: 1. Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот. 2. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи. 3. Если A-матрица коэффициентов исходной задачи, то транспонированная матрица задачи AT будет матрицей коэффициентов двойственной. 4. В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥ . 5. Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак ( ≥ ), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот. В матричном виде двойственные задачи, заданные в симметричной форме, имеют вид:
Переменные ( y1, y2,.., ym ) называются двойственными (или объективно-обусловленными) оценками. Экономическая интерпретация задач следующая. Вектор x – это вектор выпускаемой продукции, y – двойственные оценки ресурсов прямой задачи. Левая часть ограничений двойственной задачи представляет собой оценку затрат на единицу выпускаемой продукции в двойственных ценах. Прямая задача представляет собой задачу на определение плана, обеспечивающего максимальный выпуск продукции при заданных ценах реализации и ограничениях на ресурсы. Двойственная задача – определение таких оценок ресурсов, в которых стоимость имеющихся ресурсов минимальна, а затраты на производство единицы продукции не меньше цен реализации продукции.
13. Основные теоремы двойственности. Первая теорема двойственности. Для взаимно двойственных задач имеет место один из трех случаев: 1. Если существует решение одной задачи, то существует решение и второй задачи. Значения целевых функций на оптимальных решениях обеих задач равны 2. Если решение одной задачи неограниченно, то другая задача несовместна. 3. Обе задачи несовместны.
Вторая теорема двойственности. Оптимальные решения двойственных задач удовлетворяют соотношениям
Имеет место и обратное свойство: если допустимые значения переменных xj, yi удовлетворяют соотношениям (см. выше), то они являются оптимальными решениями обеих задач. Экономический смысл второй теоремы двойственности состоит в следующем: 1) если оптимальная оценка i-го ресурса не равна нулю
2) если в оптимальном плане ресурс не используется полностью 3) если j-й продукт входит в оптимальный план
4) если j-й продукт в оптимальных оценках ресурсов убыточен
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-04-09; Просмотров: 738; Нарушение авторского права страницы
и на множестве допустимых значений обеих задач выполняется неравенство 
Если на допустимых решениях обеих задач целевые функции равны, то решения оптимальны.
, то в оптимальном плане этот ресурс используется полностью 
