Линейное программирование. Геометрический метод решений задач

 

Ключевой элемент 0,1

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

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

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

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

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

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

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

Шаг 3: Элементы таблицы преобразуются и записывают в новую таблицу

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
126	x6	1200	0	1	1	0	0	10

 

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

– для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке – элемент ключевого столбца;

– соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключевой элемент;

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

Столбец х0

                  

 

x0

80

240

1200

151200

 

После преобразований получаем новую таблицу:

Итерация 1

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

Включение на первой итерации в план неизвестной х3 обеспечит сумму прибыли 151200 руб.

Шаг 4: Решение задачи продолжается, так как в целевой строке так находятся отрицательные коэффициенты.

Наибольший по модулю элемент -108. Значит ключевой столбец х1.

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

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

 

 

 

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

Определяем ключевую строку:

80/0,8=100            240/0,4=600         

Минимальное значение в х4

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

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

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

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

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

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

После преобразований получаем новую таблицу:

 

 

 

 

Итерация 2

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
108	x1	100	1	-0.13	0	1.25	0	-7.5
0	x5	200	0	0.15	0	-0.5	1	0
126	x3	1200	0	1	1	0	0	10
		162000	0	0.5	0	135	0	450

 

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

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
108	x1	100	1	-0.13	0	1.25	0	-7.5
0	x5	200	0	0.15	0	-0.5	1	0
126	x3	1200	0	1	1	0	0	10
		162000	0	0.5	0	135	0	450

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

x1 = 100

x3 = 1200

F(X) = 108 • 100 + 126 • 1200 = 162000

Далее решим задачу с помощью MS Excel.

Отведем ячейки С3, С4 и С5 под значения переменных Х1, Х2, и Х3(рис. 1).

Рис. 1. Диапазоны, отведенные под переменные, целевую функцию и ограничения

В ячейку С6 ведем функцию цели: =СУММ(С3:С5), в ячейки А10 : С10 введем левые части ограничений:

=0,8*В3+0,5*В4+0,6*В5

=0,4*В3+0,4*В4+0,3*В5

=0,1*В4+0,1*В5,

а в ячейки С3, С4 и С5 введем левые части ограничений (рис.1.):

=108*В3

=112*В4

=126*В5

Выберем команды Сервис/Поиск решения и заполним открывшееся диалоговое окно Поиск решения как показано на рис 2.

Для ввода ограничений нажмем кнопку Добавить.

 

Рис. 2. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике

В диалоговом окне Параметры поиска решения установим флажок Линейная модель (Рис.3.).

Рис 3. Параметры поиска решения

После нажатия кнопки Выполнить открывается окно Результаты поиска решения, которое сообщает, что решение найдено (рис. 4).

Рис. 4. Результаты поиска решения

Результаты расчета задачи представлены на рис. 5,  из которого видно, что максимальную прибыль в количестве 162000 руб. можно получить производя сырья А в количестве 100 т и сырья С в количестве 1200 т и не произведя при этом сырья В.

Рис. 5. Результаты расчета

 

 

 

 

 

Заключение

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1. Ашманов С.А. Линейное программирование. – М.: Наука, 2008.
2. Коротков М., Гаврилов М. «Основы линейного программирования», 2007 г..
3. Лищенко «Линейное и нелинейное программирование», М. 2006 г.
4. Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007 г.

Интернет – ресурсы

5. http://ru.wikipedia.org/