МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ПЕНЗЕНСКАЯГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ

(ПГТА)

Кафедра:

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Методы и модели»

Выполнил: студент гр.11ЭМ1б

Лебедева Е.В.

Проверил:

Шишов В.П.

Пенза,2012

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

Предприниматель арендовал технологическую линию деревообрабатывающих станков для изготовления вагонки. Магазин «Стройматериалы» заказал комлекты из трех элементов: два длиной 2м и один длиной 1,25м. поставщик завозит на грузовом автомобиле доски длиной по 4 м-50 шт.

Определить, как распилить доски, чтобы продать максимальное количество комплектов.

Составим ЭММ задачи:

F(X) = 2x₁+1.25x₂

при следующих ограничениях:

2x₁+2x₂≤200

2x₁≤40

x_1, x₂ ≥0

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

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

2x₁+2x₂≤200

2x₁≤40

2x₁ + 2x₂ + 1x₃ + 0x₄ = 200

2x₁ + 0x₂ + 0x₃ + 1x₄ = 40

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

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

x₃, x₄,

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

X1 = (0,0,200,40)

Базис	В	x1	x2	x3	x4
x3	200	2	2	1	0
x4	40	2	0	0	1
F(X0)	0	-2	-1.25	0	0

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

Итерация №0.

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

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

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

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

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

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

Базис	В	x1	x2	x3	x4	min
x3	200	2	2	1	0	100
x4	40	2	0	0	1	20
F(X1)	0	-2	-1.25	0	0	0

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

Базис	В	x1	x2	x3	x4
x3	160	0	2	1	-1
x1	20	1	0	0	0.5
F(X1)	40	0	-1.25	0	1

Итерация №1.

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

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

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

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

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

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

Базис	В	x1	x2	x3	x4	min
x3	160	0	2	1	-1	80
x1	20	1	0	0	0.5	-
F(X2)	40	0	-1.25	0	1	0

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

Базис	В	x1	x2	x3	x4
x2	80	0	1	0.5	-0.5
x1	20	1	0	0	0.5
F(X2)	140	0	0	0.63	0.38

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

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

Базис	В	x1	x2	x3	x4
x2	80	0	1	0.5	-0.5
x1	20	1	0	0	0.5
F(X3)	140	0	0	0.63	0.38

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

x₂ = 80

x₁ = 20

F(X) = 2*20 + 1.25*80 = 140

РЕШЕНИЕ В EXCEL:

1. Внесите данные. Мышкой или с помощью клавиатуры перейдите к ячейке F4

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

3. В диалоговом окне укажите: вид поиска (максимальное значение) в поле изменяя ячейки: $B$2:$C$2 в поле Ограничения добавьте заданные ограничения Поле должно иметь следующее содержание: $B$2:$C$2>=0 $F$6<=$E$6 $F$7<=$E$7

4. Нажмите на кнопку Выполнить