Математическая постановка транспортной задачи линейного программирования
Основные понятия транспортных задач. Методы определения первоначального опорного плана решения. Распределительный и венгерский способ. Решение в качестве примера конкретной транспортной задачи об оптимальных перевозках с помощью средств Ms Excel.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 20.10.2010 |
| Размер файла | 404,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Содержание
Введение
1. Основные понятия транспортных задач
2. Методы определения первоначального опорного плана
2.1 Метод вычеркивания
2.2 Метод северо-западного угла
2.3 Метод минимальной стоимости
2.4 Переход от одного опорного решения к другому
3. Распределительный метод
4. Венгерский метод
5. Метод решения задачи об оптимальных перевозках средствами Ms Excel
6. Решение транспортной задачи
6.1 Постановка транспортной задачи
6.2 Решение задачи
Заключение
Список литературы
Введение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования и метод решения задач средствами Ms Excel. В курсовой работе будут рассмотрены основные понятия транспортных задач, методы определения первоначального опорного плана, распределительный и венгерский методы решения, а также с помощью средств Ms Excel будет подробно рассмотрено в качестве примера решение конкретной транспортной задачи.
1. Основные понятия транспортных задач
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A1,A2,…Am n потребителям B1,B2,…Bn, не превышающий объем производства в каждом пункте поставки. Транспортная задача была впервые сформулирована Хитчкоком и с тех пор применяется для решения практических задач доставки и распределения однородных продуктов.
Различают два типа транспортных задач Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г., с.56:
по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию);
по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a1,a2,…,am, а общее количество имеющегося в наличии груза a = = a1+a2+…+am; заказы каждого из потребителей (потребности) обозначим соответственно b1,b2,…,bn, а общее количество потребностей b = b1+b2+…+bn.
Тогда при условии a = b мы имеем сбалансированную задачу (закрытая модель), а при условии a ? b - несбалансированную (открытая модель).
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a > b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a < b).
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например - склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986, 175с.:
Переменное xij означает количество груза, перевозимого с базы Ai потребителю Bj: совокупность этих величин образует матрицу (матрицу перевозок). Очевидно, переменные xij должны удовлетворять условиям:
(*)
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы cij, т. е. стоимость перевозки единицы груза с базы Aj потребителю Bj. Совокупность тарифов cij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных xij:
(**)
Требуется в области допустимых решений системы уравнений (*) найти решение, минимизирующее линейную функцию (**):
Далее считаем, что задача сбалансированная. Таким образом, математическую модель задачи можно записать так Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. Пособие / Новосиб. Гос.ун-т. Новосибирск, 2005. с.10:
, (1)
, i = 1,…,m , (2)
, j = 1,…, n, (3)
, i = 1,…,m, j = 1,…,n (4)
Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).
Математическая модель транспортной задачи может быть записана в векторном виде Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3):
.……………………………………………………
А = (6).
……………………………………………………
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая - на (m+j)-м месте.
Обозначим через вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:
(7)
=, (8)
, i=1,…,m, j=1,…,n (9)
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами.
2. Методы определения первоначального опорного плана
Опорным решением транспортной задачи называется любое допустимое решение, для которого вектора-условия, соответствующие положительным координатам, линейно независимы Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002., с.47.
Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1.
Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные - незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная , которой соответствует вектор-условие .
Для того чтобы избежать трудоемких вычислений при проверке линейной независимости векторов-условий, соответствующих положительным координатам допустимого решения, вводят понятие цикла. Циклы также используются для перехода от одного опорного решения к другому.
Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002., с.50.
Для того чтобы система векторов-условий транспортной задачи были линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл. Допустимое решение транспортной задачи Х=(), i=1,2,,…,m, j=1,2,…,n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.
2.1 Метод вычеркивания
Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.
Пусть допустимое решение транспортной задачи, которое имеет m+n-1 отличную от нуля координату, записано в таблицу. Чтобы данное решение было опорным, векторы-условия, соответствующие положительным координатам, должны быть линейно независимы. Для этого занятые решением клетки таблицы должны быть расположены так, чтобы из них нельзя было образовать цикл.
Строка или столбец таблицы с одной занятой клеткой не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждой строке или в столбце. Следовательно, можно вычеркнуть сначала либо все строки таблицы, содержащие по одной занятой клетке, либо все столбцы, содержащие по одной занятой клетке, далее вернуться к столбцам (строкам) и продолжить их вычеркивание. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов-условий линейно независима, а решение является опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов-условий линейно зависима, а решение не является опорным.
Ниже приведены примеры “вычеркиваемого” (опорного) и ”невычеркиваемого” (неопорного) решений:
;
“вычеркиваемое” “невычеркиваемое”
Существует ряд методов построения начального опорного решения.
2.2 Метод северо-западного угла Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г., с.69
В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Осуществляется это таким образом:
если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj, ;
если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki, ;
если , то и исключается либо i-й поставщик, , k=1, 2, …, n, kj, , либо j-й потребитель, , k=1, 2, …, m, ki, .
Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому опорное решение, построенное данным методом, может быть далеко от оптимального.
2.3 Метод минимальной стоимости Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,…,m, j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.
2.4 Переход от одного опорного решения к другому
В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решений. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.
Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным - знак «-» (рис 1.)
1 2
+ -
- 5 +
6
+ -
3 4
Рис 1.
Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на .
Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину = получится опорное решение.
3. Распределительный метод Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
Один из наиболее простых методов решения транспортной задачи - распределительный метод.
Пусть для транспортной задачи найдено начальное опорное решение и вычислено значение целевой функции на этом решении. Для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину =, можно получить новое опорное решение Х2.
Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равно разности двух сумм: =, где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «-».
В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции, а в клетках, отмеченных знаком «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.
Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. <0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z() на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие = 0. (10)
Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину =. В результате получится новое опорное решение.
Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очевидность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимости перевозок , так как решается задача на нахождение минимума.
4. Венгерский метод
Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.
Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 = {xij[0]}, элементы которой неотрицательны и удовлетворяют неравенствам:
, i = 1,…,m ,
, j = 1,…, n,
Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk = {xij[k]}. Близость этой матрицы к решению задачи характеризует число Dk -- суммарная невязка матрицы Хk:
В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.
Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).
Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности.
5. Метод решения задачи об оптимальных перевозках средствами Ms Excel
Нахождение оптимального плана перевозок с применением компьютерной программы Ms Excel осуществляется посредством функции «Поиск решения».
Схема выполнения Павлова Т.Н., Ракова О.А. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002.:
Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (рис. 5.1), а также матрицу, которая должна будет отображать искомый план перевозок (рис. 5.2.).
В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.
Таблицу «План перевозок» создать с пустыми полями (заполненными единицами), заранее заданного числового формата. В ячейках запасов (потребностей) каждого поставщика (потребителя) ввести формулу, выполняющую суммирование всех возможных поставок этого поставщика (потребителя).
Рис. 5.1. Фрагмент окна программы MS Excel: Модель таблицы «Стоимость перевозок".
Рис. 5.2. Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок».
В ячейке целевой функции ввести формулу, высчитывающую сумму произведений элементов матрицы «Стоимость перевозок» и соответствующих элементов матрицы «План перевозок».
В диалоговом окне функции «Поиск решения» установить необходимые ограничения, в целевой ячейке указать адрес ячейки с формулой целевой функции и установить ее равной минимальному значению, в качестве изменяемых ячеек выбрать диапазон всех элементов матрицы «План перевозок». Ограничения в «Поиске решений» заключаются в необходимости равенства запасов (потребностей), в матрице «План перевозок» соответствующим запасам и потребностям, указанным в матрице «Стоимость перевозок». Также все элементы матрицы «План перевозок» должны быть неотрицательными и целочисленными.
В диалоговом окне «Параметры поиска решений» установить параметр «Линейная модель» и число итераций, равное 100.
Выполнить функцию «Поиск решения» нажатием на кнопку «Выполнить». В качестве отчета по результатам выбрать необходимый пункт в списке «Тип отчета» диалогового окна «Результаты поиска решения».
После выполнения вышеуказанных действий при условии, что задача имеет решение, т.е. оптимальный план перевозок с указанием объемов поставок в каждой ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.
6. Решение транспортной задачи
6.1 Постановка транспортной задачи
Есть 3 поставщика с мощностями с1, с2, с3 и 5 потребителей (их спрос d1, d2, d3, d4, d5 соответственно) некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей А размера 3Ч5. Найти оптимальный план поставок.
,
с1 = 40, с2 = 90, с3 = 50,
d1 = 20, d2 = 25, d3 = 65, d4 = 50, d5 = 20.
6.2 Решение задачи
Изобразим матричную запись задачи (табл. 6.2.1):
Модель закрытая, т.к. запасы равны потреблению:
|
Стоимость перевозки единицы продукции |
Объемы производства |
|||||||
|
3 |
1 |
1 |
4 |
5 |
40 |
|||
|
6 |
2 |
4 |
8 |
1 |
90 |
|||
|
4 |
7 |
6 |
9 |
2 |
50 |
Всего |
||
|
Объемы потребления |
20 |
25 |
65 |
50 |
20 |
180 |
||
|
Всего |
180 |
Создадим в окне программы Ms Excel 2 матрицы «План перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис. 6.2.1.).
|
План поставок |
Стоимость перевозок |
|||||||||||||||||
|
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
|||||
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
20 |
25 |
65 |
50 |
20 |
|||||
|
A1 |
0 |
0 |
0 |
0 |
0 |
0 |
A1 |
40 |
3 |
1 |
1 |
4 |
5 |
|||||
|
A2 |
0 |
0 |
0 |
0 |
0 |
0 |
A2 |
90 |
6 |
2 |
4 |
8 |
1 |
ЦФ |
||||
|
A3 |
0 |
0 |
0 |
0 |
0 |
0 |
A3 |
50 |
4 |
7 |
6 |
9 |
2 |
0 |
Рис. 6.2.1. Фрагмент окна программы Ms Excel: Матрицы «План перевозок» и «Стоимость перевозок»
В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы, суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ(C4:G4), C3=СУММ(C4:C6).
В ячейку целевой функции (R6) введем =СУММПРОИЗВ(C4:G6;L4:P6).
Задача решается при помощи меню Сервис, пункт Поиск решения.
В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения и ссылки на необходимые ячейки (рис. 6.2.2.).
Рис. 6.2.2. Диалоговое окно «Поиск решения»
В диалоговом окне «Параметры поиска решения» установить необходимые параметры (рис. 6.2.3.):
Рис. 6.2.3. Диалоговое окно «Параметры поиска решения»
После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» нажать «Сохранить найденное решение», выделить необходимые типы отчетов и нажать «ОК».
|
План поставок |
Стоимость перевозок |
|||||||||||||||||
|
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
|||||
|
|
|
20 |
25 |
65 |
50 |
20 |
|
|
20 |
25 |
65 |
50 |
20 |
|||||
|
A1 |
40 |
0 |
0 |
0 |
40 |
0 |
A1 |
40 |
3 |
1 |
1 |
4 |
5 |
|||||
|
A2 |
90 |
0 |
25 |
65 |
0 |
0 |
A2 |
90 |
6 |
2 |
4 |
8 |
1 |
ЦФ |
||||
|
A3 |
50 |
20 |
0 |
0 |
10 |
20 |
A3 |
50 |
4 |
7 |
6 |
9 |
2 |
680 |
Рис. 6.2.4. Фрагмент окна программы Ms Excel: Результат поиска решения
Полученное значение целевой функции равно 680.
Можно создать отчет по проведению данного решения, в котором будут приведены данные о ячейках, их начальных и конечных значениях, формулах и сведениях о размерах реализованного сырья. При необходимости итерации можно просмотреть, выбрав пункт «Показывать результаты итераций».
Ответ
Затраты на перевозку всей продукции - 680 ден. ед.
Оптимальный план поставок:
|
|
B1 |
B2 |
B3 |
B4 |
B5 |
|
|
A1 |
40 |
|||||
|
A2 |
25 |
65 |
||||
|
A3 |
20 |
10 |
20 |
Заключение
Описанная в курсовой работе транспортная задача и методы ее решения - только отдельный пример огромного множества задач линейного программирования. Цель транспортной задачи - разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затрата предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Список литературы
1. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
2. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986, 319с.
3. Павлова Т.Н., Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
4. Павлова Т.Н., Ракова О.А. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002.
5. Ермаков В.И. Сборник задач по высшей математике для экономистов. - М.: Издательство Инфра, 2001, 574с.
6. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.
7. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
8. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. Пособие / Новосиб. Гос. ун-т. Новосибирск, 2005. 78с.
9. Береснев В.Л., Дементьев В.Т. Исследование операций. Введение. Учебное пособие. НГУ, 1979, I - 92.
10. Авдей А.Н. Анализ данных в Excel: под ред. Проф. А.А. Прихожего. - Мн.: БГПА, 2000
Подобные документы
Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа [514,8 K], добавлен 04.02.2011Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Сущность и назначение основных алгоритмов оптимизации. Линейное программирование. Постановка и аналитический метод решения параметрической транспортной задачи, математическая модель. Метод решения задачи об оптимальных перевозках средствами MS Excel.
курсовая работа [465,6 K], добавлен 24.04.2009Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015
