Решение транспортных задач методом потенциала.

Распределительный метод среди задач линейного программирования получил распространение из-за упрощения расчетов, точности вычисле-ний и снижения затрат времени на ввод исходной информации. Метод предложили А. Толстой и Л. В. Конторович в 1939–1940 гг. Первоначально он применялся в задачах, связанных с транспортировкой грузов, их рас-пределением между поставщиком и потребителем, поэтому получил на-

звание «транспортная задача». Применяется при решении ряда землеуст-роительных задач: распределение севооборотов и угодий по участкам, размещение культур на землях различных категорий, перераспределение участков между хозяйствами для экономии транспортных затрат и др. Суть распределительной задачи следующая. Задано m источников ресурса (производители продукции, базы с готовой продукцией) и n

пунктов его потребления. Запасы ресурса в источниках составляют Аi, i=1, …, m, потребности – Bj, j=1, …, n. Стоимость транспортировки еди-ницы ресурса от i-го источника к j-му потребителю Сij. Количество ре-сурса, транспортируемого от i-го источника к j-му потребителю Хij. Тре-буется определить такие значения Хij, при которых общие транспортныерасходы будут минимальны. При сбалансированности, когда общий спрос на запас ресурса у по-ставщиков и общий спрос на него у потребителя равны, задачу называют закрытой.Если баланс не выдерживается, то транспортная задача является от-

крытой. Особенности распределительных транспортных задач следующие:

• условия задачи описываются уравнениями (в симплекс-методе

описываются и неравенствами);

• все переменные выражаются в одних и тех же единицах измерения;

• во всех уравнениях коэффициенты при переменных равны единице;

• каждая переменная встречается только в двух уравнениях системы

ограничений: в одном по строке (по запасам) и в одном по столбцу (по

потребностям).

Целевая функция Z выражает суммарные расходы на транспорти-ровку грузов. ограничения по запасам и по потребностям означают, что сумма ресурса, забираемого из i-го источника, должна быть равна запасу ресурса в нем, как и сумма ресурса, доставляемого j-му потребителю, должна быть равна его потребности. Величина Сij может выражать транспортные расходы (минимиза-ция) или прибыль от транспортных операций (максимизация) и другие показатели.

На «транспортном» языке эта задача может быть описана следующим об-разом. «Ресурсы» в источниках (Ai) – площади севооборотов и улучшенных сенокосов; «потребности в ресурсах» (Bj) – площади участков; «прибыль от транспортных операций» (Сij) – чистый доход с единицы площади; «транспор-тируемый ресурс» (Хij) – часть площади i-го севооборота или угодья, разме-

щаемого на j-м участке; максимальная целевая функция (F) – чистый доход хозяйства от рационального размещения и трансформации угодий; Σai =Σbj . Чистый доход проставляется в правом верхнем углу каждой клетки (Сij, руб/га).Дальнейшее решение задачи проводится с использованием метода потенциалов. Для решения транспортных задач разработан ряд методов: функцио-нала, потенциала, дельта-метод, лямбда-задача. Используются модифи-

цированные модели: транспортно-производственная, многоэтапная, мно-гопродуктовая.

 

31. Наименьшая существенная разность (НСР). Используется в дис-персионном анализе. Она показывает то минимальное различие между средними, начиная с которого при выбранном уровне вероятности средние сравниваемые показатели существенно отличаются друг от друга. Величина критерия выражается в тех же единицах, что и сравниваемые средние выборочных совокупностей и определяется по фор-муле: НСР = tтабл ∙ md ,где md – ошибка разницы средних; tтабл – табличное значение критерия Стьюдента при уровне вероятности 0,95 или 0,99 и степени свободы, определяемой экспериментом. Если разность между сравниваемыми средними в условиях эксперимента больше или равна величине НСР при Р 0,95 или 0,99, то различие сущеcтвенно.

 

32. Открытая транспортная задача. Транспортная задача, в которой суммарная мощность поставщиков не совпадает с суммарным спросом потребителей, называется открытой. В связи с этим условия модели записываются как: ∑ai > ∑ bj или ∑ai < ∑bj. Для решения открытой транспортной задачи могут применяться методы: потенциалов, дельта-метод, МОДИ. При решении задачи методом потенциалов или МОДИ проводятся следующие дополнительные мероприятия. Если суммарные мощности поставщиков превышают суммарные мощности потребителей, в мат-рицу исходных данных следует ввести дополнительный столбец – фиктивный потребитель(В) со спросом равным небалансу: bn+1 = ∑ai – ∑bj . Показатели cij в столбце фиктивного потребителя должны быть одинаковыми по величине, которая устанавливается произвольно (любая величина, обычно проставляют 0). Если суммарный спрос потребителей превышает суммарную мощ-ность поставщиков, необходимо ввести в матрицу дополнительную строку – фиктивного поставщика (А), мощность которого должна быть равна небалансу: аm+1 = ∑bj – ∑ai. Показатели cij этой строки должны быть одинаковыми и произвольными (обычно нулевые).

При составлении базисного допустимого плана и в процессе вычислительных операций в матрице должно содержаться число поставок (клеток с кружками), равное m + n – 1. Они должны находиться в порядке вычеркиваемой комбинации. Учитываются фиктивные строки и столбцы.При использовании дельта-метода фиктивные поставщики или потребители не вводятся. Задача решается с нарушением баланса строк и столбцов. Закрытая- при которой запас резервов у поставщиков и спрос на него у потребителей равны.

 

33.Критерий Фишера используется. F=сигма в квадрате большая / сигма в квадрате меньшая. Если Fф<Fт, то различие не существенно.

Дельта-метод Аганбегяна

Для решения закрытых и открытых транспортных задач А. Г. Аганбегян (1961) разработал дельта-метод для ручной обработки.

Отличие построения цепей в дельта-методе:

• цепь строится незамкнутая;

• цепь начинается в клетке с кружком (с поставкой), которая находится в минусовой строке; в этой клетке поставка уменьшается и она становится отрицательной вершиной цепи;

• перемещение поставки в конец открытой цепи производится как в методе потенциалов с чередованием положительных и отрицательных вершин;

• в этом методе не требуется количества кружков (клеток с поставка-ми), равного m + n – 1 ;

• в исходном плане число кружков равно числу столбцов и лишь в ходе решения появляются новые клетки с кружками (поставками);

• в незамкнутой цепи вершинами бывают клетки без кружков (без поставок); они положительны, так как в них вносится поставка;

• характеристика незамкнутой цепи рассчитывается как алгебраиче-ская сумма показателей ∆Сij или в ее вершинах; так как при распре-делении поставок по цепи функционал увеличивается, характеристика цепи всегда положительная; она показывает, насколько увеличивается в функционал, если передвинуть по цепи поставку, равную 1, из минусовой строки в плюсовую.

 

35. Критерий Пирсона (хи-квадрат, χ2). Для оценки соответствия или расхождения полученных эмпирических данных и теоретических (рас-четных, прогнозных) распределений применяются статистические кри-терии согласия. Среди них наибольшее распространение получил непараметрический критерий К. Пирсона – хи-квадрат. Его можно использовать с различными формами распределения совокупностей. Как и любой другой статистический критерий, он не доказывает справедливость нулевой гипотезы, а лишь устанавливает с определенной вероятностью ее согласие или несогласие с экспериментальными данными. Критерий применяется при условии наличия не менее 5 наблюдений или частот в каждой группе, классе или совокупности. Малые частоты объединяют. Вычисление проводят по формуле:

χ2 = ∑ [(φ – φ΄)2 / ∑ φ΄], (1.26)

где φ, φ΄– наблюдения или частоты в опыте соответственно эмпириче-ски или теоретически ожидаемые.

Значения χ2 могут быть только положительными и возрастать от нуля до бесконечности. Если вычисленный критерий хи-квадрат больше табличного (теоретического) значения, нулевая гипотеза, которая предполагает соответствие эмпирического и теоретического распределений, отвергается, при χ2выч < χ2табл нулевая гипотеза принимается.

Достоверность различий можно определить по правилу Романовского: нулевая гипотеза отвергается, если соблюдается неравенство: D = (χ2 – ν) / >3

Степень свободы при проверке гипотезы о нормальном распределе-нии вычисляется по формуле ν = k – 3, где k – число классов. Различие между экспериментальными вариантами и теоретическими считаются достоверными, если D > 3.

Критерий Пирсона тем меньше, чем меньше различаются эмпирические и теоретические частоты. Он не позволяет обнаружить различия, которые скрадывает группировка (объединение малых частот в одну группу). Его удобно использовать, так как не требуется вычислений средних дисперсий.