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

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИНСТИТУТ КОМПЬЮТЕРНЫХ СИСТЕМ

КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ И ТЕХНОЛОГИЙ

Расчетно – графическая работа

По дисциплине: «Математические методы исследования операций»

На тему: «Решение задач линейного программирования симплекс- методом»

Вариант № 8

Выполнил:

Ст.гр. АИ-111

Криворот Стас

Проверил:

Болтенков В.А.

Одесса 2013

Вариант 8

Фермер располагает удобрениями двух видов: У1 и У2. В одной тонне удобрения У1 содержится 30 ед. вещества В1, 60 ед. вещества В2 и 90 ед. вещества В3, а в 1 тонне удобрения У2 соответственно: 10, 60, 150 ед. На 1 га должно быть внесено не более 200 ед. вещества В1, 600 ед. В2 и 1200 ед. В3. При соблюдении этих норм прибавка урожая от внесения одной тонны удобрения У1 составит 4500 кг, удобрения У2 — 3500 кг. Какие количества удобрений надо внести на 1 га, чтобы прибавка урожая была наибольшей?

Решение (вручную)

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

	B1	B2	B3	Прибавка
Y1	30	60	90	4500
Y2	10	60	150	3500
Рубеж вещ- в	200	600	1200

Пусть x1 – тоннаж удобрения Y1, x2 – тоннаж удобрения Y2.

Согласно условиям, получим следующую задачу ЛП:

Максимизировать Z = 4500x1+3500x2

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

30x1+10x2 <= 200

60x1+60x2 <=600

90x1+150x2<=1200

Симплекс-метод.

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

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

30x₁ + 10x₂≤200

60x₁ + 60x₂≤600

90x₁ + 150x₂≤1200

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

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

30x₁ + 10x₂ + 1x₃ + 0x₄ + 0x₅ = 200

60x₁ + 60x₂ + 0x₃ + 1x₄ + 0x₅ = 600

90x₁ + 150x₂ + 0x₃ + 0x₄ + 1x₅ = 1200

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

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

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

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

x₃, x₄, x₅,

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

X1 = (0,0,200,600,1200)

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

Базис	B	x1	x2	x3	x4	x5
x3	200	30	10	1	0	0
x4	600	60	60	0	1	0
x5	1200	90	150	0	0	1
F(X0)	0	-4500	-3500	0	0	0

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

Итерация №0.

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

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

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

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

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

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

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

min (200 : 30 , 600 : 60 , 1200 : 90 ) = 6²/₃

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

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

Базис	B	x1	x2	x3	x4	x5	min
x3	200	30	10	1	0	0	6^2/3
x4	600	60	60	0	1	0	10
x5	1200	90	150	0	0	1	13^1/3
F(X1)	0	-4500	-3500	0	0	0	0

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

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

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

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

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

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

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

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

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

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

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

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

B	x 1	x 2	x 3	x 4	x 5
200 : 30	30 : 30	10 : 30	1 : 30	0 : 30	0 : 30
600-(200 • 60):30	60-(30 • 60):30	60-(10 • 60):30	0-(1 • 60):30	1-(0 • 60):30	0-(0 • 60):30
1200-(200 • 90):30	90-(30 • 90):30	150-(10 • 90):30	0-(1 • 90):30	0-(0 • 90):30	1-(0 • 90):30
0-(200 • -4500):30	-4500-(30 • -4500):30	-3500-(10 • -4500):30	0-(1 • -4500):30	0-(0 • -4500):30	0-(0 • -4500):30

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

Базис	B	x1	x2	x3	x4	x5
x1	6^2/3	1	^1/3	^1/30	0	0
x4	200	0	40	-2	1	0
x5	600	0	120	-3	0	1
F(X1)	30000	0	-2000	150	0	0

Итерация №1.

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

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

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

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

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

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

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

min (6²/₃ : ¹/₃ , 200 : 40 , 600 : 120 ) = 5

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

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

Базис	B	x1	x2	x3	x4	x5	min
x1	6^2/3	1	^1/3	^1/30	0	0	20
x4	200	0	40	-2	1	0	5
x5	600	0	120	-3	0	1	5
F(X2)	30000	0	-2000	150	0	0	0

Поскольку в последнем столбце присутствует несколько минимальных элементов 5, то номер строки выбираем по правилу Креко.

Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=5, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.