19812

Знаходження оптимального розподілу поставок методом оцінки клітин

Доклад

Информатика, кибернетика и программирование

2.Знаходження оптимального розподілу поставок методом оцінки клітин Один з найбільш простих методів вирішення транспортної задачі розподільний метод.Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому ріше

Украинкский

2013-07-17

28 KB

1 чел.

2.Знаходження оптимального розподілу поставок методом оцінки клітин

Один з найбільш простих методів вирішення транспортної задачі - розподільний метод.
Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому рішенні Z (). За теоремою для кожної вільної клітини таблиці завдання можна побудувати єдиний цикл, який містить цю клітку і частина клітин, зайнятих опорним рішенням. Означивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину =, можна отримати нове опорне рішення Х2.
Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зсуві на одиницю вантажу по циклу, відповідному клітці (l, k), приріст цільової функції дорівнює різниці двох сум: =, де - сума вартостей перевезень одиниць вантажу в непарних клітинах циклу, позначених знаком "+", - сума вартостей перевезень одиниць вантажу в парних клітинах циклу, позначених знаком «-».
У клітинах, позначених знаком "+", величини вантажу додаються, що призводить до збільшення значення цільової функції Z (), а в клітинах, позначених знаком "-", величини вантажу зменшуються, що призводить до зменшення значення цільової функції.
Якщо різниця сум для вільної клітини (l, k) менше нуля, тобто <0, то перерозподіл величини за відповідним циклу призведе до зменшення значення Z () на величину, тобто опорне рішення можна поліпшити. Якщо ж величини, звані оцінками, для всіх вільних клітин таблиці транспортної задачі ненегативні, то значення цільової функції не можна зменшити і опорне рішення оптимально. Отже, ознакою оптимальності розподільного методу є умова = 0. (11)
Для вирішення транспортної задачі розподільним методом необхідно знайти початкове опорне рішення. Потім для чергової опорної клітини (l, k) побудувати цикл і обчислити оцінку. Якщо оцінка ненегативна, перехід до наступного вільної клітці. Якщо ж оцінка негативна, слід здійснити зсув по циклу на величину =. В результаті вийде нове опорне рішення.
Для кожного нового опорного рішення обчислення оцінок починається з першої вільної клітини таблиці. Очевидність перевіряються вільних клітин доцільно встановлювати в порядку зростання вартості перевезень, так як вирішується завдання на знаходження мінімуму.


 

А также другие работы, которые могут Вас заинтересовать

36577. Концепция типа данных. простой тип данных 38 KB
  К любому порядковому типу применимы следующие функции: OrdX порядковый номер значения выражения Х этого типа; PredX предыдущее значение выражения Х этого типа; SuccX следующее значение выражения Х этого типа; HighX наибольшее значение диапазона аргумента Х; LowX наименьшее значение диапазона аргумента Х; Функция Ord определена для любого значения порядкового типа причём нумерация значений начинается от номера 0 номера наименьшего значения типа. Функции Pred и Succ не определены соответственно для левой и правой границы...
36578. Концепция типа данных. Тип данных в ТР 29.5 KB
  Тип данных в ТР. Ранее мы познакомились с некоторыми стандартными типами данных: числовыми символьным строковым и булевским. Стандартные типы данных это лишь частный случай общей концепции типа данных Паскаля.
36579. Оператор итерационного цикла ( repeat , while ) 31 KB
  В каждом операторе итерационного цикла будем различать условие и тело цикла повторяющееся действие. Тело цикла whiledo это один оператор записанный после do а для цикла repetuntil тело цикла может быть и последовательностью операторов записанных между repet и until. Если условие есть true выполняется тело цикла и повторно вычисляется значение условия.
36580. Композиция условий и операторов. Оператор условного перехода 32.5 KB
  Оператор условного перехода. Композиция условий и операторов. Простые операторы несмотря на свою важность недостаточны для того чтобы представлять любые алгоритмы задач.
36581. Простые операторы ввода-вывода 33.5 KB
  Эти операторы Турбо Паскаля обеспечивают простейшие формы ввода с клавиатуры и вывода на экран дисплея в текстовом режиме. К простым операторам ввода и вывода относятся операторы red redln write writeln реализующие так называемый потоковый вводвывод при котором ввод и вывод рассматриваются как непрерывный поток символов и строк протекающий через экран дисплея. На экране отображается последняя порция этого потока так что нижняя строка экрана всегда остается свободной для отображения очередной строки вывода вывод идёт в нижнюю строку...
36582. Простые операторы управления вводом-выводом в текстовом режиме 32 KB
  Кроме ввода и вывода потока символов более удобный пользовательский интерфейс может быть обеспечен при использовании вводавывода в текстовом режиме экрана. В Турбо Паскале имеются средства управления вводом с клавиатуры управления курсором вывода на экран управления цветом фона экрана и выводимых символов яркостью символов и ряд других функций в том числе управления звуковым генератором. Установка цвета фона цвета символов и очистка экрана. Модуль CRT допускает использовать в текстовом режиме экрана 16 цветов задаваемых стандартными...
36583. Оператор присваивания 28.5 KB
  Левая часть это переменная любого типа правая часть выражение совместимое по типу с переменной левой части. При выполнении этого оператора вычисляется значение выражения правой части и это значение становится значением переменной левой части. Совместимость левой и правой частей присваивания по типу означает либо равенство типов либо случаи когда тип выражения правой части автоматически преобразуется к типу левой части. Эти случаи автоматического преобразования типов для известных нам стандартных типов исчерпываются следующими:  Тип...
36584. Стандартные типы данных, операции, выражения 48.5 KB
  Целые числа типа integer это числа диапазона 32768 . Константы типа integer обычные целые числа возможно со знаком. Синтаксическое определение целых чисел имеет вид: целое число ::= [ ] { цифра } В отличие от целых чисел вещественные числа типа rel представляются в памяти компьютера приближенно. Константы типа rel числа возможно с дробной частью отделяемой от целой части точкой.
36585. Структура программ на Паскале 36 KB
  Любая программа на Турбо Паскале имеет одну и ту же общую структуру: [ progrm имя программы ; ] [ раздел описаний ] begin раздел операторов end. Эта структура состоит из заголовка программы необязательного раздела описаний который может в особых случаях отсутствовать и раздела операторов содержащего хотя бы один оператор. Имя программы идентификатор выбираемый программистом. В разделе описаний должны быть описаны все нестандартные имена используемые далее в разделе операторов этой программы.