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

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

КУРСОВОЙ ПРОЕКТ

По курсу: Исследование операций в экономике

Содержание

Введение

1. Графическое решение задач линейного программирования

2. Решение задач линейного программирования симплекс-методом

3. Транспортная задача

4. Задача о назначениях

5. Задача о ранце

Заключение

Введение

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

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

В настоящее время существует две группы методов принятия управленческих решений:

1) логический (когда решение принимается на основании опыта, интуиции и других личностных качеств лица, принимающего решение);

2) формально-логический или формализованный (когда решение принимается на основе изучения предварительно-построенной модели). При этом появляется возможность оценить последствия каждого из вариантов и выбрать наилучший по некоторому критерию. В этой группе методов важную роль играют экономико-математические модели.

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

Использование цифровых и знаковых символов позволяет создать категорию моделей, которая включает формально-логические и математические модели.

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

Наиболее распространённая форма, основной инструмент воплощения экономико-математических методов - это экономико-математическое моделирование. Математическое моделирование опирается на математическое описание моделируемого объекта (процесса) в виде формул, зависимостей с помощью математических символов, знаков.

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

Благодаря моделированию субъект управления способен в ходе анализа иметь дело не с реальным объектом управления, а с его аналогом в виде модели. Это значительно расширяет возможности поиска лучших способов управления, не нарушая функционирования реального объекта управления в период выработки управленческих решений. Появляется возможность применить вычислительную технику, использовать компьютеры, для которых математический язык моделей является самым удобным. Благодаря компьютерам можно производить многовариантные модельные расчёты, что повышает шансы на отыскание лучших вариантов.

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

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

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

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

Математические машины, внедряемые в производство и управление и используемые в научно-исследовательской работе, создают огромные возможности для развития различных отраслей науки, для совершенствования методов планирования и автоматизации производства. Однако без строгих формулировок задач, без формально-математического описания процессов не может быть достигнут необходимый уровень использования техники. Возникают вопросы, связанные с формализацией физических, экономических, технических и других процессов. Формализация задачи - необходимый этап для перевода каждой прикладной экономической задачи на язык математических машин.

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

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

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

1. Графическое решение задач линейного программирования

Решить графически задачу

F = 4x₁+x₂ > max,

при следующих ограничениях:

20x₁+7x₂?140

15x₁+10x₂?150

5x₁+20x₂?100

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

Рис. 1

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

Рис. 2

Рассмотрим целевую функцию задачи F = 4x₁+x₂ > max. Построим прямую, отвечающую значению функции F = 0: F = 4x₁+x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых: 20x₁+7x₂=140 5x₁+20x₂=100

Решив систему уравнений, получим: x₁ = 5.7534, x₂ = 3.5616 Откуда найдем максимальное значение целевой функции: F(X) = 4*5.7534 + 1*3.5616 = 26.5753



Рис.3

Рис. 4 Область допустимых решений представляет собой многоугольник

2. Решение задач линейного программирования симплекс-методом

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

Определим максимальное значение целевой функции F(X) = 5x₁ + 5x₂ + 11x₃+9 при следующих условиях - ограничений.

При вычислениях значение Fc = 9 временно не учитываем. x₁ + x₂ + x₃ + x₄?0 7x₁ + 5x₂ + 3x₃ + 2x₄?0 3x₁ + 5x₂ + 10x₃ + 15x₄?0

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (?) вводим базисную переменную x₅. В 2-м неравенстве смысла (?) вводим базисную переменную x₆. В 3-м неравенстве смысла (?) вводим базисную переменную x₇.

1x₁ + 1x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ = 0 7x₁ + 5x₂ + 3x₃ + 2x₄ + 0x₅ + 1x₆ + 0x₇ = 0 3x₁ + 5x₂ + 10x₃ + 15x₄ + 0x₅ + 0x₆ + 1x₇ = 0 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Таблица 1

1	1	1	1	1	0	0
7	5	3	2	0	1	0
3	5	10	15	0	0	1

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

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

Решим систему уравнений относительно базисных переменных: x₅, x₆, x₇

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,0,0,0)

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

Таблица 2

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	0	1	1	1	1	1	0	0
x6	0	7	5	3	2	0	1	0
x7	0	3	5	10	15	0	0	1
F(X0)	0	-5	-5	-11	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: min (0 : 1 , 0 : 3 , 0 : 10 ) = 0

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 3

Базис	B	x1	x2	x3	x4	x5	x6	x7	min
x5	0	1	1	1	1	1	0	0	0
x6	0	7	5	3	2	0	1	0	0
x7	0	3	5	10	15	0	0	1	0
F(X1)	0	-5	-5	-11	0	0	0	0	0

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 1 войдет переменная x₃. Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=1 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x₃ плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:

Таблица 4

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7
0 : 1	1 : 1	1 : 1	1 : 1	1 : 1	1 : 1	0 : 1	0 : 1
0-(0 * 3):1	7-(1 * 3):1	5-(1 * 3):1	3-(1 * 3):1	2-(1 * 3):1	0-(1 * 3):1	1-(0 * 3):1	0-(0 * 3):1
0-(0 * 10):1	3-(1 * 10):1	5-(1 * 10):1	10-(1 * 10):1	15-(1 * 10):1	0-(1 * 10):1	0-(0 * 10):1	1-(0 * 10):1
0-(0 * -11):1	-5-(1 * -11):1	-5-(1 * -11):1	-11-(1 * -11):1	0-(1 * -11):1	0-(1 * -11):1	0-(0 * -11):1	0-(0 * -11):1

Получаем новую симплекс-таблицу:

Таблица 5

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	0	1	1	1	1	1	0	0
x6	0	4	2	0	-1	-3	1	0
x7	0	-7	-5	0	5	-10	0	1
F(X1)	0	6	6	0	11	11	0	0

 1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:

Таблица 6

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	0	1	1	1	1	1	0	0
x6	0	4	2	0	-1	-3	1	0
x7	0	-7	-5	0	5	-10	0	1
F(X2)	0	6	6	0	11	11	0	0

Оптимальный план можно записать так: x₃ = 0 F(X) = 11*0 + 9 = 9

3. Транспортная задача

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента. Прежде всего отыскивается какое-то решение задачи -- исходный опорный план. Затем посредством специальных показателей опорный план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному.

Таблица 7

	1	2	3	4	5	Запасы
1	12	10	6	12	18	410
2	15	6	13	15	23	310
3	21	18	14	19	22	230
Потребности	210	180	240	225	175

Проверим необходимое и достаточное условие разрешимости задачи. ? a = 410 + 310 + 230 = 950 ? b = 210 + 180 + 240 + 225 + 175 = 1030 Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равным 80 (1030--950). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Занесем исходные данные в распределительную таблицу.

Таблица 8

	1	2	3	4	5	Запасы
1	12	10	6	12	18	410
2	15	6	13	15	23	310
3	21	18	14	19	22	230
4	0	0	0	0	0	80
Потребности	210	180	240	225	175

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность. Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и по способу Лебедева-Тихомирова. Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Искомый элемент равен 6 Для этого элемента запасы равны 410, потребности 240. Поскольку минимальным является 240, то вычитаем его. x₁₃ = min(410,240) = 240.

Таблица 9

12	10	6	12	18	410 - 240 = 170
15	6	x	15	23	310
21	18	x	19	22	230
0	0	x	0	0	80
210	180	240 - 240 = 0	225	175	0

Искомый элемент равен 6 Для этого элемента запасы равны 310, потребности 180. Поскольку минимальным является 180, то вычитаем его. x₂₂ = min(310,180) = 180.

Таблица 10

12	x	6	12	18	170
15	6	x	15	23	310 - 180 = 130
21	x	x	19	22	230
0	x	x	0	0	80
210	180 - 180 = 0	0	225	175	0

Искомый элемент равен 12 Для этого элемента запасы равны 170, потребности 210. Поскольку минимальным является 170, то вычитаем его. x₁₁ = min(170,210) = 170.

Таблица 11

12	x	6	x	x	170 - 170 = 0
15	6	x	15	23	130
21	x	x	19	22	230
0	x	x	0	0	80
210 - 170 = 40	0	0	225	175	0

Искомый элемент равен 15. Для этого элемента запасы равны 130, потребности 40. Поскольку минимальным является 40, то вычитаем его. x₂₁ = min(130,40) = 40.

Таблица 12

12	x	6	x	x	0
15	6	x	15	23	130 - 40 = 90
x	x	x	19	22	230
x	x	x	0	0	80
40 - 40 = 0	0	0	225	175	0

Искомый элемент равен 15. Для этого элемента запасы равны 90, потребности 225. Поскольку минимальным является 90, то вычитаем его. x₂₄ = min(90,225) = 90.

Таблица 13

12	x	6	x	x	0
15	6	x	15	x	90 - 90 = 0
x	x	x	19	22	230
x	x	x	0	0	80
0	0	0	225 - 90 = 135	175	0

Искомый элемент равен 19. Для этого элемента запасы равны 230, потребности 135. Поскольку минимальным является 135, то вычитаем его. x₃₄ = min(230,135) = 135.

Таблица 14

12	x	6	x	x	0
15	6	x	15	x	0
x	x	x	19	22	230 - 135 = 95
x	x	x	x	0	80
0	0	0	135 - 135 = 0	175	0

Искомый элемент равен 22. Для этого элемента запасы равны 95, потребности 175. Поскольку минимальным является 95, то вычитаем его. x₃₅ = min(95,175) = 95.

Таблица 15

12	x	6	x	x	0
15	6	x	15	x	0
x	x	x	19	22	95 - 95 = 0
x	x	x	x	0	80
0	0	0	0	175 - 95 = 80	0

Искомый элемент равен 0. Для этого элемента запасы равны 80, потребности 80. Поскольку минимальным является 80, то вычитаем его. x₄₅ = min(80,80) = 80.

Таблица 16

12	x	6	x	x	0
15	6	x	15	x	0
x	x	x	19	22	0
x	x	x	x	0	80 - 80 = 0
0	0	0	0	80 - 80 = 0	0

Таблица 17

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40]	6[180]	13	15[90]	23	310
3	21	18	14	19[135]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 12*170 + 6*240 + 15*40 + 6*180 + 15*90 + 19*135 + 22*95 + 0*80 = 11165 Значение целевой функции для этого опорного плана равно: 12*170 + 6*240 + 15*40 + 6*180 + 15*90 + 19*135 + 22*95 + 0*80 = 11165

Этап II. Улучшение опорного плана. Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение поставок. План распределения поставок будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на поставку будет невозможно. Проверим возможность уменьшения суммарных затрат на поставку продукции.

С этой целью для каждой свободной от поставки клетки определяется величина ?_ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки х_ij=1 от поставщика А_i к потребителю В_j. При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи. Величина ?_ij называется оценкой свободной клетки (или характеристика). В исходном решении задачи имеются клетки свободные от поставок. Необходимо вычислить значение оценок ?_ij для этих свободных от поставок клеток. С этой целью для каждой свободной клетки составляется означенный цикл перерасчета (или замкнутая цепь, круг, кольцо, контур и т.д.). Под циклом пересчета (цепью) понимается замкнутая ломаная линия. Вершинами цикла (цепи) являются клетки таблицы, проще - вершины лежат в клетках таблицы. Причем одна из вершин находится в свободной от поставки клетке, в той, для которой определяется оценка ?_ij.

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

Следующий этап решения транспортной задачи заключается в улучшении опорного плана. Если при каком-то опорном плане оказывается несколько свободных клеток с отрицательными оценками ?_ij, то за один переход к лучшему плану можно занять поставкой только одну клетку - ту, которая обеспечивает наибольшее снижение целевой функции. Шаг 1. Определяем оценку для каждой свободной клетки. (1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 18

	1	2	3	4	5	Запасы
1	12[170][-]	10[+]	6[240]	12	18	410
2	15[40][+]	6[180][-]	13	15[90]	23	310
3	21	18	14	19[135]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (1,2 > 1,1 > 2,1 > 2,2). Оценка свободной клетки равна ?₁₂ = (10) - (12) + (15) - (6) = 7. (1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 19

	1	2	3	4	5	Запасы
1	12[170][-]	10	6[240]	12[+]	18	410
2	15[40][+]	6[180]	13	15[90][-]	23	310
3	21	18	14	19[135]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (1,4 > 1,1 > 2,1 > 2,4). Оценка свободной клетки равна ?₁₄ = (12) - (12) + (15) - (15) = 0. (1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 20

	1	2	3	4	5	Запасы
1	12[170][-]	10	6[240]	12	18[+]	410
2	15[40][+]	6[180]	13	15[90][-]	23	310
3	21	18	14	19[135][+]	22[95][-]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (1,5 > 1,1 > 2,1 > 2,4 > 3,4 > 3,5). Оценка свободной клетки равна ?₁₅ = (18) - (12) + (15) - (15) + (19) - (22) = 3. (2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 21

	1	2	3	4	5	Запасы
1	12[170][+]	10	6[240][-]	12	18	410
2	15[40][-]	6[180]	13[+]	15[90]	23	310
3	21	18	14	19[135]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (2,3 > 2,1 > 1,1 > 1,3). Оценка свободной клетки равна ?₂₃ = (13) - (15) + (12) - (6) = 4. (2;5): В свободную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 22

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40]	6[180]	13	15[90][-]	23[+]	310
3	21	18	14	19[135][+]	22[95][-]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (2,5 > 2,4 > 3,4 > 3,5). Оценка свободной клетки равна ?₂₅ = (23) - (15) + (19) - (22) = 5. (3;1): В свободную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 23

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40][-]	6[180]	13	15[90][+]	23	310
3	21[+]	18	14	19[135][-]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (3,1 > 3,4 > 2,4 > 2,1). Оценка свободной клетки равна ?₃₁ = (21) - (19) + (15) - (15) = 2. (3;2): В свободную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 24

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40]	6[180][-]	13	15[90][+]	23	310
3	21	18[+]	14	19[135][-]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (3,2 > 3,4 > 2,4 > 2,2). Оценка свободной клетки равна ?₃₂ = (18) - (19) + (15) - (6) = 8. (3;3): В свободную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (3,3 > 3,4 > 2,4 > 2,1 > 1,1 > 1,3). Оценка свободной клетки равна ?₃₃ = (14) - (19) + (15) - (15) + (12) - (6) = 1. (4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 25

	1	2	3	4	5	Запасы
1	12[170][+]	10	6[240][-]	12	18	410
2	15[40][-]	6[180]	13	15[90][+]	23	310
3	21	18	14[+]	19[135][-]	22[95]	230
4	0	0	0	0	0[80]	80
Потребности	210	180	240	225	175

Таблица 26

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40][-]	6[180]	13	15[90][+]	23	310
3	21	18	14	19[135][-]	22[95][+]	230
4	0[+]	0	0	0	0[80][-]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (4,1 > 4,5 > 3,5 > 3,4 > 2,4 > 2,1). Оценка свободной клетки равна ?₄₁ = (0) - (0) + (22) - (19) + (15) - (15) = 3. (4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 27

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40]	6[180][-]	13	15[90][+]	23	310
3	21	18	14	19[135][-]	22[95][+]	230
4	0	0[+]	0	0	0[80][-]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (4,2 > 4,5 > 3,5 > 3,4 > 2,4 > 2,2). Оценка свободной клетки равна ?₄₂ = (0) - (0) + (22) - (19) + (15) - (6) = 12. (4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 28

	1	2	3	4	5	Запасы
1	12[170][+]	10	6[240][-]	12	18	410
2	15[40][-]	6[180]	13	15[90][+]	23	310
3	21	18	14	19[135][-]	22[95][+]	230
4	0	0	0[+]	0	0[80][-]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (4,3 > 4,5 > 3,5 > 3,4 > 2,4 > 2,1 > 1,1 > 1,3). Оценка свободной клетки равна ?₄₃ = (0) - (0) + (22) - (19) + (15) - (15) + (12) - (6) = 9. (4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 29

	1	2	3	4	5	Запасы
1	12[170]	10	6[240]	12	18	410
2	15[40]	6[180]	13	15[90]	23	310
3	21	18	14	19[135][-]	22[95][+]	230
4	0	0	0	0[+]	0[80][-]	80
Потребности	210	180	240	225	175

Цикл приведен в таблице (4,4 > 4,5 > 3,5 > 3,4). Оценка свободной клетки равна ?₄₄ = (0) - (0) + (22) - (19) = 3. Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения. Таким образом, последний опорный план является оптимальным. Минимальные затраты составят: 12*170 + 6*240 + 15*40 + 6*180 + 15*90 + 19*135 + 22*95 + 0*80 = 11165 Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым -- минимальным. Их принято называть альтернативными.

Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп--(m+n--1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 -- 361 цикл. Анализ оптимального плана. Из 1-го склада необходимо груз направить в 1-й магазин (170), в 3-й магазин (240) Из 2-го склада необходимо груз направить в 1-й магазин (40), в 2-й магазин (180), в 4-й магазин (90) Из 3-го склада необходимо груз направить в 4-й магазин (135), в 5-й магазин (95) Потребность 5-го магазина остается неудовлетворенной на 80 ед. Оптимальный план является вырожденным, так как базисная переменная x₄₅=0.

4. Задача о назначениях

Таблица 30 Исходные данные:

Бригада	Виды работ
	1	2	3	4	5
1	2	5	16	2	2
2	0	7	8	5	10
3	4	17	6	3	3
4	6	11	11	7	8
5	6	12	2	13	12

Исходная матрица имеет вид:

Таблица 31

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

• Исследование операций

  Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
  
  курсовая работа [54,1 K], добавлен 05.03.2010
  

• Исследование операций в экономике

  Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
  
  курсовая работа [105,5 K], добавлен 02.10.2014
  

• Решение задач линейного программирования

  Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
  
  контрольная работа [40,0 K], добавлен 04.05.2014
  

• Запись математической модели в форме стандартной задачи линейного программирования

  Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
  
  дипломная работа [311,3 K], добавлен 17.01.2014
  

• Линейное программирование

  Задача линейного программирования: определение количества продуктов для получения максимального дохода от реализации, расчет цены для минимальной общей стоимости затрат на производство с помощью графического и симплекс-метода. Решение транспортных задач.
  
  курсовая работа [519,5 K], добавлен 06.05.2011
  

• Применение графического метода и симплекс-метода для решения задач линейного программирования

  Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
  
  контрольная работа [398,2 K], добавлен 15.08.2012
  

• Решение экономических задач математическими методами с использованием Mathcad и MS Excel

  Построение математической модели и решение задачи математического программирования в средах MathCad и MS Excel. Решение систем с произвольными векторами свободных коэффициентов. Определение вектора невязки. Минимизация и максимизация целевой функции.
  
  отчет по практике [323,5 K], добавлен 01.10.2013
  

• Оптимизация плана производства

  Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
  
  курсовая работа [458,6 K], добавлен 10.12.2013
  

• Построение оптимального плана перевозок груза с минимальной стоимостью

  Определение первичного опорного плана разными способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Перепланировка поставок с помощью метода потенциалов для каждого плана. Анализ эффективности их использования.
  
  контрольная работа [67,2 K], добавлен 06.11.2012
  

• Методы и математические модели в экономике

  Определение максимума целевой функции при различных системах ограничений. Применение экономико-математических методов при нахождении оптимальных планов транспортных задач. Решение линейных неравенств, максимальное и минимальное значения целевой функции.
  
  методичка [45,2 K], добавлен 06.06.2012
  

• Решение задач о планировании перевозок

  Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.
  
  курсовая работа [111,1 K], добавлен 16.01.2011
  

• Примеры использования графического и симплексного методов в решении задач линейного программирования

  Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
  
  контрольная работа [367,5 K], добавлен 11.05.2014
  

• Оптимальные экономико-математические модели

  Нахождение начального опорного плана методом минимальной стоимости, оптимизация его методом потенциалов. Решение задачи о назначениях с заданной матрицей затрат. Построение набора дуг, соединяющих все вершины сети и имеющих минимальную протяженность.
  
  контрольная работа [341,0 K], добавлен 24.04.2012
  

• Методы принятия управленческих решений

  Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
  
  контрольная работа [613,3 K], добавлен 18.02.2014
  

• Экономико-математические методы

  Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
  
  контрольная работа [177,8 K], добавлен 02.02.2010
  

• Анализ экономических задач оптимизации

  Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).
  
  контрольная работа [812,0 K], добавлен 29.09.2010
  

• Исследование операций в экономике

  Нахождение области допустимых значений и оптимумов целевой функции с целью решения графическим методом задачи линейного программирования. Нахождение оптимальных значений двойственных переменных при помощи симплексного метода и теории двойственности.
  
  контрольная работа [116,0 K], добавлен 09.04.2012
  

• Применение методов линейного программирования для оптимизации стоимости перевозок

  Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.
  
  контрольная работа [81,9 K], добавлен 14.09.2010
  

• Экономико-математические методы и прикладные модели

  Решение задач линейного программирования с применением алгоритма графического определения показателей и значений, с использованием симплекс-метода. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана ЗЛП.
  
  контрольная работа [94,6 K], добавлен 23.04.2013
  

• Определение оптимальных значений вероятности событий

  Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.
  
  контрольная работа [152,3 K], добавлен 16.05.2013
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам