Решение линейного программирования - Программирование, компьютеры и кибернетика отчет по практике
Составление программы для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей. Алгоритм метода потенциалов. Пример решения транспортной задачи методом наименьшей стоимости.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство образования науки Российской Федерации
НОУ ВПО Московский институт государственного и корпоративного управления
По дисциплине «Компьютерное моделирование в экономике».
Тема: «Решение линейного программирования».
2. Краткие теоретические сведения о методе
5. Блок-схема и решение задачи с помощью программы Excel
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями. Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.
В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений
2. Краткие теоретические сведения о методе
Линейное программирование: общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида
Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП )
Задача линейного программирования будет иметь канонический вид, если в общей задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства
Основную задачу можно свести к канонической путём введения дополнительных переменных.
Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств
Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.
Компания владеет тремя заводами: «А», «В», «С», с соответствующими стоимостями производства на единицу объема «а1», «а2», «а3», объем производства «А1», «В2», «С3» единиц. Компания обязалась поставлять соответственно «w1», «x2», «y3», «z4» единиц в города W, X,Y,Z. Стоимость единиц перевозок от заводов к городам AW; AX; AY; AZ;
BW; BX; BY; BZ; CW; CX; CY; CZ. При заданных стоимостях перевозок составить оптимальный план производства и распределения в магазины.
План транспортной задачи является оптимальным, если для всех свободных клеток таблицы перевозок значение критерия оптимальности dij<=0. Если для всех свободных клеток таблицы перевозок критерий оптимальности dij<0, то этот план перевозок является единственным. Если для некоторых свободных клеток таблицы перевозок критерий оптимальности dij=0, то этот оптимальный план перевозок не является единственным. Наконец, если имеются свободные клетки, для которых критерий оптимальности dij>0, то полученный план перевозок не является оптимальным. Алгоритм метода потенциалов состоит в следующем: каждому поставщику Ai ставится в соответствие некоторое число u, которое называется потенциалом Ai-того поставщика; каждому потребителю Bj ставится в соответствие некоторое число v, которое называется потенциалом Bj-того потребителя. Для каждой заполненной клетки, т. е. для каждой базисной переменной строится соотношение:
Получаем систему с числом уравнений, равным количеству базисных переменных. Из этой системы определяем неизвестные потенциалы ui и vj, полагая ui=0. Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются косвенные тарифы cij* по формуле:
Затем полученный план проверяют на оптимальность по критерию оптимальности dij. Если для каждой незаполненной клетки выполняется условие: dij<=cij*<=0, то исходный план является оптимальным. Если некоторые dij>0, то необходимо перейти к новому плану путем перемещения перевозки в клетку, отвечающую условию max(dij). Если таких клеток несколько, то выбирают любую из них.
Для правильного перемещения перевозок, чтобы не нарушить ограничения задачи, строят так называемый цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.
Цикл строится следующим образом: вычёркиваются (мысленно) все строки и столбцы, содержащие ровно одну заполненную клетку, при этом считается, что выбранная клетка без поставки является заполненной; все оставшиеся после вычеркивания клетки составляют цикл и лежат в его углах, они соединяются ломаной линией. В каждую клетку цикла, начиная с незаполненной, поочередно вписывают знаки “+” и “-“. В клетках с отрицательными знаками выбирается минимальная величина поставки, обозначаемая как D. В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “-“ поставки уменьшаются на величину D. При этом суммы поставок по строкам и столбцам не изменяются. В результате клетка, для которой строился цикл, станет занятой, а в одной из бывших занятых клеток окажется нулевая поставка и её надо объявить свободной. Общее количество заполненных клеток не изменится, следовательно, новый план перевозок является невырожденным.
Если в результате пересчета одновременно в нескольких ранее занятых клетках цикла поставки примут нулевые значения, то свободной объявляется лишь одна из них. Остальные считаются условно занятыми с нулевыми поставками.
Значения переменных, включенных в цикл, после пересчета переносятся в новую таблицу без изменений. Полученный новый план проверяется на оптимальность.
Такое улучшение плана можно проводить неоднократно до тех пор пока все критерии для незаполненных клеток окажутся dij<=0. Затем вычисляется оптимальная стоимость перевозок.
Пример решения транспортной задачи методом наименьшей стоимости
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи.
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 2 (26-24). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
транспортный задача поставщик потенциал
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;3): 4
Для этого в перспективную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;1): 4
Для этого в перспективную клетку (2;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;1): 2
Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Опорный план является оптимальным.
F(x) = 4*6 + 4*2 + 3*6 + 2*2 + 3*8 + 0*2 = 78
5. Блок-схема и решение задачи с помощью программы Excel
Добавляем преобразование - вводим столбец фиктивного поставщика
Решаем поставленную задачу методом линейного программирования с помощью табличного редактора Microsoft Excel
Подбор решения осуществляем с помощью команды «Сервис/поиск решения» и вводом параметров в диалоговом окне.
Математическая модель транспортной задачи:
С целью составления двойственной задачи переменные x ij в условии (2) заменим на u 1 , u 2 , u i ,.., u m , а переменные x ij в условия (3) на v 1 , v 2 , v j ,.., v n .
Поскольку каждая переменная x ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.
Требуется найти не отрицательные числа u i (при i = 1,2,…,m) и v j (при j = 1,2,..,n), обращающие в максимум целевую функцию
u i + v j ? c ij , i = 1,2,..,m; j = 1,2,..,n (4)
В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:
Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.
Числа u i , v j называются потенциалами. Причем число u i называется потенциалом поставщика, а число v j - потенциалом потребителя.
По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Проверим необходимое и достаточное условие разрешимости задачи.
?b = 1500 + 2500 + 2700 + 3300 = 10000
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 2000 (12000--10000). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a i , или b j .
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1 Для этого элемента запасы равны 6000, потребности 1500. Поскольку минимальным является 1500, то вычитаем его.
Для этого элемента запасы равны 4500, потребности 2700. Поскольку минимальным является 2700, то вычитаем его.
Для этого элемента запасы равны 3000, потребности 2500. Поскольку минимальным является 2500, то вычитаем его.
Для этого элемента запасы равны 500, потребности 3300. Поскольку минимальным является 500, то вычитаем его.
Для этого элемента запасы равны 3000, потребности 2800. Поскольку минимальным является 2800, то вычитаем его.
Для этого элемента запасы равны 1800, потребности 2000. Поскольку минимальным является 1800, то вычитаем его.
Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 1*1500 + 1*2700 + 0*1800 + 8*2800 + 0*200 + 1*2500 + 3*500 = 30600
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v i . по занятым клеткам таблицы, в которых
u 1 + v 1 = 1; 0 + v 1 = 1; v 1 = 1
u 1 + v 3 = 1; 0 + v 3 = 1; v 3 = 1
u 1 + v 5 = 0; 0 + v 5 = 0; v 5 = 0
u 2 + v 5 = 0; 0 + u 2 = 0; u 2 = 0
u 2 + v 4 = 8; 0 + v 4 = 8; v 4 = 8
u 3 + v 4 = 3; 8 + u 3 = 3; u 3 = -5
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v i > c ij
(1;2): 0 + 6 > 4; ? 12 = 0 + 6 - 4 = 2
(2;2): 0 + 6 > 2; ? 22 = 0 + 6 - 2 = 4
Выбираем максимальную оценку свободной клетки (2;2): 2
Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2; ).
Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 2500. Прибавляем 2500 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2500 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v i . по занятым клеткам таблицы, в которых
u 1 + v 1 = 1; 0 + v 1 = 1; v 1 = 1
u 1 + v 3 = 1; 0 + v 3 = 1; v 3 = 1
u 1 + v 5 = 0; 0 + v 5 = 0; v 5 = 0
u 2 + v 5 = 0; 0 + u 2 = 0; u 2 = 0
u 2 + v 2 = 2; 0 + v 2 = 2; v 2 = 2
u 2 + v 4 = 8; 0 + v 4 = 8; v 4 = 8
u 3 + v 4 = 3; 8 + u 3 = 3; u 3 = -5
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + v i <= c ij .
F(x) = 1*1500 + 1*2700 + 0*1800 + 2*2500 + 8*300 + 0*200 + 3*3000 = 20600
Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).
G = 0*6000 + 0*3000 -5*3000 + 1*1500 + 2*2500 + 1*2700 + 8*3300 + 0*2000 = 20600
Из 1-го склада необходимо груз направить в 1-й магазин (1500), в 3-й магазин (2700)
Из 2-го склада необходимо груз направить в 2-й магазин (2500), в 4-й магазин (300)
Из 3-го склада необходимо весь груз направить в 4-й магазин
На 1-ом складе остался невостребованным груз в количестве 1800 ед.
Оптимальный план является вырожденным, так как базисная переменная x 15 =0.
На 2-ом складе остался невостребованным груз в количестве 200 ед.
Оптимальный план является вырожденным, так как базисная переменная x 25 =0.
Мне была поставлена задача составить программу для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей.
Все вводимые данные и начальный базис выводятся в виде таблицы.
В программе удобный и понятный пользовательский интерфейс. Для ввода данных используется клавиатура. Данные, выводимые программой, соответствуют тем, что получены при расчетах без использования компьютера. Таким образом, поставленная задача была выполнена.
Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения. контрольная работа [118,5 K], добавлен 11.04.2012
Основные этапы решения транспортной задачи, использование метода потенциалов. Алгоритм решения методом аппроксимации Фогеля. Процедура построения цикла. Планирование перевозок из конечного числа пунктов отправления в конечное число пунктов назначения. контрольная работа [32,6 K], добавлен 26.04.2011
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования. дипломная работа [2,4 M], добавлен 20.11.2010
Программа для решения транспортной задачи. Метод потенциалов, его математический смысл и порядок действий по его применению. Математические методы решения транспортных задач. Вычисление стоимости перевозок, расхода топлива, общей прибыли и окупаемости. курсовая работа [33,7 K], добавлен 20.11.2008
Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения. курсовая работа [2,0 M], добавлен 12.02.2013
Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса. курсовая работа [232,4 K], добавлен 01.06.2009
Математическая постановка транспортной задачи открытой модели методом потенциалов при известных показателях запаса груза поставщика и потребности потребителя; ее решение ручным способом и с помощью компьютерной программы, написанной в среде Delphi. курсовая работа [167,2 K], добавлен 16.01.2011
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Решение линейного программирования отчет по практике. Программирование, компьютеры и кибернетика.
Реферат: Определение горизонтальной составляющей магнитного поля Земли
Финансовые Посредники Реферат
Эссе На Тему Победа
Реферат по теме Церковное пение
Дипломная работа по теме Формирование информационных компетенций учащихся в процессе обучения физики
Реферат: Victorian Literature Essay Research Paper
Дипломная работа: Профилактика правонарушений среди осужденных
Курсовая работа: Технология швейного производства
Курсовая работа по теме Развитие малого предпринимательства в Карагандинской области
Метафизика Всеединства Владимира Соловьева Сочинение Философия
Практическое задание по теме Внешкольный досуг для детей старшего школьного возраста
Дипломная работа по теме Агрессивное поведение младших школьников
Контрольная работа по теме Политический портрет Нахимова П.С.
Сочинение На Тему Польза Науки
Книга: У наш час юристу як ніколи потрібно мати силу
Курсовая Работа По Экономике Устойчивого Развития
Государственные Предприятия Курсовая
Сочинения Сталина Читать
Гдз Rainbow English 7 Контрольные Работы
Контрольная работа по теме Паутинообразная модель. Построение имитационной моделей: паутинообразная, выбора инвестиционного проекта. Межотраслевой баланс производства и распределения продукции
Теоретические вопросы осуществления и защиты гражданских прав - Государство и право дипломная работа
Оценка контрольный работ - Программирование, компьютеры и кибернетика курсовая работа
Культура Арабского Востока - Культура и искусство реферат