Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Контрольная работа по прикладной математике - файл задача 6.doc


Лабораторная работа - Контрольная работа по прикладной математике
скачать (145.2 kb.)

Доступные файлы (5):

Задача 10.doc88kb.19.04.2010 13:21скачать
задача 6.doc361kb.18.01.2011 18:28скачать
задача 7.rtf147kb.18.04.2010 10:05скачать
задача 8.xls29kb.18.04.2010 10:35скачать
задача 9.xls27kb.18.04.2010 10:59скачать

задача 6.doc

Контрольная работа №2.

Вариант 13

Задача № 6


Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2.

На изготовление единицы Изделия 1 требуется затратить а11 кг сырья первого типа, а21 кг сырья второго типа, а31 кг сырья третьего типа.

На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.

Рыночная цена единицы изделия 1 составляет c1 тыс. руб, а единицы изделия 2 c2 тыс. руб.

Требуется:

1) построить математическую модель задач;

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

3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, при помощи табличного симплекс-метода решения задачи линейного программирования;

4) найти двойственные оценки сырья каждого типа и коэффициенты структурных сдвигов.


а11=7

а12=2

b1=560

а21=3

а22=3

b2=300

а31=1

а32=5

b3=332

с1=70

с2=110




Решение.

1. Построение экономико-математической модели задачи.

Составим следующую таблицу:




Изделие 1

Изделие 2

Запасы сырья

Сырье I

7

2

560

Сырье II

3

3

300

Сырье III

1

5

332

Цены на изделия

70руб.

110руб.





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

Пусть выпущено x1 шт. Изделия 1 и x2 шт. Изделия 2.

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

(1)

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

Сырье I: (кг.)

Сырье II: (кг.)

Сырье III: (кг.)

Мы не можем израсходовать сырья больше, чем имеется в наличии. Кроме того, по смыслу задачи . В результате получаем систему линейных ограничений данной задачи:

(2)

Целевая функция (1) вместе с системой линейных ограничений (2) представляет собой экономико-математическую модель данной задачи.

^ 2. Решение производственной задачи геометрическим методом.

2.1. Построение множества решений системы линейных ограничений.

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

(2.1) 

Если x1=0, то x2=280. Получаем точку (0; 280).

Если x2=0, то x1=80. Получаем точку (80; 0).

(2.2) 

Если x1=0, то x2=100. Получаем точку (0; 100).

Если x2=0, то x1=100. Получаем точку (100; 0).

(2.3) 

Если x1=0, то x2=66,4. Получаем точку (0; 66,4).

Если x2=0, то x1=332. Получаем точку (332; 0).

(2.4)  . Этой прямой соответствует ось Ox1.

(2.5)  . Этой прямой соответствует ось Ox2.

Результаты вычислений и построений представлены на рис.2. Решением системы неравенств является многоугольник OABCD, иначе называемый симплексом решений задачи линейного программирования (1)-(2).



Рис. 2. Симплекс решений системы линейных ограничений (2).
2.2. Нахождение координат угловых точек симплекса решений.

Нахождение координат точек O, A, D не представляет особых трудностей, и их можно сразу же выписать:

O (0;0)

A (0;66,4)

D (80;0)

Для нахождения координат точки C предварительно отметим, что она является точкой пересечения прямых (2.1) и (2.2). Следовательно, для нахождения ее координат необходимо совместно решить уравнения этих прямых.



Таким образом, координаты точки C (72; 28).

Точка B лежит на пересечении прямых (2.2) и (2.3). Поэтому ее координаты находим, решая следующую систему уравнений:



Таким образом, координаты точки B (42; 58).
2.3. Выбор оптимального плана.

В линейном программировании доказывается теорема о том, что если оптимальное решение задачи линейного программирования существует, то оно обязательно совпадает с координатами одной из угловых точек симплекса решений системы линейных ограничений (2).

Вычисляем значения целевой функции (1) в каждой угловой точке и выбираем наибольшее:



Таким образом, оптимальный план выпуска изделий соответствует точке ^ B и равен x1=42 шт. Изделия 1 и x2=58 шт. Изделия 2. Выручка от реализации в этом случае будет максимальна и составит 9320 руб.

Найдем остатки сырья каждого типа, обозначая их x3; x4; x5 соответственно.



Ответ: Оптимальный план выпуска изделий составляет x1=42 шт. Изделия 1 и x2=58 шт. Изделия 2. Выручка от их последующей реализации в этом случае будет максимальна и составит 9320 руб. При этом все запасы Сырья III и Сырья II будут израсходованы полностью, а остаток Cырья I составит 150 кг.

^ 3. Симплексный метод решения задачи.

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

7 x1 + 2 x2 <=560

3 x1 + 3 x2 <=300

x1 + 5 x2 <=332

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

7x1 + 2x2 + 1x3 + 0x4 + 0x5 = 560

3x1 + 3x2 + 0x3 + 1x4 + 0x5 = 300

1x1 + 5x2 + 0x3 + 0x4 + 1x5 = 332

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

x3 , x4 , x5

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

X1 = (0,0,560,300,332)

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

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

План


Базис


В


x 1


x 2


x 3


x 4


x 5


min


1


x3


560


7


2


1


0


0


280



x4


300


3


3


0


1


0


100



x5


332


1


5


0


0


1


66.4


Индексная строка


F(X1)


0


-70


-110


0


0


0


0


Итерация №0

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

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

Вычислим значения D i по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей

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

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

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

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

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

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

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

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

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

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

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

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

B


x 1


x 2


x 3


x 4


x 5





























332 / 5 = 66.4


1 / 5 = 0.2


5 / 5 = 1


0 / 5 = 0


0 / 5 = 0


1 / 5 = 0.2
















План


Базис


В


x 1


x 2


x 3


x 4


x 5


min





2


x3


427.2


6.6


0


1


0


-0.4


64.73






x4


100.8


2.4


0


0


1


-0.6


42






x2


66.4


0.2


1


0


0


0.2


332





Индексная строка


F(X2)


7304


-48


0


0


0


22


0


Итерация №1

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

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

Вычислим значения D i по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей

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

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

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

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

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

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

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

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

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

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

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

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

B


x 1


x 2


x 3


x 4


x 5














100.8 / 2.4 = 42


2.4 / 2.4 = 1


0 / 2.4 = 0


0 / 2.4 = 0


1 / 2.4 = 0.42


-0.6 / 2.4 = -0.25




























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

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

План


Базис


В


x 1


x 2


x 3


x 4


x 5


min


3


x3


150


0


0


1


-2.75


1.25


64.73



x1


42


1


0


0


0.42


-0.25


42



x2


58


0


1


0


-0.08


0.25


332


Индексная строка


F(X3)


9320


0


0


0


20


10


0


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

x3 = 150

x1 = 42

x2 = 58

F(X) = 70*42 + 110*58 = 9320
^ 4. Двойственная задача.

Естественно, что на практике запасы сырья каждого типа необходимо менять таким образом, чтобы добавочная продукция составляла целое число. В рассматриваемой задаче изменения запасов сырья первого и второго типа должны быть кратны 5 кг: 5 кг, 10 кг, 15 кг и т.д.


Скачать файл (145.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации