Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ

Здравствуйте гость!

Логин:

Пароль:

Запомнить

Забыли пароль? Регистрация

Поиск учебного материала на сайте

Поиск по названию работы

Поиск по тексту работы

Повышение оригинальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.

Результат поиска


Наименование:	курсовая работа Реализация модифицированного симплекс-метода
Информация:	Тип работы: курсовая работа. Добавлен: 26.04.2013. Год: 2013. Страниц: 21. Уникальность по antiplagiat.ru: < 30%

Описание (план):
	Содержание 1. Линейное программирование 1.2 История возникновения транспортной задачи и лин6ейного программирования 1.3 Основные понятия линейного программирования 2. Теоремы линейного программирования 3. Методы нахождения начального опорного решения транспортных задач линейного программирования 3.1 Метод северо-западного угла 3.2 Метод минимальной стоимости 3.3 Метод потенциала 3.4 Метод Фогеля 5. Решение транспортной задачи методом Фогеля 6. Решение задачи в электронных таблицах 7. Решение транспортной задачи на программе Pascal Введение Развитие современных экономических, производственных и других систем невозможно без эффективного управления, обеспечивающего их переход из одного качественного состояния в другое, в соответствии с определенными целями и задачами. Процесс управления всеми звеньями системы предусматривает необходимость выработки наилучших (оптимальных) управленческих решений. Подавляющее количество проблем и задач, по которым руководителю приходится принимать решения, являются прогнозного или планового характера. Поэтому для выработки наиболее эффективных решений лицам, ответственным за подготовку и принятие решений, необходимо стремиться к наиболее полному привлечению информации о многочисленных факторах, влияющих не только на процесс принятия решения, но и на ход и исход его выполнения. При современных масштабах производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием – математическое программирование. Математическое программирование в применении к анализу и управлению экономикой представляет собой теорию эффективного использования ресурсов. Она применяется для определения оптимальных планов, решения проблемы наилучшего сочетания желаемого и возможного. Линейное программирование – это область математического программирования, оно является одним из основных научных направлений в области оптимальной деятельности при ограниченных ресурсах, его методы активно используются в прогнозных расчетах, планировании и организации производственных процессов, а также в финансовой сфере. Актуальность темы данной курсовой работы заключается в том, что изучение решения задач линейного программирования позволит приобрести необходимые навыки, которые понадобятся для профессиональной деятельности и успешной работы. Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов. Цель транспортной деятельности считается достигнутой при выполнении шести условий: нужный товар; необходимого качества; в необходимом количестве доставлен; в нужное время; в нужное место; с минимальными затратами. Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-комме ческую деятельность. В данной курсовой работе будут рассмотрены понятие транспортной задачи, ее типы, различные методы решения. Решена задача по варианту 6.2 с помощью ТЗprog и приложена компьютерная программа по решению задачи данного типа. 1. Линейное программирование Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно довольно просто проиллюстрировать. Действительно, путь необходимо исследовать на экстремум линейную функцию : Z = С ₁х₁+С₂х₂+... +С_Nx_N при линейных ограничениях a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁ a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂ . . . . . . . . . . . . . . . a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М Так как Z - линейная функция, то = С_j (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами. Для решения задач линейного программирования потребовалось создание специальных методов. Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные. 1.2 История возникновения транспортной задачи и лин6ейного программирования Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной. Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”. В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математик , обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой. Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования. Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны. Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем – словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого! А самому Леониду Витальевичу – как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году. 1.3 Основные понятия линейного программирования Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования. Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим: математические модели очень большого числа экономических задач линейны относительно искомых переменных; эти типы задач в настоящее время наиболее изучены; для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ; многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве; некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы. Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи. Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального). В общей постановке задача линейного программирования выглядит следующим образом: Имеются какие-то переменные х = (х₁, х₂, … х_n) и функция этих переменных f(x) = f (х₁, х₂, … х_n), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G: В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что а) функция f(x) является линейной функцией переменных х₁, х₂, … х_n б) область G определяется системой линейных равенств или неравенств. Математическая модель любой задачи линейного программирования включает в себя: максимум или минимум целевой функции (критерий оптимальности); систему ограничений в форме линейных уравнений и неравенств; требование неотрицательности переменных. Пример 2.1.1 В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Поyтому в наиболее общей форме задачу линейного программирования формулируют следующим образом: Коэффициенты a_i,j, b_i, c_j, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0). Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными. Выше описанная задача линейного программирования (ЗЛП) представлена в общей форме, но одна и та же (ЗЛП) может быть сформулирована в различных эквивалентных формах. Наиболее важными формами задачи линейного программирования являются каноническая и стандартная. В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, ..., х_nявляются неотрицательными: К канонической форме можно преобразовать любую задачу линейного программирования. Правило приведения ЗЛП к каноническому виду: 1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «?» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «?» - со знаком «-» Вводим переменную . Тогда неравенство (2.10) запишется в виде: В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений. 2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных 3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1) 4. Наконец, если исходная задача была задачей на минимум, то введением новой целевой функции F₁= -F мы преобразуем нашу задачу на минимум функции F в задачу на максимум функции F₁. Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме. В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны. Всякую задачу линейного программирования можно сформулировать в стандартной форме. Преобразование задачи на минимум в задачу на максимум, а также обеспечение не отрицательности переменных производится так же, как и раньше. Всякое равенство в системе ограничений равносильно системе взаимопротивоположны неравенств: Существует и другие способы преобразования системы равенств в систему неравенств, т.е. всякую задачу линейного программирования можно сформулировать в стандартной форме. 2. Теоремы линейного программирования Основные теоремы линейного программирования. Рассмотрим некоторые теоремы. Отражающие фундаментальные свойства задач линейного программирования и лежащие в основе методов их решения. Они по существу обобщают на случай задач с произвольным количеством переменных те свойства, которые мы наблюдали в двумерном случае. Теорема 1.1. Если целевая функция f принимает максимальное значение в некоторой точке множества допустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества. Доказательство. Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D ограничено, и, следовательно, является выпуклым многогранником. Для доказательства воспользуемся следующим известным свойством ограниченных выпуклых множеств: Если D — замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек, то любая точка х D может быть представлена в виде выпуклой комбинации угловых точек D. Строгое доказательство данного утверждения см., например: Пусть х1, х2,…,хm — угловые точки множества D, а х* — точка, в которой целевая функция f достигает максимума. На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых точек х1, х2,..., xm Так как х* — точка максимума, то для любого х D сх* ? сх. Функция f(x) — линейная, поэтому следовательно, где xr — угловая точка, удовлетворяющая условию Из (1.10) видно, что сх* ? схr. В то же время справедливо обратное неравенство: сх* ? схr. Откуда следует, что сх* = схr, т. е. существует по крайней мере одна угловая точка хr, в которой целевая функция принимает максимальное значение. A 3. Определение начального допустимого решения Для сбалансированной транспортной задачи существует только m + n - 1 независимых уравнений. Таким образом, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных. Начальное базисное решение транспортной задачи получают непосредственно из транспортной таблицы. Для этого можно использовать три процедуры. 3.1 Метод северо-западного угла При нахождении опорного плана транспортной задачи методом "северо-западно о угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х11 приписывают максимальное значение, допускаемое ограничениями на спрос и запасы. После этого вычеркивают соответствующий столбец или строку, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю. Если ограничения выполняются одновременно, то можно вычеркнуть либо строку, либо столбец. Процесс завершается тогда, когда будет присвоено значение переменной хmin. Исходный опорный план, построенный по правилу "северо-западно о угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина сij). Более совершенным правилом является правило "минимального элемента". 3.2 Метод минимальной стоимости В методе "северо-западно о угла" на каждом шаге потребность первого из оставшихся пунктов назначения удовлетворяется за счет запасов первого из оставшихся пунктов отправления. Очевидно, что выбор пунктов назначения и отправления целесообразно производить, ориентируясь на стоимость перевозок, а именно на каждом шаге следует выбирать какую-либо клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбирать любую из них), и рассматривать пункты назначения и отправления, соответствующие выбранной клетке. Правило "минимального элемента" заключается в том, чтобы перевозить максимально возможные объемы из пунктов отправления маршрутами минимальной стоимости. Заполнение таблицы начинаем с клетки, которой соответствует наименьшая стоимость перевозки (элемент cij) из всей таблицы. Переменной этой клетки хij присваивается максимально возможное значение с учетом ограничений. Затем остаток по столбцу или строке помещается в клетку того же столбца или строки, которой соответствует следующее по величине значение сij и т. д. Иными словами, последовательность заполнения клеток определяется по величине сij, а помещаемая в этих клетках величина хij такая же, как и в правиле "северо-западно о угла". 3.3 Метод потенциала Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций). Общий принцип определения оптимального плана транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. Составим двойственную задачу 1. , - любые 2. 3. Пусть есть план Теорема (критерий оптимальности): Для того чтобы допустимый план перевозок в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа , , что если , (6) если . (7) числа и называются потенциалами пунктов отправления и назначения соответственно. Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план. Для этого плана, в котором базисных клеток, можно определить потенциалы и так, чтобы выполнялось условие (6). Поскольку система (2)-(4) содержит уравнений и неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (6) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины . Если оказалось, что , то план оптимален. Если же хотя бы в одной свободной клетке , то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке. Циклом в таблице условий транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия (7). 3.4 Метод Фогеля Метод Фогеля (англ. Vogel’s approximation method) — один из методов получения начального решения транспортной задачи. В отличие отметода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов. Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку.^[2]^:115Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек. Числовой пример: В этом примере стоимость доставки в рублях за кг записана в ячейках в квадратных скобках. В эти же ячейки транспортной таблицы следует вписать объемы перевозки, чтобы распределить запасы поставщиков по потребителям. Шаг 1: Вычислим разницы между двумя минимальными тарифами по строкам. Строка 1: 2-2=0 Строка 2: 2-1=1 Строка 3: 3-2=1 И затем по столбцам. Столбец 1: 3-2=1 Столбец 2: 3-2=1 Столбец 3: 2-2=0 Столбец 4: 4-1=3 Наиболее предпочтителен столбец 4, поскольку разница для него максимальна. В столбце 4 найдем минимальную цену — 1 руб/кг в строке 2. В нашем примере это ячейка X₂₄(2-й поставщик, 4-й потребитель), где цена доставки = 1 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 10 кг, то есть 10 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет. Шаг 2 Вычислим разницы между двумя минимальными тарифами по строкам (не учитывая закрашенные серым и распределенные ячейки — см. таблицу выше). Строка 1: 2-2=0 Строка 2: 3-2=1 Строка 3: 3-2=1 И затем по столбцам. Столбец 1: 3-2=1 Столбец 2: 3-2=1 Столбец 3: 2-2=0 Есть несколько строк и столбцов с одинаковой предпочтительностью, возьмем любую из них, например строку 2, а в ней — выберем минимальный тариф, не учитывая (см. таблицу выше) закрашенные ячейки. В нашем примере это ячейка X₂₂(2-й поставщик, 2-й потребитель), где цена доставки = 2 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (30 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет. Возможности поставщика также исчерпаны, закрашиваем в серый цвет также и строку. Шаг 3 Вычислим разницы между двумя минимальными тарифами по строкам (не учитывая закрашенные серым и распределенные ячейки — см. таблицу выше). Строка 1: 2-2=0 Строка 3: 4-2=2 И затем по столбцам. Столбец 1: 4-2=2 Столбец 3: 2-2=0 Есть строка и столбец с одинаковой предпочтительностью (максимальной разницей тарифов, равной 2 руб./кг), возьмем любой из них, например строку 3, а в ней — выберем минимальный тариф, не учитывая (см. таблицу выше) закрашенные ячейки. В нашем примере это ячейка X₃₃(3-й поставщик, 3-й потребитель), где цена доставки = 2 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (минимальное значение между 20 и 30 кг, то есть 20 кг). Поскольку возможности поставщика полностью исчерпаны, закрашиваем соответствующую строку в серый цвет. Шаг 4 Заполнение оставшихся ячеек (см. таблицу выше) безальтернативно, алгоритмически (если мы пишем программу для ЭВМ) присваиваем разницы = 0, если число нераспределенных ячеек в строке или столбце меньше двух. Дальнейшая оптимизация решения Полученный результат распределения составляет 220+210+230+110+ *20 = 170 рублей. Метод минимальных тарифов на этом же примере дал результат стоимостью 210 рублей, а метод северо-западного угла — 290 руб., то есть — наименее оптимальный. Проверить этот результат на оптимальность и, при необходимости, окончательно его оптимизировать можно при помощи метода потенциалов(который в этом примере показывает, что это распределение оптимально). 5. Решение транспортной задачи методом Фогеля Однородный груз сосредоточен у трех поставщиков в объемах 9, 16 и 5 тонн. Данный груз необходимо доставить четырем потребителям в объемах 11, 7, 8 и 4 тонн. Известны стоимости единицы груза от каждого поставщика каждому потребителю. 2 5 8 1 8 3 9 2 7 4 6 3 Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Математическая модель транспортной задачи: F = ??c_ijx_ij, (1) при условиях: ?x_ij = a_i, i = 1,2,…, m, (2) ?x_ij = b_j, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов Проверим необходимое и достаточное условие разрешимости задачи. ?a = 9 + 16 + 5 = 30 ?b = 11 + 7 + 8 + 4 = 30 Занесем исходные данные в распределительную таблицу. Этап I. Поиск первого опорного плана. 1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке. Сведем все вычисления в одну таблицу. В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным. Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i и т.д.................

Скачать работу Скачать работу с онлайн повышением оригинальности до 90% по antiplagiat.ru, etxt.ru Смотреть полный текст работы бесплатно * Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.

Повышение оригинальности

Результат поиска

Числовой пример:

В этом примере стоимость доставки в рублях за кг записана в ячейках в квадратных скобках.

Шаг 1:

Вычислим разницы между двумя минимальными тарифами по строкам.

Строка 1: 2-2=0

Строка 2: 2-1=1

Строка 3: 3-2=1

И затем по столбцам.

Столбец 1: 3-2=1

Столбец 2: 3-2=1

Шаг 2

Шаг 3

Шаг 4

Дальнейшая оптимизация решения

Скачать работу

Скачать работу с онлайн повышением оригинальности до 90% по antiplagiat.ru, etxt.ru

Смотреть полный текст работы бесплатно