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

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

Рубрика Программирование, компьютеры и кибернетика
Вид отчет по практике
Язык русский
Дата добавления 06.12.2013
Размер файла 991,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

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

Отчет

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

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

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

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

Содержание

Введение

1. Цель

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

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

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

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. При заданных стоимостях перевозок составить оптимальный план производства и распределения в магазины.

Пример:

W

X

Y

Z

A

A1

B

B2

C

C3

W1X2 Y3 Z4

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

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

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

ui+vj=cij

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

cij* = ui+vj.

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

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

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

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

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

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

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

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

1

2

3

4

Запасы

1

1

2

4

3

6

2

4

3

8

5

8

3

2

7

6

3

10

Потребности

4

6

8

8

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

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

1

2

3

4

Запасы

1

1

2

4

3

6

2

4

3

8

5

8

3

2

7

6

3

10

4

0

0

0

0

2

Потребности

4

6

8

8

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

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

1

2

3

4

Запасы

1

1[4]

2[2]

4

3

6[0]

2

4

3[4]

8[4]

5

8[0]

3

2

7

6[2]

3[8]

10[0]

4

0

0

0[2]

0

2[0]

Потребности

4[0]

6[0]

8[0]

8[0]

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

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

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

u1=1

u2=2

u3=7

u4=4

v1=0

1[4]

2[2]

4

3

v2=1

4

3[4]

8[4]

5

v3=-1

2

7

6[2]

3[8]

v4=-7

0

0

0[2]

0

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

(1;3): 0 + 7 > 4 

(1;4): 0 + 4 > 3 

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

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

1

2

3

4

Запасы

1

1[4]

2[2][-]

4[+]

3

6

2

4

3[4][+]

8[4][-]

5

8

3

2

7

6[2]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

1

2

3

4

Запасы

1

1[4]

2

4[2]

3

6

2

4

3[6]

8[2]

5

8

3

2

7

6[2]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

Таблица

u1=1

u2=-1

u3=4

u4=1

v1=0

1[4]

2

4[2]

3

v2=4

4

3[6]

8[2]

5

v3=2

2

7

6[2]

3[8]

v4=-4

0

0

0[2]

0

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

(2;1): 4 + 1 > 4 

(3;1): 2 + 1 > 2 

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

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

1

2

3

4

Запасы

1

1[4][-]

2

4[2][+]

3

6

2

4[+]

3[6]

8[2][-]

5

8

3

2

7

6[2]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

1

2

3

4

Запасы

1

1[2]

2

4[4]

3

6

2

4[2]

3[6]

8

5

8

3

2

7

6[2]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

u1=1

u2=0

u3=4

u4=1

v1=0

1[2]

2

4[4]

3

v2=3

4[2]

3[6]

8

5

v3=2

2

7

6[2]

3[8]

v4=-4

0

0

0[2]

0

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

(3;1): 2 + 1 > 2 

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

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

1

2

3

4

Запасы

1

1[2][-]

2

4[4][+]

3

6

2

4[2]

3[6]

8

5

8

3

2[+]

7

6[2][-]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

1

2

3

4

Запасы

1

1

2

4[6]

3

6

2

4[2]

3[6]

8

5

8

3

2[2]

7

6[0]

3[8]

10

4

0

0

0[2]

0

2

Потребности

4

6

8

8

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

u1=0

u2=-1

u3=4

u4=1

v1=0

1

2

4[6]

3

v2=4

4[2]

3[6]

8

5

v3=2

2[2]

7

6

3[8]

v4=-4

0

0

0[2]

0

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

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

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

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

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

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

W

X

Y

Z

А

1

4

1

9

6000

В

9

2

2

8

3000

С

6

1

7

3

3000

1500

2500

2700

3300

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

W

X

Y

Z

Ф

А

1

4

1

9

0

6000

В

9

2

2

8

0

3000

С

6

1

7

3

0

3000

1500

2500

2700

3300

2000

Решаем поставленную задачу методом линейного программирования с помощью табличного редактора Microsoft Excel

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

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

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

F = ??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), обращающие в максимум целевую функцию

G = ?aiui + ?bjvj

при условии

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

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

ui + vj ? cij, если xij = 0,

ui + vj = cij, если xij ? 0,

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

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

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

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

1

2

3

4

Запасы

1

1

4

1

9

6000

2

9

2

2

8

3000

3

6

1

7

3

3000

Потребности

1500

2500

2700

3300

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

?a = 6000 + 3000 + 3000 = 12000

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

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

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

1

2

3

4

5

Запасы

1

1

4

1

9

0

6000

2

9

2

2

8

0

3000

3

6

1

7

3

0

3000

Потребности

1500

2500

2700

3300

2000

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

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

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

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

x11 = min(6000,1500) = 1500.

1

4

1

9

0

6000 - 1500 = 4500

x

2

2

8

0

3000

x

1

7

3

0

3000

1500 - 1500 = 0

2500

2700

3300

2000

0

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

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

x13 = min(4500,2700) = 2700.

1

4

1

9

0

4500 - 2700 = 1800

x

2

x

8

0

3000

x

1

x

3

0

3000

0

2500

2700 - 2700 = 0

3300

2000

0

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

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

x32 = min(3000,2500) = 2500.

1

x

1

9

0

1800

x

x

x

8

0

3000

x

1

x

3

0

3000 - 2500 = 500

0

2500 - 2500 = 0

0

3300

2000

0

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

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

x34 = min(500,3300) = 500.

1

x

1

9

0

1800

x

x

x

8

0

3000

x

1

x

3

x

500 - 500 = 0

0

0

0

3300 - 500 = 2800

2000

0

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

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

x24 = min(3000,2800) = 2800.

1

x

1

x

0

1800

x

x

x

8

0

3000 - 2800 = 200

x

1

x

3

x

0

0

0

0

2800 - 2800 = 0

2000

0

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

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

x15 = min(1800,2000) = 1800.

1

x

1

x

0

1800 - 1800 = 0

x

x

x

8

0

200

x

1

x

3

x

0

0

0

0

0

2000 - 1800 = 200

0

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

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

x25 = min(200,200) = 200.

1

x

1

x

0

0

x

x

x

8

0

200 - 200 = 0

x

1

x

3

x

0

0

0

0

0

200 - 200 = 0

0

1

2

3

4

5

Запасы

1

1[1500]

4

1[2700]

9

0[1800]

6000

2

9

2

2

8[2800]

0[200]

3000

3

6

1[2500]

7

3[500]

0

3000

Потребности

1500

2500

2700

3300

2000

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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 1*1500 + 1*2700 + 0*1800 + 8*2800 + 0*200 + 1*2500 + 3*500 = 30600

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

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

ui + vi = cij,

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

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

u1 + v5 = 0; 0 + v5 = 0; v5 = 0

u2 + v5 = 0; 0 + u2 = 0; u2 = 0

u2 + v4 = 8; 0 + v4 = 8; v4 = 8

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

v1=1

v2=6

v3=1

v4=8

v5=0

u1=0

1[1500]

4

1[2700]

9

0[1800]

u2=0

9

2

2

8[2800]

0[200]

u3=-5

6

1[2500]

7

3[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

max(2,4) = 4

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

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

1

2

3

4

5

Запасы

1

1[1500]

4

1[2700]

9

0[1800]

6000

2

9

2[+]

2

8[2800][-]

0[200]

3000

3

6

1[2500][-]

7

3[500][+]

0

3000

Потребности

1500

2500

2700

3300

2000

Цикл приведен в таблице (2,2; 2,4; 3,4; 3,2; ).

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

1

2

3

4

5

Запасы

1

1[1500]

4

1[2700]

9

0[1800]

6000

2

9

2[2500]

2

8[300]

0[200]

3000

3

6

1

7

3[3000]

0

3000

Потребности

1500

2500

2700

3300

2000

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

ui + vi = cij,

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

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

u1 + v5 = 0; 0 + v5 = 0; v5 = 0

u2 + v5 = 0; 0 + u2 = 0; u2 = 0

u2 + v2 = 2; 0 + v2 = 2; v2 = 2

u2 + v4 = 8; 0 + v4 = 8; v4 = 8

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

v1=1

v2=2

v3=1

v4=8

v5=0

u1=0

1[1500]

4

1[2700]

9

0[1800]

u2=0

9

2[2500]

2

8[300]

0[200]

u3=-5

6

1

7

3[3000]

0

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

Минимальные затраты составят:

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 ед.

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

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

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

Выводы

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

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

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

Размещено на Allbest.ru


Подобные документы

  • Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Основные этапы решения транспортной задачи, использование метода потенциалов. Алгоритм решения методом аппроксимации Фогеля. Процедура построения цикла. Планирование перевозок из конечного числа пунктов отправления в конечное число пунктов назначения.

    контрольная работа [32,6 K], добавлен 26.04.2011

  • Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.

    курсовая работа [2,0 M], добавлен 12.02.2013

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

    курсовая работа [33,7 K], добавлен 20.11.2008

  • Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.

    курсовая работа [232,4 K], добавлен 01.06.2009

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

    курсовая работа [167,2 K], добавлен 16.01.2011

  • Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.

    курсовая работа [280,8 K], добавлен 17.11.2011

  • Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.

    курсовая работа [514,8 K], добавлен 04.02.2011

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.