Решение оптимизационных экономических задач методами линейного программирования

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

Смоленский гуманитарный университет

Факультет компьютерных технологий, экономики и дизайна

Кафедра математического моделирования

Курсовая работа

Решение оптимизационных экономических задач методами линейного программирования

Научный руководитель:

д.т.н., профессор Бешенков С.Н.

Зав.кафедрой:

д.т.н., профессор Бешенков С.Н.

Смоленск 2010

Содержание

Введение

1. Общая постановка задачи линейного программирования

2. Примеры экономических задач, приводящихся к задачам ЛП

3. Графический метод решения задачи ЛП

4. Симплекс-метод решения задач ЛП

5. Теорема двойственности

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

7. Решение задач ЛП с использованием программы «Microsoft Excel»

Заключение

Литература

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

Введение

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.

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

Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д

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

1. Общая постановка задачи линейного программирования

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

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

задача об оптимальном использовании ресурсов при производственном планировании;

задача о смесях (планирование состава продукции);

задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование - наиболее применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

математические модели большого числа экономических задач линейны относительно искомых переменных;

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

многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

В общем виде модель записывается следующим образом:

целевая функция:

= c1x1 + c2x2 + ... + cnxn > max(min); (2.1)

ограничения:

a11x1 + a12x2 + ... + a1nxn {? = ?} b1,

a21x1 + a22x2 + ... + a2nxn {? = ?} b2,

am1x1 + am2x2 + ... + amnxn {? = ?} bm; (2.2)

требование неотрицательности:

xj ? 0, (2.3)

При этом aij, bi, cj ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

2. Примеры экономических задач, приводящихся к задачам ЛП

Задача о наилучшем использовании ресурсов.

Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Ее будем обозначать . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации

, т. е. --вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Так как - цена реализации единицы j'-й продукции, цена реализованных единиц будет равна , а общий объем реализации

Это выражение -- целевая функция, которую нужно максимизировать.

Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц:

Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции:

.

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

(1)

при ограничениях:

(2)

(3)

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

Задача о смесях.

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

Задача о раскрое материалов.

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

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

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

Задача о размещении заказа.

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

3. Графический метод решения задачи ЛП

Пример(1)

При откорме каждое животное должно получить не менее А=28 ед.питательного вещества S1, не менее В=5 ед. вещества S2 и не менее С=9 вещества S3 . Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 килограмме каждого вида корма и стоимость одного килограмма корма дана в таблицах 1 и 2.

Таблица 1

Питательные вещества	Количество единиц питательных веществ в 1 кг. корма
	корм 1	корм 2
S1	a1=1	a2=2
S2	b1=3	b2=1
S3	c1=3	c2=4
Стоимость 1 кг. корма	p1=5	p2=8

X1 - корма 1, X2 - корма 2

Составить рацион минимальной стоимости.

Решение

Необходимо найти минимальное значение целевой функции

F = 5X1+8X2 => min, при системе ограничений:

x1+2x2?5 (1)

3x1+x2?5 (2)

3x1+4x2?14 (3)

Начало формы

.

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

Границы области

Обозначим границы области многоугольника решений.



Целевая функция F(x) => min

Рассмотрим целевую функцию задачи F = 5X1+8X2 => min.

Построим прямую, отвечающую значению функции F = 0: F = 5X1+8X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.



Равный масштаб

Конец формы

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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых 1 и 3, то ее координаты удовлетворяют уравнениям этих прямых:

x1+2x2?5

3x1+4x2?14

Решив систему уравнений, получим: x1 = 4, x2 = 0.5

Откуда найдем минимальное значение целевой функции:

F(X) = 5*4 + 8*0.5 = 24

4. Симплекс-метод решения задач ЛП

Пример(2)

Для изготовления 4-ёх видов продукции P1, P2, P3, P4 используют два вида сырья: S1 и S2 . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.

Таблица 2

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	А=5	a1=3	a2=1	a3=3	a4=3
S2	В=8	b1=2	b2=2	b3=1	b4=4
Прибыль от единицы продукции	C1=9	C2=5	C3=5	C4=14

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

Определим максимальное значение целевой функции

F(X)= 9x1+5x2+5x3+14x4 при следующих условиях-ограничений.

3x1+x2+3x3+3x4?5

2x1+2x2+x3+4x4?8

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

3x1 + 1x2 + 3x3 + 3x4 + 1x5 + 0x6 = 5

2x1 + 2x2 + 1x3 + 4x4 + 0x5 + 1x6 = 8

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

x5, x6,

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

X1 = (0,0,0,0,5,8)

План	Базис	В	x1	x2	x3	x4	x5	x6
0	x5	5	3	1	3	3	1	0
	x6	8	2	2	1	4	0	1
Индексная строка	F(X0)	0	-9	-5	-5	-14	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
1	x5	5	3	1	3	3	1	0	1.67
	x6	8	2	2	1	4	0	1	2
Индексная строка	F(X1)	0	-9	-5	-5	-14	0	0	0

Итерация №0.

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

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

Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей

План	Базис	В	x1	x2	x3	x4	x5	x6	min
2	x4	1.67	1	0.3333	1	1	0.3333	0	5
	x6	1.33	-2	0.6667	-3	0	-1.33	1	2
Индексная строка	F(X2)	23.33	5	-0.3333	9	0	4.67	0	0

Итерация №1.

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

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

Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей

Конец итераций: найден оптимальный план

Окончательный вариант симплекс-таблицы:

План	Базис	В	x1	x2	x3	x4	x5	x6
3	x4	1	2	0	2.5	1	1	-0.5
	x2	2	-3	1	-4.5	0	-2	1.5
Индексная строка	F(X3)	24	4	0	7.5	0	4	0.5

Оптимальный план можно записать так:

x4 = 1

x2 = 2

F(X) = 5*2 + 14*1 = 24

5. Теорема двойственности

Пример(3)

а) Составить задачу двойственную к примеру 2.

б) найти её решение любым методом.

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

Составим двойственную задачу к прямой задаче.

5y1+8y2 => min

3y1+2y2?9

y1+2y2?5

3y1+y2?5

3y1+4y2?14

y1 ? 0

y2 ? 0

Необходимо найти минимальное значение целевой функции

Z=5Y1+8Y2=> min

при системе ограничений:

3y1+2y2?9 (1)

y1+2y2?5 (2)

3y1+y2?5 (3)

3y1+4y2?14 (4)

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

Рис. 5.1

Границы области

Обозначим границы области многоугольника решений.

Рис. 5.2

Рассмотрим целевую функцию задачи F = 5x1+8x2 > min.

Построим прямую, отвечающую значению функции F = 0: F = 5x1+8x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области.

На графике эта прямая обозначена пунктирной линией.



Рис. 5.3

Равный масштаб



Рис. 5.4

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

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (4), то ее координаты удовлетворяют уравнениям этих прямых:

x1+2x2?5

3x1+4x2?14

Решив систему уравнений, получим: x1 = 4, x2 = 0.5

Откуда найдем минимальное значение целевой функции:

F(X) = 5*4 + 8*0.5 = 24

Найдем Х1, Х2, Х3, Х4 исходной задачи.

y1 > 0 > 3x1+x2+3x3+3x4=5

y2 > 0 > 2x1+2x2+x3+4x4=8

Представим y1 = 4, y2 = 0.5 в систему ограничений:

3y1+2y2=3*4+2*0.5=13 > 9> х1=0

y1+2y2=1*4+2*0.5=5 > х2?0

3y1+y2=3*4+1*0.5=12.5>5 > х3=0

3y1+4y2=3*4+4*0.5=14 > х4?0

Решим систему уравнений (ограничения из исходной задачи):

Х2+3x4=5

2х2+4х4=8

От сюда: Х2=2; Х4=1; F(X) = 5*2 + 14*1 = 24

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

Пример(4)

Исходные данные приведены в таблице 3, найти оптимальный план.

Таблица 3

Мощность поставщиков	Мощность потребителей
	4N + 8 56	4N + 8 56	3N + 6 42	4N + 8 56
8N + 16 112	5	4	3	4
7N + 14 98	3	2	5	5
3N + 6 42	1	6	3	2

Решение

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

	1	2	3	4	Запасы
1	5	4	3	4	112
2	3	2	5	5	98
3	1	6	3	2	42
Потребности	56	56	42	56

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

? a = 112 + 98 + 42 = 252

? b = 56 + 56 + 42 + 56 = 210

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

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

	1	2	3	4	5	Запасы
1	5	4	3	4	0	112
2	3	2	5	5		98
3	1	6	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5	4	3 [42]	4 [56]	0 [14]	112
2	3 [14]	2 [56]	5	5	0 [28]	98
3	1 [42]	6	3	2	0	42
Потребности	56	56	42	56	42

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

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

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

	v1=3	v2=2	v3=3	v4=4	v5=0
u1=0	5	4	3[42]	4[56]	0[14]
u2=0	3[14]	2[56]	5	5	0[28]
u3=-2	1[42]	6	3	2	0

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

(1;1): 0 + 3 < 5

(1;2): 0 + 2 < 4

(2;3): 0 + 3 < 5

(2;4): 0 + 4 < 5

(3;2): -2 + 2 < 6

(3;3): -2 + 3 < 3

(3;5): -2 + 0 < 0

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

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

	1	2	3	4	5	Запасы
1	5	4	3[42]	4[56]	0[14]	112
2	3[14][+]	2[56][-]	5	5	0[28]	98
3	1[42][-]	6[+]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5	4	3[42]	4[56]	0[14]	112
2	3[56]	2[14]	5	5	0[28]	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	v1=3	v2=2	v3=3	v4=4	v5=0
u1=0	5	4	3[42]	4[56]	0[14]
u2=0	3[56]	2[14]	5	5	0[28]
u3=4	1	6[42]	3	2	0

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

(1;1): 0 + 3 < 5

(1;2): 0 + 2 < 4

(2;3): 0 + 3 < 5

(2;4): 0 + 4 < 5

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

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

	1	2	3	4	5	Запасы
1	5[+]	4	3[42]	4[56]	0[14][-]	112
2	3[56][-]	2[14]	5	5	0[28][+]	98
	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5[14]	4	3[42]	4[56]	0	112
2	3[42]	2[14]	5	5	0[42]	98
3	1	6[42]	3	2	0	42
Потреб.	56	56	42	56	42

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

	v1=5	v2=4	v3=3	v4=4	v5=2
u1=0	5[14]	4	3[42]	4[56]	0
u2=-2	3[42]	2[14]	5	5	0[42]
u3=2	1	6[42]	3	2	0

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

(2;3): -2 + 3 < 5

(2;4): -2 + 4 < 5

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

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

	1	2	3	4	5	Запасы
1	5[14][+]	4	3[42][-]	4[56]	0	112
2	3[42][-]	2[14]	5[+]	5	0[42]	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5[56]	4	3[0]	4[56]	0	112
2	3	2[14]	5[42]	5	0[42]	98
3	1	6[42]	3	2	0	42
Потреб.	56	56	42	56	42

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

	v1=5	v2=0	v3=3	v4=4	v5=-2
u1=0	5[56]	4	3[0]	4[56]	0
u2=2	3	2[14]	5[42]	5	0[42]
u3=6	1	6[42]	3	2	0

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

(1;2): 0 + 0 < 4

(1;5): 0 + -2 < 0

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

	1	2	3	4	5	Запасы
1	5[56]	4[+]	3[0][-]	4[56]	0	112
2	3	2[14][-]	5[42][+]	5	0[42]	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5[56]	4[0]	3	4[56]	0	112
2	3	2[14]	5[42]	5	0[42]	98
3	1	6[42]	3	2	0	42
Потреб.	56	56	42	56	42

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

	v1=5	v2=4	v3=7	v4=4	v5=2
u1=0	5[56]	4[0]	3	4[56]	0
u2=-2	3	2[14]	5[42]	5	0[42]
u3=2	1	6[42]	3	2	0

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

(2;4): -2 + 4 < 5

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

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

	1	2	3	4	5	Запасы
1	5[56]	4[0][+]	3	4[56][-]	0	112
2	3	2[14][-]	5[42]	5[+]	0[42]	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5[56]	4[14]	3	4[42]	0	112
2	3	2	5[42]	5[14]	0[42]	98
3	1	6[42]	3	2	0	42
Потреб.	56	56	42	56	42

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

	v1=5	v2=4	v3=4	v4=4	v5=-1
u1=0	5[56]	4[14]	3	4[42]	0
u2=1	3	2	5[42]	5[14]	0[42]
u3=2	1	6[42]	3	2	0

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

(1;5): 0 + -1 < 0

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

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

	1	2	3	4	5	Запасы
1	5[56]	4[14]	3	4[42][-]	0[+]	112
2	3	2	5[42]	5[14][+]	0[42][-]	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5[56]	4[14]	3	4[0]	0[42]	112
2	3	2	5[42]	5[56]	0	98
3	1	6[42]	3	2	0	42
Потребности	56	56	42	56	42

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

	v1=5	v2=4	v3=4	v4=4	v5=0
u1=0	5[56]	4[14]	3	4[0]	0[42]
u2=1	3	2	5[42]	5[56]	0
u3=2	1	6[42]	3	2	0

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

Максимальная прибыль составит:

F(x) = 5*56 + 4*14 + 0*42 + 5*42 + 5*56 + 6*42 = 1078

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

	1	2	3	4	Запасы
1	5	4	3	4	112
2	3	2	5	5	98
3	1	6	3	2	42
Потреб.	56	56	42	56

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

? a = 112 + 98 + 42 = 252

? b = 56 + 56 + 42 + 56 = 210

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

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

	1	2	3	4	5	Запасы
1	5	4	3	4	0	112
2	3	2	5	5	0	98
3	1	6	3	2	0	42
Потребности	56	56	42	56	42

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

	1	2	3	4	5	Запасы
1	5	4	3[42]	4[56]	0[14]	112
2	3[14]	2[56]	5	5	0[28]	98
3	1[42]	6	3	2	0	42
Потребности	56	56	42	56	42

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

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

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

	v1=3	v2=2	v3=3	v4=4	v5=0
u1=0	5	4	3[42]	4[56]	0[14]
u2=0	3[14]	2[56]	5	5	0[28]
u3=-2	1[42]	6	3	2	0

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

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

F(x) = 3*42 + 4*56 + 0*14 + 3*14 + 2*56 + 0*28 + 1*42 = 546

7. Решение задач ЛП с использованием программы «Microsoft Excel»

Решить задачу линейного программирования (Пример1):

F = 5X1+8X2 > min,

x1+2x2?5 (1)

3x1+x2?5 (2)

3x1+4x2?14 (3)

Перейдем к решению задачи в Excel.

В ячейки B4-C4 занесем данные о количестве затрат первого сырья на производство соответствующих продукции. В ячейку E4 занесем запас первого сырья.

В ячейки B5-C5 занесем данные о количестве затрат второго сырья на производство соответствующих продукции. В ячейку E5 занесем запас второго сырья.

В ячейки B9-C9 занесем данные о стоимости получаемой от производства 1 кг. корма.

В ячейки B2-С2 занесем нулевые значения как начальное приближение.

В ячейку F4 занесем сумму произведений ячеек B4-C4 на ячейки B2-C2 (вектор X на первое ограничение).

В ячейку F5 занесем сумму произведений ячеек B5-C5 на ячейки B2-C2 (вектор X на второе ограничение).

В ячейку F6 занесем сумму произведений ячеек B6-C6 на ячейки B2-C6 (вектор X на третье ограничение).

В ячейку D9 занесем сумму произведений ячеек B8-C8 на ячейки B2-C2 (целевая функция).



Установим курсор в ячейку D9 и откроем надстройку «поиск решения». В поле «изменяя ячейки» занесем диапазон $B$2:$C$2. Добавим ограничения $B$2:$C$2>=0; $F$4>= $E$4; $F$5>= $E$5; $F$6>= $E$6;. Установим переключатель в положение «минимальному значению» (т.к. задача на минимум).

Нажмем кнопку «выполнить». В ячейке D9 получим минимальное значение целевой функции. В ячейках B2-С2 - вектор X целевой функции.



Ответ задачи: Функция F =5X1+8X2 достигает минимального значения равного 24 при х1=4 и х2=0.5.

Решить задачу линейного программирования (Пример2):

F(X)= 9x1+5x2+5x3+14x4 при следующих условиях-ограничений.

3x1+x2+3x3+3x4?5

2x1+2x2+x3+4x4?8

X1,X2,X3,X4 ?0

Перейдем к решению задачи в Excel.

В ячейки B4-E4 занесем данные о количестве затрат первого сырья на производство соответствующих продукции. В ячейку G4 занесем запас первого сырья.

В ячейки B5-E5 занесем данные о количестве затрат второго сырья на производство соответствующих продукции. В ячейку G5 занесем запас второго сырья.

В ячейки B8-E8 занесем данные о прибыли получаемой от производства единицы соответствующего вида продукции.

В ячейки B2-E2 занесем нулевые значения как начальное приближение. В ячейку H4 занесем сумму произведений ячеек B4-E4 на ячейки B2-E2 (вектор X на первое ограничение).



В ячейку H5 занесем сумму произведений ячеек B5-E5 на ячейки B2-E2 (вектор X на второе ограничение).

В ячейку F8 занесем сумму произведений ячеек B8-E8 на ячейки B2-E2 (целевая функция).



Установим курсор в ячейку F8 и откроем надстройку «поиск решения». В поле «изменяя ячейки» занесем диапазон $B$2:$E$2. Добавим ограничения $B$2:$E$2>=0; $H$5<= $G$5. Установим переключатель в положение «максимальному значению» (т.к. задача на максимум).

Нажмем кнопку «выполнить». В ячейке F8 получим максимальное значение целевой функции. В ячейках B2-E2 - вектор X целевой функции.



Ответ задачи: Функция F(X)= 9x1+5x2+5x3+14x4 достигает минимального значения равного 24 при х2=2 и х4=1.

Решить задачу линейного программирования (Пример3):

3y1+2y2?9

y1+2y2?5

3y1+y2?5

3y1+4y2?14

5y1+8y2 => min

y1 ? 0

y2 ? 0

Перейдем к решению задачи в Excel.

В ячейки B4-C4 занесем данные о количестве затрат первого сырья на производство соответствующих продукции. В ячейку E4 занесем запас первого сырья.

В ячейки B5-C5 занесем данные о количестве затрат второго сырья на производство соответствующих продукции. В ячейку E5 занесем запас второго сырья.

В яч...