Решение линейного программирования

 

Министерство образования науки Российской Федерации

НОУ ВПО Московский институт государственного и корпоративного управления

Отчет

По дисциплине «Компьютерное моделирование в экономике».

Тема: «Решение линейного программирования».

Выполнила Кац О.П.

Проверила Дробышева А.П.

Содержание

Введение

. Цель

. Краткие теоретические сведения о методе

. Постановка задачи

. Аналитическое решение задачи

5. Блок-схема и решение задачи с помощью программы Excel

6. Результаты решения задачи

Выводы

1. Цель

Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования - области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями. Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.

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

2. Краткие теоретические сведения о методе

Линейное программирование: общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

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

Основную задачу можно свести к канонической путём введения дополнительных переменных.

Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств

Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты с обратным знаком.

3. Постановка задачи

Компания владеет тремя заводами: «А», «В», «С», с соответствующими стоимостями производства на единицу объема «а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. При заданных стоимостях перевозок составить оптимальный план производства и распределения в магазины.

Пример:

WXYZAA1BB2CC3W1X2 Y3 Z4

4. Аналитическое решение задачи

Алгоритм метода потенциалов

План транспортной задачи является оптимальным, если для всех свободных клеток таблицы перевозок значение критерия оптимальности dij<=0. Если для всех свободных клеток таблицы перевозок критерий оптимальности dij<0, то этот план перевозок является единственным. Если для некоторых свободных клеток таблицы перевозок критерий оптимальности dij=0, то этот оптимальный план перевозок не является единственным. Наконец, если имеются свободные клетки, для которых критерий оптимальности dij>0, то полученный план перевозок не является оптимальным. Алгоритм метода потенциалов состоит в следующем: каждому поставщику Ai ставится в соответствие некоторое число u, которое называется потенциалом Ai-того поставщика; каждому потребителю Bj ставится в соответствие некоторое число v, которое называется потенциалом Bj-того потребителя. Для каждой заполненной клетки, т. е. для каждой базисной переменной строится соотношение:

+vj=cij

Получаем систему с числом уравнений, равным количеству базисных переменных. Из этой системы определяем неизвестные потенциалы ui и vj, полагая ui=0. Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются косвенные тарифы cij* по формуле:

* = ui+vj.

Затем полученный план проверяют на оптимальность по критерию оптимальности dij. Если для каждой незаполненной клетки выполняется условие: dij<=cij*<=0, то исходный план является оптимальным. Если некоторые dij>0, то необходимо перейти к новому плану путем перемещения перевозки в клетку, отвечающую условию max(dij). Если таких клеток несколько, то выбирают любую из них.

Для правильного перемещения перевозок, чтобы не нарушить ограничения задачи, строят так называемый цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.

Цикл строится следующим образом: вычёркиваются (мысленно) все строки и столбцы, содержащие ровно одну заполненную клетку, при этом считается, что выбранная клетка без поставки является заполненной; все оставшиеся после вычеркивания клетки составляют цикл и лежат в его углах, они соединяются ломаной линией. В каждую клетку цикла, начиная с незаполненной, поочередно вписывают знаки + и -. В клетках с отрицательными знаками выбирается минимальная величина поставки, обозначаемая как D. В те вершины, которые имеют знак + прибавляется поставка D, а в вершинах со знаком - поставки уменьшаются на величину D. При этом суммы поставок по строкам и столбцам не изменяются. В результате клетка, для которой строился цикл, станет занятой, а в одной из бывших занятых клеток окажется нулевая поставка и её надо объявить свободной. Общее количество заполненных клеток не изменится, следовательно, новый план перевозок является невырожденным.

Если в результате пересчета одновременно в нескольких ранее занятых клетках цикла поставки примут нулевые значения, то свободной объявляется лишь одна из них. Остальные считаются условно занятыми с нулевыми поставками.

Значения переменных, включенных в цикл, после пересчета переносятся в новую таблицу без изменений. Полученный новый план проверяется на оптимальность.

Такое улучшение плана можно проводить неоднократно до тех пор пока все критерии для незаполненных клеток окажутся dij<=0. Затем вычисляется оптимальная стоимость перевозок.

Пример решения транспортной задачи методом наименьшей стоимости

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

1234Запасы1124362438583276310Потребности4688

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 2 (26-24). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

1234Запасы1124362438583276310400002Потребности4688

. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

транспортный задача поставщик потенциал

1234Запасы11[4]2[2]436[0]243[4]8[4]58[0]3276[2]3[8]10[0]4000[2]02[0]Потребности4[0]6[0]8[0]8[0]

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

. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1=1u2=2u3=7u4=4v1=01[4]2[2]43v2=143[4]8[4]5v3=-1276[2]3[8]v4=-7000[2]0

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(1;3): 0 + 7 > 4

(1;4): 0 + 4 > 3

Выбираем максимальную оценку свободной клетки (1;3): 4

Для этого в перспективную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

1234Запасы11[4]2[2][-]4[+]36243[4][+]8[4][-]583276[2]3[8]104000[2]02Потребности4688

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1234Запасы11[4]24[2]36243[6]8[2]583276[2]3[8]104000[2]02Потребности4688

. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Таблица

u1=1u2=-1u3=4u4=1v1=01[4]24[2]3v2=443[6]8[2]5v3=2276[2]3[8]v4=-4000[2]0

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(2;1): 4 + 1 > 4

(3;1): 2 + 1 > 2

Выбираем максимальную оценку свободной клетки (2;1): 4

Для этого в перспективную клетку (2;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

1234Запасы11[4][-]24[2][+]3624[+]3[6]8[2][-]583276[2]3[8]104000[2]02Потребности4688

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках.

1234Запасы11[2]24[4]3624[2]3[6]8583276[2]3[8]104000[2]02Потребности46884. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1=1u2=0u3=4u4=1v1=01[2]24[4]3v2=34[2]3[6]85v3=2276[2]3[8]v4=-4000[2]0

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij

(3;1): 2 + 1 > 2

Выбираем максимальную оценку свободной клетки (3;1): 2

Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

1234Запасы11[2][-]24[4][+]3624[2]3[6]85832[+]76[2][-]3[8]104000[2]02Потребности4688

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1234Запасы1124[6]3624[2]3[6]85832[2]76[0]3[8]104000[2]02Потребности4688

. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1=0u2=-1u3=4u4=1v1=0124[6]3v2=44[2]3[6]85v3=22[2]763[8]v4=-4000[2]0

Опорный план является оптимальным.

Затраты составят:

F(x) = 4*6 + 4*2 + 3*6 + 2*2 + 3*8 + 0*2 = 78

5. Блок-схема и решение задачи с помощью программы Excel

Решение поставленной задачи

Составляем матрицу коэффициентов

WXYZА14196000В92283000С617330001500250027003300

Добавляем преобразование - вводим столбец фиктивного поставщика

WXYZФА141906000В922803000С61730300015002500270033002000Решаем поставленную задачу методом линейного программирования с помощью табличного редактора Microsoft Excel

Подбор решения осуществляем с помощью команды «Сервис/поиск решения» и вводом параметров в диалоговом окне.

6. Результаты решения

Математическая модель транспортной задачи:

= ??cijxij, (1)

при условиях:

?xij = ai, i = 1,2,…, m, (2)

?xij = bj, j = 1,2,…, n, (3)

С целью составления двойственной задачи переменные xij в условии (2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3) на v1, v2, vj,.., vn.

Поскольку каждая переменная xij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию

= ?aiui + ?bjvj

при условии

ui + vj ? cij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:i + vj ? cij, если xij = 0,i + vj = cij, если xij ? 0,

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

Числа ui , vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj - потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

1234Запасы114196000292283000361733000Потребности1500250027003300

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 6000 + 3000 + 3000 = 12000

?b = 1500 + 2500 + 2700 + 3300 = 10000

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 2000 (12000-10000). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу.

12345Запасы114190600029228030003617303000Потребности15002500270033002000

Этап I. Поиск первого опорного плана.

. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.

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

Искомый элемент равен 1 Для этого элемента запасы равны 6000, потребности 1500. Поскольку минимальным является 1500, то вычитаем его.11 = min(6000,1500) = 1500.

141906000 - 1500 = 4500x22803000x173030001500 - 1500 = 025002700330020000

Искомый элемент равен 1

Для этого элемента запасы равны 4500, потребности 2700. Поскольку минимальным является 2700, то вычитаем его.13 = min(4500,2700) = 2700.

141904500 - 2700 = 1800x2x803000x1x303000025002700 - 2700 = 0330020000Искомый элемент равен 1

Для этого элемента запасы равны 3000, потребности 2500. Поскольку минимальным является 2500, то вычитаем его.32 = min(3000,2500) = 2500.

1x1901800xxx803000x1x303000 - 2500 = 50002500 - 2500 = 00330020000

Искомый элемент равен 3

Для этого элемента запасы равны 500, потребности 3300. Поскольку минимальным является 500, то вычитаем его.34 = min(500,3300) = 500.

1x1901800xxx803000x1x3x500 - 500 = 00003300 - 500 = 280020000

Искомый элемент равен 8

Для этого элемента запасы равны 3000, потребности 2800. Поскольку минимальным является 2800, то вычитаем его.24 = min(3000,2800) = 2800.

1x1x01800xxx803000 - 2800 = 200x1x3x00002800 - 2800 = 020000

Искомый элемент равен 0

Для этого элемента запасы равны 1800, потребности 2000. Поскольку минимальным является 1800, то вычитаем его.15 = min(1800,2000) = 1800.

1x1x01800 - 1800 = 0xxx80200x1x3x000002000 - 1800 = 2000

Искомый элемент равен 0

Для этого элемента запасы равны 200, потребности 200. Поскольку минимальным является 200, то вычитаем его.25 = min(200,200) = 200.

1x1x00xxx80200 - 200 = 0x1x3x00000200 - 200 = 00

12345Запасы11[1500]41[2700]90[1800]600029228[2800]0[200]3000361[2500]73[500]03000Потребности15002500270033002000

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

. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:(x) = 1*1500 + 1*2700 + 0*1800 + 8*2800 + 0*200 + 1*2500 + 3*500 = 30600

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых

i + vi = cij,

полагая, что u1 = 0.1 + v1 = 1; 0 + v1 = 1; v1 = 11 + v3 = 1; 0 + v3 = 1; v3 = 1

u1 + v5 = 0; 0 + v5 = 0; v5 = 02 + v5 = 0; 0 + u2 = 0; u2 = 02 + v4 = 8; 0 + v4 = 8; v4 = 8

u3 + v4 = 3; 8 + u3 = 3; u3 = -5

v1=1v2=6v3=1v4=8v5=0u1=01[1500]41[2700]90[1800]u2=09228[2800]0[200]u3=-561[2500]73[500]0Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(1;2): 0 + 6 > 4; ?12 = 0 + 6 - 4 = 2

(2;2): 0 + 6 > 2; ?22 = 0 + 6 - 2 = 4(2,4) = 4

Выбираем максимальную оценку свободной клетки (2;2): 2

Для этого в перспективную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

12345Запасы11[1500]41[2700]90[1800]6000292[+]28[2800][-]0[200]3000361[2500][-]73[500][+]03000Потребности15002500270033002000Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 2500. Прибавляем 2500 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2500 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

12345Запасы11[1500]41[2700]90[1800]6000292[2500]28[300]0[200]300036173[3000]03000Потребности15002500270033002000

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которыхi + vi = cij,

полагая, что u1 = 0.

u1 + v1 = 1; 0 + v1 = 1; v1 = 11 + v3 = 1; 0 + v3 = 1; v3 = 11 + v5 = 0; 0 + v5 = 0; v5 = 02 + v5 = 0; 0 + u2 = 0; u2 = 02 + v2 = 2; 0 + v2 = 2; v2 = 22 + v4 = 8; 0 + v4 = 8; v4 = 8

u3 + v4 = 3; 8 + u3 = 3; u3 = -5

v1=1v2=2v3=1v4=8v5=0u1=01[1500]41[2700]90[1800]u2=092[2500]28[300]0[200]u3=-56173[3000]0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:(x) = 1*1500 + 1*2700 + 0*1800 + 2*2500 + 8*300 + 0*200 + 3*3000 = 20600

Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).= 06000 + 03000 -53000 + 11500 + 22500 + 12700 + 83300 + 02000 = 20600

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (1500), в 3-й магазин (2700)

Из 2-го склада необходимо груз направить в 2-й магазин (2500), в 4-й магазин (300)

Из 3-го склада необходимо весь груз направить в 4-й магазин

На 1-ом складе остался невостребованным груз в количестве 1800 ед.

Оптимальный план является вырожденным, так как базисная переменная x15=0.

На 2-ом складе остался невостребованным груз в количестве 200 ед.

Оптимальный план является вырожденным, так как базисная переменная x25=0.

Вûâîäû

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

Все вводимые данные и начальный базис выводятся в виде таблицы.

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

Министерство образования науки Российской Федерации НОУ ВПО Московский институт государственного и корпоративного управления

Больше работ по теме: