Лабораторная работа по "Экономико-математическому моделированию"

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ УКРАИНЫ

ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ  ЗАВЕДЕНИЕ «ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

УЧЕБНЫЙ НАУЧНЫЙ ИНСТИТУТ «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ И  МЕНЕДЖМЕНТА»

ФАКУЛЬТЕТ МЕНЕДЖМЕНТА

КАФЕДРА ЭКОНОМИЧЕСКОЙ КИБЕРНЕТИКИ

 

 

 

 

 

 

 

Лабораторная работа №9

по Экономико-математическому моделированию

 

 

 

 

                      Выполнила:

                                                              студентка II курса группы ЭК 12-а

                                                            направления подготовки 6.050302

специальности экономическая кибернетика

 Тарасова Алёна

 

 

   Проверили:

   Горчакова И.А. ________________(оценка)

   Гизатулин А.М. ________________(оценка)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Донецьк – 2013г.

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

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

Осуществить промежуточную и итоговую проверку через «Поиск решения» в Excel.

1. Формулировка полностью целочисленной задачи линейного

программирования.

 

 

Целевая функція принимает значение:

F(x)= 3x₁ + x_2max

2. Решения задачи.

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

 Поскольку в правой  части присутствуют отрицательные  значения, умножим соответствующие  строки на (-1).

 Определим максимальное  значение целевой функции F(x)= 3x₁ + x_2max при следующих условиях-ограничений:

 

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных. В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅. 

3x₁-2x₂ + 1x₃ + 0x₄ + 0x₅ = 3

5x₁ + 0x₂ + 0x₃-1x₄ + 0x₅ = 10

2x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ = 5

Введем искусственные переменные x: в 2-м равенстве вводим переменную x₆; 

3x₁-2x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 3

5x₁ + 0x₂ + 0x₃-1x₄ + 0x₅ + 1x₆ = 10

2x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 5

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

F(X) = 3x₁+x₂ - Mx₆ → max

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

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

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

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

x₆ = 10-5x₁+x₄

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

F(X) = 3x₁ + x₂ - M(10-5x₁+x₄) → max

или

F(X) = (3+5M)x₁+(1)x₂+(-M)x₄+(-10M) → max

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

 

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

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

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

x₃, x₆, x₅,

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

X1 = (0,0,3,0,5,10)

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

 

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

Итерация №1.

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

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

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

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

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

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

min (3 : 3 , 10 : 5 , 5 : 2 ) = 1

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

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

 

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	3	3	-2	1	0	0	0	1
x6	10	5	0	0	-1	0	1	2
x5	5	2	0	0	0	1	0	21/2
F(X1)	-10M	-3-5M	-1	0	M	0	0	0

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

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

Вместо переменной x₃ в план 1 войдет переменная x₁.

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5	x 6
3 : 3	3 : 3	-2 : 3	1 : 3	0 : 3	0 : 3	0 : 3
10-(3 • 5):3	5-(3 • 5):3	0-(-2 • 5):3	0-(1 • 5):3	-1-(0 • 5):3	0-(0 • 5):3	1-(0 • 5):3
5-(3 • 2):3	2-(3 • 2):3	0-(-2 • 2):3	0-(1 • 2):3	0-(0 • 2):3	1-(0 • 2):3	0-(0 • 2):3
(0)-(3 • (-3-5M)):3	(-3-5M)-(3 • (-3-5M)):3	(-1)-(-2 • (-3-5M)):3	(0)-(1 • (-3-5M)):3	(M)-(0 • (-3-5M)):3	(0)-(0 • (-3-5M)):3	(0)-(0 • (-3-5M)):3

 

Итерация№2.

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

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

x₁, так как это наибольший коэффициент.

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

И из них выберем наименьшее: min (3:3, 10:5, 5:2)=1. 

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

 

План	Базис	B	x1	x2	x3	x4	x5	x6	min
2	x1	1	1	-2 /3	1 /3	0	0	0	-
	x6	5	0	71/3	-12/3	-1	0	1	15 /22
	x5	3	0	21/3	-2 /3	0	1	0	12/7
Индексная строка	F(X2)	3-5M	0	-3-71/3M	1+12/3M	1M	0	0	0

Итерация №3. 

Текущий опорный план неоптимален, так как в индексной строк

находятся отрицательные  коэффициенты. 

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

Вычислим значения D_i по строкам как частное от деления: и из них выберем наименьшее: 

min (- , 5 : 7¹/₃ , 3 : 2¹/₃ ) = ¹⁵/₂₂

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

 

План	Базис	B	x1	x2	x3	x4	x5	x6	min
3	x1	15/11	1	0	2 /11	-1 /11	0	1 /11	-
	x2	15 /22	0	1	-5 /22	-3 /22	0	3 /22	-
	x5	19/22	0	0	-3 /22	7 /22	1	-7 /22	43/7
Индексная строка	F(X3)	51/22	0	0	7 /22	-9 /22	0	9 /22+1M	0

 

 Итерация №4. 

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

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

Вычислим значения D_i по строкам как частное от деления:  и из них выберем наименьшее: 

min (- , - , 1⁹/₂₂ : ⁷/₂₂ ) = 4³/₇

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

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

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

План	Базис	B	x1	x2	x3	x4	x5	x6
4	x1	16/7	1	0	1 /7	0	2 /7	0
	x2	12/7	0	1	-2 /7	0	3 /7	0
	x4	43/7	0	0	-3 /7	1	31/7	-1
Индексная строка	F(X4)	66/7	0	0	1 /7	0	12/7	1M