Решение линейных оптимизационных задач

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

Практическая работа № 1

ПОСТРОЕНИЕ ЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки теоретического построения линейных оптимизационных моделей в задачах планирования деятельности туристской фирмы.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ

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

Организация предоставляет два вида услуг:

-визовую поддержку,

-продажу авиабилетов в страны Европы.

Организационно-экономические возможности фирмы следующие:

-выход в Интернет - не более 500 Мб в неделю,

-поездки в посольства и представительства стран Европы в других городах - не более 6 раз в неделю.

Дополнительные сведения о нормах объемов информации по сети Интернет (по ADSL-технологии) и поездок в посольства или представительства в других городах приведены в таблицах 1, 2.

Выручка фирмы от предоставления двух видов услуг должна составлять не менее 20000 руб. в день, в т.ч. от продажи авиабилетов - не менее 10000 руб.

Определим потребляемые организацией ресурсы z:

zr1 - суммарный расход от выхода в интернет;

zr2 - суммарный расход от поездок;

zr1 = 40x1 + 50x2 ? 500;

zr2 = 2x1 ? 6

определим выходные экономические показатели:

zl1 - суммарный результат по общей выручке.

zl2 - суммарный результат по выручке от продажи билетов

zl1 = 4400x1 + 7000 x2 ? 20000,

zl2 = 7000 x2 ? 10000

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

z0 = 440 x1 + 700x2 > max

Цель моделирования: z0 > max.

Ограничения на ресурсы и экономические показатели: x1 ? 0, x2 ? 0.

Таким образом, получаем:

z0 = 440 x1 + 700x2 > max;

zr1 = 40x1 + 50x2 ? 500;

zr2 = 2x1 ? 6;

zl1 = 4400x1 + 7000 x2 ? 20000,

zl2 = 7000 x2 ? 10000

x1 ? 0, x2 ? 0

Приведем модель к стандартной форме, получим:

z0 = 440 x1 + 700x2 > max;

yr1 = -40x1 - 50x2 + 500 ? 0;

yr2 = -2x1 +6 ? 0;

yl1 = 4400x1 + 7000 x2 - 20000? 0,

yl2 = 7000 x2 -10000 ? 0

x1 ? 0, x2 ? 0

Практическая работа № 2

ГРАФИЧЕСКИЕ МЕТОДЫ ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ ЛИНЕЙНЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки анализа экономико-математических моделей на основе графических методов поиска их оптимальных решений.

Необходимо найти максимальное значение целевой функции F = 440x1+700x2 > max, при системе ограничений:

40x1+50x2?500	(1)
2x1?6	(2)
4400x1+7000x2?20000	(3)
7000x2?10000	(4)
x1?0	(5)
x2?0	(6)

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



Или

Границы области допустимых решений

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

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

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

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



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

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

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

40x1+50x2?500

x1=0

Решив систему уравнений, получим: x1 = 0, x2 = 10
Откуда найдем максимальное значение целевой функции:
F(X) = 440*0 + 700*10 = 7000.

Практическая работа № 3

СИМПЛЕКС-МЕТОД ПОИСКА И АНАЛИЗА ОПТИМАЛЬНОГО РЕШЕНИЯ ЛИНЕЙНЫХ МОДЕЛЕЙ

ЦЕЛЬ РАБОТЫ: развить навыки поиска и анализа оптимальных решений линейных моделей на основе симплексного метода.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ

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

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

Определим максимальное значение целевой функции F(X) = 440x1 + 700x2 при следующих условиях-ограничений.

40x1 + 50x2?500

2x1?6

4400x1 + 7000x2?20000

7000x2?10000

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

В 1-м неравенстве смысла (?) вводим базисную переменную x3. В 2-м неравенстве смысла (?) вводим базисную переменную x4. В 3-м неравенстве смысла (?) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла (?) вводим базисную переменную x6 со знаком минус.

40x1 + 50x2 + 1x3 + 0x4 + 0x5 + 0x6 = 500

2x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 = 6

4400x1 + 7000x2 + 0x3 + 0x4-1x5 + 0x6 = 20000

0x1 + 7000x2 + 0x3 + 0x4 + 0x5-1x6 = 10000

Введем искусственные переменные x: в 3-м равенстве вводим переменную x7; в 4-м равенстве вводим переменную x8;

40x1 + 50x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 + 0x8 = 500

2x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 6

4400x1 + 7000x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 + 0x8 = 20000

0x1 + 7000x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 1x8 = 10000

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = 440x1+700x2 - Mx7 - Mx8 > max

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

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

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

Из уравнений выражаем искусственные переменные:

x7 = 20000-4400x1-7000x2+x5

x8 = 10000-7000x2+x6

которые подставим в целевую функцию:

F(X) = 440x1 + 700x2 - M(20000-4400x1-7000x2+x5) - M(10000-7000x2+x6) > max

или

F(X) = (440+4400M)x1+(700+14000M)x2+(-M)x5+(-M)x6+(-30000M) > max

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

40	50	1	0	0	0	0	0
2	0	0	1	0	0	0	0
4400	7000	0	0	-1	0	1	0
0	7000	0	0	0	-1	0	1

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

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

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

x3, x4, x7, x8,

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

X1 = (0,0,500,6,0,0,20000,10000)

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	500	40	50	1	0	0	0	0	0
x4	6	2	0	0	1	0	0	0	0
x7	20000	4400	7000	0	0	-1	0	1	0
x8	10000	0	7000	0	0	0	-1	0	1
F(X0)	-30000M	-440-4400M	-700-14000M	0	0	M	M	0	0

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

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (500 : 50 , - , 20000 : 7000 , 10000 : 7000 ) = 13/7

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x3	500	40	50	1	0	0	0	0	0	10
x4	6	2	0	0	1	0	0	0	0	-
x7	20000	4400	7000	0	0	-1	0	1	0	26/7
x8	10000	0	7000	0	0	0	-1	0	1	13/7
F(X1)	-30000M	-440-4400M	-700-14000M	0	0	M	M	0	0	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x8 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=7000

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (7000), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
500-(10000 * 50):7000	40-(0 * 50):7000	50-(7000 * 50):7000	1-(0 * 50):7000	0-(0 * 50):7000	0-(0 * 50):7000	0-(-1 * 50):7000	0-(0 * 50):7000	0-(1 * 50):7000
6-(10000 * 0):7000	2-(0 * 0):7000	0-(7000 * 0):7000	0-(0 * 0):7000	1-(0 * 0):7000	0-(0 * 0):7000	0-(-1 * 0):7000	0-(0 * 0):7000	0-(1 * 0):7000
20000-(10000 * 7000):7000	4400-(0 * 7000):7000	7000-(7000 * 7000):7000	0-(0 * 7000):7000	0-(0 * 7000):7000	-1-(0 * 7000):7000	0-(-1 * 7000):7000	1-(0 * 7000):7000	0-(1 * 7000):7000
10000 : 7000	0 : 7000	7000 : 7000	0 : 7000	0 : 7000	0 : 7000	-1 : 7000	0 : 7000	1 : 7000
(0)-(10000 * (-700-14000M)):7000	(-440-4400M)-(0 * (-700-14000M)):7000	(-700-14000M)-(7000 * (-700-14000M)):7000	(0)-(0 * (-700-14000M)):7000	(0)-(0 * (-700-14000M)):7000	(M)-(0 * (-700-14000M)):7000	(M)-(-1 * (-700-14000M)):7000	(0)-(0 * (-700-14000M)):7000	(0)-(1 * (-700-14000M)):7000

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	4284/7	40	0	1	0	0	1/140	0	-1/140
x4	6	2	0	0	1	0	0	0	0
x7	10000	4400	0	0	0	-1	1	1	-1
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000
F(X1)	1000-10000M	-440-4400M	0	0	0	M	-1/10-M	0	1/10+2M

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (4284/7 : 40 , 6 : 2 , 10000 : 4400 , - ) = 23/11

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x3	4284/7	40	0	1	0	0	1/140	0	-1/140	105/7
x4	6	2	0	0	1	0	0	0	0	3
x7	10000	4400	0	0	0	-1	1	1	-1	23/11
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000	-
F(X2)	1000-10000M	-440-4400M	0	0	0	M	-1/10-M	0	1/10+2M	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x7 в план 2 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=4400

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x1 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
4284/7-(10000 * 40):4400	40-(4400 * 40):4400	0-(0 * 40):4400	1-(0 * 40):4400	0-(0 * 40):4400	0-(-1 * 40):4400	1/140-(1 * 40):4400	0-(1 * 40):4400	-1/140-(-1 * 40):4400
6-(10000 * 2):4400	2-(4400 * 2):4400	0-(0 * 2):4400	0-(0 * 2):4400	1-(0 * 2):4400	0-(-1 * 2):4400	0-(1 * 2):4400	0-(1 * 2):4400	0-(-1 * 2):4400
10000 : 4400	4400 : 4400	0 : 4400	0 : 4400	0 : 4400	-1 : 4400	1 : 4400	1 : 4400	-1 : 4400
13/7-(10000 * 0):4400	0-(4400 * 0):4400	1-(0 * 0):4400	0-(0 * 0):4400	0-(0 * 0):4400	0-(-1 * 0):4400	-1/7000-(1 * 0):4400	0-(1 * 0):4400	1/7000-(-1 * 0):4400
(1/10+2M)-(10000 * (-440-4400M)):4400	(-440-4400M)-(4400 * (-440-4400M)):4400	(0)-(0 * (-440-4400M)):4400	(0)-(0 * (-440-4400M)):4400	(0)-(0 * (-440-4400M)):4400	(M)-(-1 * (-440-4400M)):4400	(-1/10-M)-(1 * (-440-4400M)):4400	(0)-(1 * (-440-4400M)):4400	(1/10+2M)-(-1 * (-440-4400M)):4400

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	33751/77	0	0	1	0	1/110	-3/1540	-1/110	3/1540
x4	15/11	0	0	0	1	1/2200	-1/2200	-1/2200	1/2200
x1	23/11	1	0	0	0	-1/4400	1/4400	1/4400	-1/4400
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000
F(X2)	2000	0	0	0	0	-1/10	0	1/10+M	M

Итерация №2.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (33751/77 : 1/110 , 15/11 : 1/2200 , - , - ) = 3200

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x3	33751/77	0	0	1	0	1/110	-3/1540	-1/110	3/1540	371426/7
x4	15/11	0	0	0	1	1/2200	-1/2200	-1/2200	1/2200	3200
x1	23/11	1	0	0	0	-1/4400	1/4400	1/4400	-1/4400	-
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000	-
F(X3)	2000	0	0	0	0	-1/10	0	1/10+M	M	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 3 войдет переменная x5.

Строка, соответствующая переменной x5 в плане 3, получена в результате деления всех элементов строки x4 плана 2 на разрешающий элемент РЭ=1/2200

На месте разрешающего элемента в плане 3 получаем 1.

В остальных клетках столбца x5 плана 3 записываем нули.

Таким образом, в новом плане 3 заполнены строка x5 и столбец x5.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
33751/77-(15/11 * 1/110):1/2200	0-(0 * 1/110):1/2200	0-(0 * 1/110):1/2200	1-(0 * 1/110):1/2200	0-(1 * 1/110):1/2200	1/110-(1/2200 * 1/110):1/2200	-3/1540-(-1/2200 * 1/110):1/2200	-1/110-(-1/2200 * 1/110):1/2200	3/1540-(1/2200 * 1/110):1/2200
15/11 : 1/2200	0 : 1/2200	0 : 1/2200	0 : 1/2200	1 : 1/2200	1/2200 : 1/2200	-1/2200 : 1/2200	-1/2200 : 1/2200	1/2200 : 1/2200
23/11-(15/11 * -1/4400):1/2200	1-(0 * -1/4400):1/2200	0-(0 * -1/4400):1/2200	0-(0 * -1/4400):1/2200	0-(1 * -1/4400):1/2200	-1/4400-(1/2200 * -1/4400):1/2200	1/4400-(-1/2200 * -1/4400):1/2200	1/4400-(-1/2200 * -1/4400):1/2200	-1/4400-(1/2200 * -1/4400):1/2200
13/7-(15/11 * 0):1/2200	0-(0 * 0):1/2200	1-(0 * 0):1/2200	0-(0 * 0):1/2200	0-(1 * 0):1/2200	0-(1/2200 * 0):1/2200	-1/7000-(-1/2200 * 0):1/2200	0-(-1/2200 * 0):1/2200	1/7000-(1/2200 * 0):1/2200
(M)-(15/11 * (-1/10)):1/2200	(0)-(0 * (-1/10)):1/2200	(0)-(0 * (-1/10)):1/2200	(0)-(0 * (-1/10)):1/2200	(0)-(1 * (-1/10)):1/2200	(-1/10)-(1/2200 * (-1/10)):1/2200	(0)-(-1/2200 * (-1/10)):1/2200	(1/10+M)-(-1/2200 * (-1/10)):1/2200	(M)-(1/2200 * (-1/10)):1/2200

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x3	3084/7	0	0	1	-20	0	1/140	0	-1/140
x5	3200	0	0	0	2200	1	-1	-1	1
x1	3	1	0	0	1/2	0	0	0	0
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000
F(X3)	2320	0	0	0	220	0	-1/10	M	1/10+M

Итерация №3.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (3084/7 : 1/140 , - , - , - ) = 43200

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x3	3084/7	0	0	1	-20	0	1/140	0	-1/140	43200
x5	3200	0	0	0	2200	1	-1	-1	1	-
x1	3	1	0	0	1/2	0	0	0	0	-
x2	13/7	0	1	0	0	0	-1/7000	0	1/7000	-
F(X4)	2320	0	0	0	220	0	-1/10	M	1/10+M	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 4 войдет переменная x6.

Строка, соответствующая переменной x6 в плане 4, получена в результате деления всех элементов строки x3 плана 3 на разрешающий элемент РЭ=1/140

На месте разрешающего элемента в плане 4 получаем 1.

В остальных клетках столбца x6 плана 4 записываем нули.

Таким образом, в новом плане 4 заполнены строка x6 и столбец x6.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
3084/7 : 1/140	0 : 1/140	0 : 1/140	1 : 1/140	-20 : 1/140	0 : 1/140	1/140 : 1/140	0 : 1/140	-1/140 : 1/140
3200-(3084/7 * -1):1/140	0-(0 * -1):1/140	0-(0 * -1):1/140	0-(1 * -1):1/140	2200-(-20 * -1):1/140	1-(0 * -1):1/140	-1-(1/140 * -1):1/140	-1-(0 * -1):1/140	1-(-1/140 * -1):1/140
3-(3084/7 * 0):1/140	1-(0 * 0):1/140	0-(0 * 0):1/140	0-(1 * 0):1/140	1/2-(-20 * 0):1/140	0-(0 * 0):1/140	0-(1/140 * 0):1/140	0-(0 * 0):1/140	0-(-1/140 * 0):1/140
13/7-(3084/7 * -1/7000):1/140	0-(0 * -1/7000):1/140	1-(0 * -1/7000):1/140	0-(1 * -1/7000):1/140	0-(-20 * -1/7000):1/140	0-(0 * -1/7000):1/140	-1/7000-(1/140 * -1/7000):1/140	0-(0 * -1/7000):1/140	1/7000-(-1/140 * -1/7000):1/140
(1/10+M)-(3084/7 * (-1/10)):1/140	(0)-(0 * (-1/10)):1/140	(0)-(0 * (-1/10)):1/140	(0)-(1 * (-1/10)):1/140	(220)-(-20 * (-1/10)):1/140	(0)-(0 * (-1/10)):1/140	(-1/10)-(1/140 * (-1/10)):1/140	(M)-(0 * (-1/10)):1/140	(1/10+M)-(-1/140 * (-1/10)):1/140

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	43200	0	0	140	-2800	0	1	0	-1
x5	46400	0	0	140	-600	1	0	-1	0
x1	3	1	0	0	1/2	0	0	0	0
x2	73/5	0	1	1/50	-2/5	0	0	0	0
F(X4)	6640	0	0	14	-60	0	0	M	M

Итерация №4.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (- , - , 3 : 1/2 , - ) = 6

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	43200	0	0	140	-2800	0	1	0	-1	-
x5	46400	0	0	140	-600	1	0	-1	0	-
x1	3	1	0	0	1/2	0	0	0	0	6
x2	73/5	0	1	1/50	-2/5	0	0	0	0	-
F(X5)	6640	0	0	14	-60	0	0	M	M	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x1 в план 5 войдет переменная x4.

Строка, соответствующая переменной x4 в плане 5, получена в результате деления всех элементов строки x1 плана 4 на разрешающий элемент РЭ=1/2

На месте разрешающего элемента в плане 5 получаем 1.

В остальных клетках столбца x4 плана 5 записываем нули.

Таким образом, в новом плане 5 заполнены строка x4 и столбец x4.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
43200-(3 * -2800):1/2	0-(1 * -2800):1/2	0-(0 * -2800):1/2	140-(0 * -2800):1/2	-2800-(1/2 * -2800):1/2	0-(0 * -2800):1/2	1-(0 * -2800):1/2	0-(0 * -2800):1/2	-1-(0 * -2800):1/2
46400-(3 * -600):1/2	0-(1 * -600):1/2	0-(0 * -600):1/2	140-(0 * -600):1/2	-600-(1/2 * -600):1/2	1-(0 * -600):1/2	0-(0 * -600):1/2	-1-(0 * -600):1/2	0-(0 * -600):1/2
3 : 1/2	1 : 1/2	0 : 1/2	0 : 1/2	1/2 : 1/2	0 : 1/2	0 : 1/2	0 : 1/2	0 : 1/2
73/5-(3 * -2/5):1/2	0-(1 * -2/5):1/2	1-(0 * -2/5):1/2	1/50-(0 * -2/5):1/2	-2/5-(1/2 * -2/5):1/2	0-(0 * -2/5):1/2	0-(0 * -2/5):1/2	0-(0 * -2/5):1/2	0-(0 * -2/5):1/2
(M)-(3 * (-60)):1/2	(0)-(1 * (-60)):1/2	(0)-(0 * (-60)):1/2	(14)-(0 * (-60)):1/2	(-60)-(1/2 * (-60)):1/2	(0)-(0 * (-60)):1/2	(0)-(0 * (-60)):1/2	(M)-(0 * (-60)):1/2	(M)-(0 * (-60)):1/2

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	60000	5600	0	140	0	0	1	0	-1
x5	50000	1200	0	140	0	1	0	-1	0
x4	6	2	0	0	1	0	0	0	0
x2	10	4/5	1	1/50	0	0	0	0	0
F(X5)	7000	120	0	14	0	0	0	M	M

Итерация №5.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

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

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

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

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

min (60000 : 5600 , 50000 : 1200 , 6 : 2 , 10 : 4/5 ) = 3

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	min
x6	60000	5600	0	140	0	0	1	0	-1	105/7
x5	50000	1200	0	140	0	1	0	-1	0	412/3
x4	6	2	0	0	1	0	0	0	0	3
x2	10	4/5	1	1/50	0	0	0	0	0	121/2
F(X6)	7000	120	0	14	0	0	0	M	M	0

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

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 6 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 6, получена в результате деления всех элементов строки x4 плана 5 на разрешающий элемент РЭ=2

На месте разрешающего элемента в плане 6 получаем 1.

В остальных клетках столбца x1 плана 6 записываем нули.

Таким образом, в новом плане 6 заполнены строка x1 и столбец x1.

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

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
60000-(6 * 5600):2	5600-(2 * 5600):2	0-(0 * 5600):2	140-(0 * 5600):2	0-(1 * 5600):2	0-(0 * 5600):2	1-(0 * 5600):2	0-(0 * 5600):2	-1-(0 * 5600):2
50000-(6 * 1200):2	1200-(2 * 1200):2	0-(0 * 1200):2	140-(0 * 1200):2	0-(1 * 1200):2	1-(0 * 1200):2	0-(0 * 1200):2	-1-(0 * 1200):2	0-(0 * 1200):2
6 : 2	2 : 2	0 : 2	0 : 2	1 : 2	0 : 2	0 : 2	0 : 2	0 : 2
10-(6 * 4/5):2	4/5-(2 * 4/5):2	1-(0 * 4/5):2	1/50-(0 * 4/5):2	0-(1 * 4/5):2	0-(0 * 4/5):2	0-(0 * 4/5):2	0-(0 * 4/5):2	0-(0 * 4/5):2
(M)-(6 * (120)):2	(120)-(2 * (120)):2	(0)-(0 * (120)):2	(14)-(0 * (120)):2	(0)-(1 * (120)):2	(0)-(0 * (120)):2	(0)-(0 * (120)):2	(M)-(0 * (120)):2	(M)-(0 * (120)):2

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	43200	0	0	140	-2800	0	1	0	-1
x5	46400	0	0	140	-600	1	0	-1	0
x1	3	1	0	0	1/2	0	0	0	0
x2	73/5	0	1	1/50	-2/5	0	0	0	0
F(X6)	6640	0	0	14	-60	0	0	M	M

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

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8
x6	43200	0	0	140	-2800	0	1	0	-1
x5	46400	0	0	140	-600	1	0	-1	0
x1	3	1	0	0	1/2	0	0	0	0
x2	73/5	0	1	1/50	-2/5	0	0	0	0
F(X7)	6640	0	0	14	-60	0	0	M	M

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

Практическая работа № 4

ТРАНСПОРТНЫЕ ЗАДАЧИ

ЦЕЛЬ РАБОТЫ: овладеть методикой построения опорных планов транспортных задач, и их оптимизации.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ.

Необходимо составить план-график доставки туристов из аэропорта в гостиницы (Вj, j=1-). В распоряжении турфирмы есть несколько автобусов (Ai, i=1).

	В1	В2	В3	В4	Кол.тур.
А1	3	4	1	5	60
А2	8	3	3	6	60
А3	9	2	4	7	50
Кол. мест	100	120	80	100

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

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

F = ??cijxij, (1)

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

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

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

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

	1	2	3	4	Запасы
1	3	4	1	5	60
2	8	3	3	6	60
3	9	2	4	7	50
Потребности	100	120	80	100

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

?a = 60 + 60 + 50 = 170

?b = 100 + 120 + 80 + 100 = 400

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

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

	1	2	3	4	Запасы
1	3	4	1	5	60
2	8	3	3	6	60
3	9	2	4	7	50
4	0	0	0	0	230
Потребности	100	120	80	100

Метод северо-западного угла

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

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

План начинается заполняться с верхнего левого угла.

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

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

x11 = min(60,100) = 60.

3	x	x	x	60 - 60 = 0
8	3	3	6	60
9	2	4	7	50
0	0	0	0	230
100 - 60 = 40	120	80	100	0

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

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

x21 = min(60,40) = 40.

3	x	x	x	0
8	3	3	6

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

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

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

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

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

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

  Задачи операционного исследования. Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе технологии симплекс-метода. Анализ результатов базовой аналитической модели и предложения по модификации.
  
  курсовая работа [1,5 M], добавлен 12.12.2009
  

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

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

• Формирование и решение линейных задач

  Моделирование экономических систем: понятие и принципы, типы моделей и оценка их адекватности. Примеры задач линейного программирования: транспортная задача, ее общая формулировка и графическая интерпретация решения задачи. Анализ симплекс-таблиц.
  
  курсовая работа [237,9 K], добавлен 22.11.2012
  

• Исследование операций, методы оптимизации

  Построение экономических и математических моделей принятия решений в условиях неопределенности. Общая методология оптимизационных задач, оценка преимуществ выбранного варианта. Двойственность и симплексный метод решения задач линейного программирования.
  
  курс лекций [496,2 K], добавлен 17.11.2011
  

• Моделирование процессов и объектов в металлургии

  Основы понятия регрессионного анализа и математического моделирования. Численное решение краевых задач математической физики методом конечных разностей. Решение стандартных и оптимизационных задач, систем линейных уравнений. Метод конечных элементов.
  
  реферат [227,1 K], добавлен 18.04.2015
  

• Разработка программных средств анализа графика функции и решение оптимизационных задач

  Программный пакет Microsoft Office и табличный процессор Excel. Задачи и основные функции в Microsoft Excel. Формулы в Microsoft Excel. Общие сведения об алгоритмах. Метод половинного деления. Понятие оптимизационных задач и оптимизационных моделей.
  
  курсовая работа [333,4 K], добавлен 17.03.2008
  

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

  Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
  
  курсовая работа [56,9 K], добавлен 04.05.2011
  

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

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

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

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

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

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

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

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

• Сущность и использование транспортных задач

  Методы линейного программирования; теория транспортной задачи, ее сущность и решение на примере ООО "Дубровчанка+": характеристика предприятия, организационная структура и статистические данные. Построение и решение экономико-математической модели.
  
  курсовая работа [652,5 K], добавлен 04.02.2011
  

• Решение экономических задач оптимизационного типа

  Исследование методики построения модели и решения на ЭВМ с ее помощью оптимизационных экономико-математических задач. Характеристика программных средств, позволяющих решать такие задачи на ЭВМ. Определение оптимального варианта производства продукции.
  
  лабораторная работа [79,3 K], добавлен 07.12.2013
  

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

  Построение математических моделей по определению плана выпуска изделий, обеспечивающего максимальную прибыль, с помощью графического и симплексного метода. Построение моделей по решению транспортных задач при применении метода минимальной стоимости.
  
  задача [169,2 K], добавлен 06.01.2012
  

• Постановка задачи по оптимизации

  Построение базовой аналитической модели. Описание вычислительной процедуры. Решение задачи оптимизации на основе симплекс-таблиц. Анализ на чувствительность к изменению. Примеры постановок и решений перспективных оптимизационных управленческих задач.
  
  курсовая работа [621,6 K], добавлен 16.02.2015
  

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

  Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
  
  курсовая работа [106,0 K], добавлен 05.10.2014
  

• Примеры построение линейных математических моделей

  Анализ основных способов построения математической модели. Математическое моделирование социально-экономических процессов как неотъемлемая часть методов экономики, особенности. Общая характеристика примеров построения линейных математических моделей.
  
  курсовая работа [1,3 M], добавлен 23.06.2013
  

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

  Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
  
  реферат [193,4 K], добавлен 28.12.2008
  

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