![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Транспортная задача линейного программирования
Основные понятия Открытая и закрытая транспортные задачи линейного программирования. Задающая таблица (таблица для записи условий) транспортной задачи линейного программирования. Условия разрешимости. Примеры практических задач, приводящих к транспортной задаче линейного программирования. Построение начального плана методом северо-западного угла и методом наименьшего тарифа. Признак оптимальности. Распределительный метод. Метод потенциалов. Экономическая интерпретация потенциалов. ЛИТЕРАТУРА: (1). Вопросы для самопроверки 1. Является ли открытой следующая транспортная задача линейного программирования.
2. Для задачи (1) составьте заданную таблицу. 4. Каковы необходимые и достаточые условия разрешимости транспортной задачи линейного программирования? 5. Имеет ли решение задача (1)? 6. Как установить оптимальность плана? 7. Для любого ли допустимого плана транспортной задачи линейного программирования существует система потенциалов? 8. Приведите задачу (1) к закрытой транспортной задаче.
Вычислительная схема метода потенциалов. Метод потенциалов - один из методов решения задачи
где x11, x12, …, xmn - переменные; c11, c12,..., cmn – произвольные фиксированные числа, которые будем называть тарифами; a1,..., am, b1,..., bn - положительные фиксированные числа, удовлетворяющие условию Рассмотрим вычислительную схему метода потенциалов, в которой для решения задачи (2) строится последовательность таблиц Т1,..., Тk до тех пор, пока не получится таблица Тk, удовлетворяющая определенному условию. Все таблицы имеют m cтрок и n столбцов; во всех клетках этих таблиц в правом верхнем углу записаны соответствующие тарифы (в клетке (i, j) - тариф cij). В каждой из этих таблиц имеется ровно m+n-1 клеток, в которых кроме тарифов записано еще по одному неотрицательному числу (эти числа будем называть перевозками). Клетки, в которых записаны перевозки, будем называть заполненными; остальные клетки будем называть свободными. В последней таблице Тk содержится информация о решении задачи (2), которое получается так: хij=dij, если клетка (i, j) таблицы Тk заполнена перевозкой dij; в противном случае хij=0 (i=1,..., m; j=1,..., n). Помимо записи тарифов в углы клеток при составлении любой из таблиц Т1,..., Тk, кроме последней, производим следующие шесть действий. 1. Заполняем таблицу перевозками. Первую таблицу Т1 заполняем специальным образом (как именно, сказано ниже). Каждую последующую таблицу заполняем так: перевозки из непомеченных клеток предыдущей таблицы переписываем в соответствующие клетки заполняемой таблицы без изменения, а перевозки из помеченных плюсом (минусом) клеток переписываем в соответствующие клетки увеличенными (уменьшенными) на величину главной перевозки; исключение из сказанного составляет лишь главная перевозка – она переписывается без изменения в ту клетку заполняемой таблицы, которая соответствует плохой клетке предыдущей таблицы. 2. Вычисляем потенциалы строк и столбцов, т.е. такие числа u1,..., um, v1,..., vn, что u1=0 и ui+vj=cij для каждой заполненной клетки (i, j). Потенциалы u1,..., um записываем справа от соответствующих строк таблицы, а потенциалы v1,..., vn - под соответствующими столбцами. Вычисляем потенциалы последовательно (постепенно). Сначала вычисляем потенциал u1=0. Затем отыскиваем какую-нибудь такую заполненную клетку (i, j), для которой уже вычислен только один из потенциалов ui или vj, и вычисляем другой из них по формуле vj=cij–u i или ui=cij–vj. Затем опять отыскиваем какую-нибудь обладающую указанным свойством клетку и вычисляем соответствующий потенциал и т.д. до тех пор, пока не будут найдены все потенциалы. 3. Определяем и помечаем знаком плюс плохую клетку, т.е. какую-нибудь одну такую свободную клетку (i, j), для которой cij–ui–vj< 0. 4. Находим цикл пересчета, т.е. такой замкнутый путь, который проходит по строкам и столбцам и имеет повороты на 90° только в заполненных и плохой клетках (не обязательно, чтобы этот путь имел повороты во всех заполненных клетках, но обязательно он должен иметь поворот в плохой клетке). 5. Означиваем цикл пересчета, т.е. снабжаем его повороты знаком плюс или минус так, чтобы поворот в плохой клетке был помечен знаком плюс (этот плюс уже был поставлен при определении плохой клетки) и никакие два соседних поворота не оказались помеченными одноименными знаками. 6. Определяем и заключаем в круглые скобки главную перевозку, т.е. наименьшую из перевозок, расположенных в помеченных минусом клетках (если таких наименьших перевозок несколько, то в качестве главной можно выбрать любую из них). Как уже говорилось, все шесть перечисленных действий выполняются при составлении любой таблицы, кроме последней. Последняя таблица Тk характеризуется тем, что в ней нет ни одной свободной клетки (i, j), для которой разность Перевозки, которые нужно записать в таблицу T1, вычисляем так. Заготавливаем вспомогательную пустую таблицу из m строк и n столбцов и для каждого i=1,..., m справа от i- й строки этой таблицы записываем число ai, а для каждого j=1,..., n под j- м столбцом записываем число bj. После этого делаем m+n-1 шагов заполнения вспомогательной таблицы. Каждый такой шаг состоит из следующей последовательности действий: 1) определяется наименьший номер i -й строки, справа от которой имеется незачеркнутое число (обозначим это число через а); 2) определяется наименьший номер j столбца, под которым имеется незачеркнутое число (обозначим это число через b); 3)если Пример 1. Решить задачу линейного програмирования Сравнивая эту задачу с задачей (2), заключаем, что в данном случае m=3, n=4, c11=3, c12=0, c13=1, c14=0, c21=5, c22=-1, c23=4, c24=c31=c32=с33=0, c34=–4, a1=a2=6, a3=7, b1=5, b2=1, b3=4, b4=9. Решение начинаем с составления вспомогательной таблицы, справа от соответствующих строк которой записываем числа 6, 6, 7, a под соответствующими столбцами - числа 5, 1, 4, 9. Делаем первый шаг заполнения этой таблицы. Справа от первой строки имеется незачёркнутое число 6, поэтому i =1, a =6; под первым столбцом имеется незачёркнутое число 5, поэтому j =1, b =5. Так как
Числа из этой таблицы переписываем в соответствующие клетки таблицы Т1 и приступаем к вычислению потенциалов. Справа от первой строки таблицы Т1 записываем потенциал u1=0. Затем находим заполненую клетку (1, 3), для которой уже вычислен потенциал u1 и не вычислен потенциал v3, и вычисляем v3 по формуле таблица Т1
Определяем и помечаем знаком плюс плохую клетку. В качестве плохой можно выбрать, например, свободную клетку (3.1), так как Заполняем вторую таблицу. Перевозку 1 из непомеченной клетки (1, 2) таблицы Т1 переписываем без изменения в клетку (1, 2) таблицы Т2 Перевозки 0, 2 из помеченных плюсом клеток (1, 3), (2, 4) таблицы Т1 увеличиваем на 4 и записываем в клетки (1, 3), (2, 4) таблицы Т2. Перевозки 5, 7 из помеченных минусом клеток (1, 1), (3, 4) таблицы Т1 уменьшаем на 4 и записываем в клетки (1, 1), (3, 4) таблицы Т2. Главную перевозку 4 из клетки (2, 3) таблицы Т1 записываем в клетку (3, 1) таблицы Т2. После этого для таблицы Т2 вычисляем потенциалы, определяем и помечаем знаком плюс плохую клетку (2, 2), находим и означиваем цикл пересчета, определяем и заключаем в круглые скобки главную перевозку 1 в клетке (1, 2). Таблица Т2
Заполняем таблицу Т3 и вычисляем для неё потенциалы. Таблица Т3
Далее, пытаясь определить в таблице Т3 плохую клетку, устанавливаем, что сделать это не удаётся, так как для любой свободной клетки разность между её тарифом и потенциалами не является отрицательной. Такая ситуация говорит о том, что построение таблиц закончено. Из последней таблицы получаем решение задачи:
Замечание 1. Уже отмечалось, что потенциалы u1,..., um записываются справа от соответствующих строк таблицы, а потенциалы v1,..., vn - под соответствующими столбцами. При этом не обязательно указывать численные значения потенциалов с помощью равенств, как это было сделано в рассмотренном выше примере; достаточно ограничиться записью только самих численных значений, как это сделано ниже при решении задачи из примера 2. Пример 2. Решить задачу вида (2), положив m=4, n=6, c11=1, c12=0, c13=c14=c15=c16=c21=c22=2, c23=0, c24=-4, c25=3, c26=-4, c31=-2, c32=c33=1, c34=0, c35=-3, c36=c41=c42=4, c43=0, c44=-3, с45=0, c46=-3, a1=a2=9, a3=a4=3, b1=b2=4, b3=5, b4=8, b5=2, b6=1. Решаем методом потенциалов (как и в пpимеpе 1, вместо зачеpкивания чисел около вспомогательной таблицы употpеблено заключение их в кpуглые скобки).
Таблица Т1
Таблица Т2
Таблица Т3
Таблица Т4
Замечание 2. Иногда нахождение цикла пересчета в таблице Тv представляется затруднительным. Преодолеть это затруднение можно так. Заготавливаем на черновике пустую таблицу размером m*n и отмечаем в ней точками центры тех клеток, которые соответствуют заполненным и плохой клетками таблицы Тv. После этого просматриваем все отмеченные незачеркнутые точками клетки и зачеркиваем крестиком те точки, которые в момент зачеркивания либо в своей строке не имеют других незачеркнутых точек. Затем опять просматриваем все отмеченные незачеркнутыми точками клетки и зачеркиваем нужные точки и т.д.. Эта процедура продолжается до тех пор, пока при очередном просмотре всех клеток с незачеркнутыми точками не будет зачеркнуто ни одной точки. В результате незачеркнутыми оказываются точки только в тех клетках, в которых цикл пересчета делает повороты, причем в каждой строке и каждом столбце имеется либо ровно две незачеркнутые точки, либо ни одной, так что нахождение цикла не составляет труда. Например, если проделать все сказанное для таблицы Т2 из примера 2, то получится такой pезультат (пунктиром показан цикл пересчета): Замечание 3. Вообще говоря, в таблицах имеется по нескольку клеток, каждую из которых можно выбрать в качестве плохой. Если задача имеет не единственное решение, то допустимый произвол в выборе плохих клеток может привести к разным оптимальным планам. Сказанное справедливо и в отношении возможного произвола в выборе главных перевозок.
§3. Задания для контрольной работы Решить гpафически и симплекс-методом. (Номер варианта соответствует последней цифре номера вашей зачетной книжки). Задача 1. За счет мелиоративных работ площадь пашни в хозяйстве возрасла на b2 га. Эту площадь было решено отвести под посев двух наиболее эффективых для хозяйства культур: проса и гречихи, причем гречихи нужно получить не менее b1 ц. В хозяйстве имеется b3 ц минеральных удобрений. Известны прибыльность и нормативы затрат в расчете на один центнер проса и гречихи:
Пусть х1 и х2-объем производства (ц) проса и гречихи соответственно. Требуется указать такие значения х1 и х2, чтобы общая прибыль от производства обеих культур была максимальной. Указание. Составить соответствующую задачу математического программирования и решить ее графически и симплекс-методом. Задачу решить при следующих значениях констант aj; bi:
Задача 2. Решить задачу линейного программирования симплекс-методом. Вариант 0) 3+14x1+42x2-12x3 2x1-8x2-6x3 2x1+22x2+4x3 x1
Вариант 1) 18x1-10x2-40x3 -6x1+2x2+16x3 6x1+0x2-24x3 x1
2) 15x1-9x2-4x3 0x1-2x2-8x3 5x1-1x2+6x3 x1
3) 5-26x1+22x2-38x3 1x1-7x2+32x3 3x1-x2-4x3 x1
4) 3+16x1-14x2+44x3 4x1-3x2+6x3 -2x1+1x2+0x3 x1
5) 3-47x1+28x2+4x3 10x1+5x2+5x3 0x1-6x2-3x3 x1
6) 25x1+3x2-4x3 24x1-7x2-4x3 -12x1+6x2+2x3 x1
7) 2+14x1+16x2-17x3 -4x1-5x2+5x3 5x1+7x2-10x3 x1
8) 49x1-8x2-5x3 -39x1+4x2+5x3 40x1-5x2-5x3 x1 9) 3+2x1+7x2-4x3 -7x1-x2+6x3 5x1-x2-4x3 x1 Задача 3. Найти оптимальное решение транспортной задачи методом потенциалов (ваpианты 0 - 9). Трем предприятиям нужно сырьё в количестве b1, b2, b3 тыс. тонн соответственно. Запасы сырья сосредоточены в четырех пунктах хранения в количестве a1, a2, a3, a4 тыс. тоннсоответственно. Известна матрица С расстояний (км.) между пунктами хранения и предприятиями (на пересечении i-той строки и j-го столбца этой матрицы указано расстояние между i-тым пунктом хранения и j-тым предприятием). Пусть хij-количество сырья (тыс. тонн), которое планируется завезти j-тому предприятию с i-того пункта хранения (i=1, 2, 3, 4; j=1, 2, 3,). Требуется найти такие значения х11, х12,..., х43, чтобы при перевозке сырья общее количество тонно-километров было минимальным. Указание. Составить соответствующую задачу математического программирования, преобразовать ее в закрытую транспортную задачу линейного программирования и решить методом потенциалов. Вариант 0)
а1=5, а2=7, а3=5, а4=7, b1=9, b2=7, b3=4;
а1=8, а2=6, а3=2, а4=8, b1=7, b2=9, b3=5; Вариант 2)
а1=8, а2=7, а3=5, а4=6, b1=9, b2=5, b3=7; 3)
а1=6, а2=8, а3=7, а4=5, b1=4, b2=8, b3=9; 4)
а1=6, а2=9, а3=6, а4=2, b1=4, b2=6, b3=7; 5)
а1=5, а2=9, а3=6, а4=7, b1=5, b2=4, b3=9; 6)
а1=5, а2=3, а3=9, а4=6, b1=3, b2=9, b3=8; 7)
а1=6, а2=6, а3=7, а4=6, b1=5, b2=9, b3=6; 8)
а1=7, а2=6, а3=4, а4=7, b1=6, b2=8, b3=5; 9)
а1=7, а2=7, а3=7, а4=2, b1=3, b2=6, b3=5;
|