Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 9 из 14)
f =
(а были равны 650). 
Табл.7 | Bj Ai | 20 | 120 | 20 | 60 | ui |
| 100 | 6 | 4 100 | 2 | 4 | 0 |
| 70 | 1 | 2 10 | 7 | 2 60 | -2 |
| 50 | 2 20 | 4 10 | 2444 1 1111 20 | 4 | 0 |
| vj | 2 | 4 | 1 | 4 |
Будет ли полученный план оптимальным?
Определим для него новые потенциалы:
u1+v2=4, u2+v2=2, u2+v4=2, u3+v1=2, u3+v2=4, u3+v3=1. Положим u1=0, тогда v2=4, u2=-2, v4=4, u3=0, v1= 2, v3=1. Проставим значения найденных потенциалов в табл.7.
Определим оценки свободных клеток:
s11=6-(0+2)=4>0, s13=2-(0+1)=1>0, s14=4-(0+4)=0
s21=1-(-2+2)=1>0, s23=7-(-2+1)=8>0, s34=4-(0+4)=0
Оценки свободных клеток неотрицательны, следовательно, полученный план является оптимальным:
x12=100, x22=10, x24=60, x31=20, x32=10, x33=20
Минимальные транспортные расходы для этого плана f=640.
Все оценки свободных клеток равны нулю. Это свидетельствует о неединственности оптимального плана.
ОТВЕТ.
Согласно оптимальному плану, с первого завода A1 нужно поставить 100м3 перекрытый на вторую строительную площадку B2, с завода А2 - 10м3 на строительную площадку В2 и 60м3 на строительную площадку В4, с завода А3 - на 20 м3 на строительную площадку В1, 10 м3 на строительную площадку В2 и 20 м3 на строительную площадку В3.
3.7. Транспортные задачи, имеющие некоторые усложнения в постановке
1. Транспортная задача с избытком запасов:
Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают стоимости перевозок грузов в Bn+1 равными нулю. Полученная новая транспортная задача является закрытой. Найдя оптимальный план xij
этой транспортной задачи и отбрасывая в полученной таблице последний столбец, получим оптимальный план исходной транспортной задачи.2. Транспортная задача с избытком заявок:
Эта задача несколько сложнее предыдущей: дело в том, что как ни развози грузы, все потребности удовлетворить все равно не удается. Поэтому постановка задачи нуждается в уточнении.
2.1. Все пункты назначения требуется удовлетворить пропорционально поданным заявкам. В этом случае, подсчитав коэффициент пропорциональности
и «подправив» заявки:
получим закрытую модель транспортной задачи.2.2. Если не заботиться о «справедливости» удовлетворения заявок, а по-прежнему интересоваться лишь минимизацией транспортных расходов, то для отыскания оптимального плана вводят фиктивный пункт (m+1)-й отправления Am+1 с запасом груза am+1 и полагают стоимости перевозок грузов из Am+1 равными нулю. Полученная транспортная задача является закрытой. Найдя оптимальный план xij
этой транспортной задачи и отбрасывая в полученной таблице последнюю строку, получим оптимальный план исходной транспортной задачи.И в случае 1 и в случае 2.2 при преобразовании открытой задачи в закрытую, целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
3. Транспортная задача с поиском максимума целевой функции.
Перейдем к целевой функции Z=-F и найдем план (
, доставляющий ей минимум. Тогда ( будет оптимальным и для исходной задачи, причем 
( 
.4. Транспортная задача с запретными маршрутами.
Речь идет о задачах, в которых нельзя перевозить груз из некоторых пунктов отправления Ai в некоторые пункты назначения Bj. В этом случае стоимости соответствующих перевозок полагаем равными достаточно большому числу. Тогда при отыскании оптимального плана соответствующие перевозки будут блокированы.
5. Транспортная задача с обязательными поставками.
Иногда приходится решать транспортную задачу, в которой дополнительным условием в ограничениях является обязательное обеспечение конкретных перевозок по определенным маршрутам. В этом случае каждую обязательную перевозку xij=dij реализуем условно, уменьшая на dij запасы в Ai и потребности в Bj. Если это не удается сделать, то исходная задача не имеет решения. В противном случае стоимости обязательных поставок полагаем равными достаточно большому числу, решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной задачи.
6. Транспортная задача с ограничениями снизу.
Пусть требуется решить транспортную задачу, в которой некоторые из перевозок ограничены снизу xij 
pij. Организуем условные перевозки, уменьшив на pij запасы в Ai и потребности в Bj. Если это сделать не удается, то исходная задача решения не имеет, в противном случае решаем полученную задачу и от ее оптимального плана переходим к оптимальному плану исходной транспортной задачи.
3.8. Экономические задачи, сводящиеся к транспортным моделям
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:
- оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
- увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность.
ПРИМЕР. Выбор оптимального варианта использования производственного оборудования.
На предприятии имеются три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков соответственно равно 100, 250, 180 часов. Каждая операция должна выполняться соответственно 100, 120, 70, 130 часов.
Определить, сколько времени и на какую операцию нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей.
Производительность каждой группы станков на каждую операцию задана матрицей
3 5 11 10 5
5 10 15 3 2
4 8 6 12 10
1. Оптимальное распределение оборудования
Оборудование m различных видов нужно распределить между n рабочими участками. Производительность одной единицы оборудования i-го вида на j-м рабочем участке равна pij;
Потребность j-го участка в оборудовании составляет bj, 
Запас оборудования i-го вида равен ai, 
Найти распределение оборудования на рабочие участки, при котором суммарная производительность максимальная.Данная задача относится к классу транспортных задач при условии, что производительность линейно зависит от количества используемого оборудования. Поставщиками в задаче являются различные виды оборудования, потребителями - рабочие участки. Предложение определяется запасом оборудования каждого вида, спрос - потребностью в нем на рабочем участке.
Обозначим через xij число единиц оборудования i-го вида, выделенное на j-й рабочий участок,
Математическая модель задачи имеет следующий вид: 