dhfdvn

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФБОУ ВПО «Поволжский государственный технологический университет»

Кафедра высшей математики

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

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

Вариант 26

Выполнила: студентка

группы ЭБ-21

Сивушкина Е.М

Проверил: доцент кафедры

высшей математики

Романов В.А.

Йошкар-Ола

2013

Задача 1.

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

1. Определить план выпуска продукции из условия максимизации его стоимости.

2*. Определить интервал изменения цены на продукцию А, при котором структура оптимального решения останется неизменной.

3*. Определить интервал изменения цены на продукцию В, при котором структура оптимального решения останется неизменной.

Сырьё	Норма расходов		Ресурсы
	А	В
I	1	5	1000
II	2	1	1600
III	3	1	800
Цена	7	3

1) Построим математическую модель задачи. Пусть х₁ и х₂ – количество изделий вида А и В соответственно, планируемых к производству. Стоимость всей продукции будет равна денежных единиц. Затраты сырья видов I, II и III составят соответственно величины , и . Математическая модель в краткой записи имеет вид:

Решим задачу графическим методом. Построим уравнение x₁+5x₂ = 1000 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 20. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 1000. Соединяем точку (0;20) с (1000;0) прямой линией. Построим уравнение 2x₁+x₂ = 1600 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 1600. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ =800. Соединяем точку (0;1600) с (800;0)

прямой линией. Построим уравнение 3x₁+x₂ = 800 по двум точкам. Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 800. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 270. Соединяем точку (0;800) с (270;0) прямой линией. Рассмотрим целевую функцию задачи F = 7x₁+3x₂ → max. Построим прямую, отвечающую значению функции F = 0: F = 7x₁+3x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(x). Начало вектора – точка (0; 0), конец – точка (7; 3). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. Область допустимых решений представляет собой многоугольник ACED

Прямая F(x) пересекает область в точке D. Точка D получена в результате пересечения прямых x₂=0 и 3x₁+2x₂=900

Задача 2

Предприятие производит 3 вида продукции А₁, А₂, А₃, используя сырье двух видов В₁ и В₂. Известны затраты сырья i-ого вида на единицу изделия j–ого вида a_ij. Количество сырья b_i (i=1,2), а также прибыль, полученная о единицы изделия j-ого вида c_j (j=1,2,3).

Сколько изделий каждого вида необходимо произвести, чтобы получить

1. максимум прибыли;

2. максимум товарной продукции

3*) построить двойственную задачу к модели из п.1 и решить её графически.

Исходные данные заданы матрицами:

Решение

1) Построим математическую модель задачи. Пусть х₁, х₂ и х₃ – количество изделий вида А₁, А₂ и А₃ соответственно, производимых предприятием. Тогда прибыль, получаемая от всех произведенных изделий, выразится суммой . Затраты сырья видов В₁ и В₂ составят соответственно величины и . Таким образом математически задача сводится к нахождению наибольшего значения функции на множестве неотрицательных значений переменных, удовлетворяющих неравенствам и . Для решения модели симплексным методом приведем её к каноническому виду:

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

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

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

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

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

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

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

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

min (800 : 1 , 1500 : 3 ) = 500

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

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

Пересчитаем симплекс - таблицу:

3^1/3	0	1^1/3	1	^-1/3	300
^2/3	1	^2/3	0	^1/3	500
^2/3	0	1^2/3	0	1^1/3	2000

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

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

x₂=(500,0,300,0)

F(X) = 4•500 = 2000

Для получения максимальной прибыли в 2000 денежных единиц следует произвести 500 единиц изделий А₂ и 300 единиц изделий А₃.

2). Задача на максимум товарной продукции отличается только целевой функцией . Приведем её решение в виде последовательности симплекс – таблиц.

4	1	2	1	0	800
2	3	2	0	1	1500
-1	-1	-1	0	0	0

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

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

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

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: min (800 : 2 , 1500 : 2 ) = 400

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

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

2	^1/2	1	^1/2	0	400
-2	2	0	-1	1	700
1	^-1/2	0	^1/2	0	400

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

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

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

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2и из них выберем наименьшее: min (400 : ¹/₂ , 700 : 2 ) = 350

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

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

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

2^1/2	0	1	^3/4	^-1/4	225
-1	1	0	^-1/2	^1/2	350
^1/2	0	0	^1/4	^1/4	575

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

x₃ = 225

x₂ = 350

F(X) = 1•225 + 1•350 = 575

Для получения максимума товарной продукции в 575 денежных единиц следует произвести 350 единиц изделий А₂ и 225единиц изделий А₃.

3). Рассмотрим модель

и составим двойственную задачу к ней:

L₁: 4y₁+2y₂=2 L₂: 1y₁+3y₂=4 L₃: 2y₁+2y₂=1 y₁=0; y₂=1 y₁=0; y₂=4/3 y₁=0; y₂=1/2 y₁=1/2; y₂=0 y₁=4; y₂=0 y₁=1/2; y₂=0

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

Задача 3

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

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

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

	В1	В2	В3	В4	a
A1	4	2	5	6	200
A2	3	1	4	2	175
A3	6	8	7	3	225
A4	2	7	5	9	200
b	80	120	100	130

Решение

Так как суммарная потребность груза в пунктах назначения превышают запасы груза на базах, то вводим фиктивную базу с запасом груза, равным (200+175+225+200) –(80+120+100+130)=370. Построим начальную распределительную таблицу.

Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен 4

Для этого элемента запасы равны 200, потребности 80. Поскольку минимальным является 80, то вычитаем его.

x₁₁ = min(200,80) = 80.

	A1	A2	A3	A4	A5	a
B1	4[80]	2[120]	5	6	0	200
B2	3	1	4[100]	2[75]	0	175
B3	6	8	7	3[55]	0[170]	225
B4	2	7	5	9	0[200]	200
b	80	120	100	130	370

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

F(x) = 4*80 + 2*120 + 4*100 + 2*75 + 3*55 + 0*170 + 0*200 = 1275

Искомый элемент равен 2 .Для этого элемента запасы равны 200, потребности 120.

	A1	A2	A3	A4	A5	a
B1	4[80]	2[120]	5	6	0	200
B2	3	1	4[100]	2[75]	0	175
B3	6	8	7	3[55]	0[170]	225
B4	2	7	5	9	0[200]	200
b	80	120	100	130	370

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

F(x) = 4*80 + 2*120 + 4*100 + 2*75 + 3*55 + 0*170 + 0*200 = 1275

Искомый элемент равен 5 .Для этого элемента запасы равны 200, потребности 100

	A1	A2	A3	A4	A5	Ai
B1	4[80]	2[20]	5[100]	6	0	200
B2	3	1[100]	4	2[75]	0	175
B3	6	8	7	3[55]	0[170]	225
B4	2	7	5	9	0[200]	200
bj	80	120	100	130	370

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

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 4*80 + 2*20 + 5*100 + 1*100 + 2*75 + 3*55 + 0*170 + 0*200 = 1275

Из 1-го склада необходимо весь груз направить в 3-й магазин

Из 2-го склада необходимо весь груз направить в 1-й магазин

Из 3-го склада необходимо груз направить в 1-й магазин (80), в 2-й магазин (50), в 3-й магазин (95)

Из 4-го склада необходимо груз направить в 2-й магазин (70), в 4-й магазин (130)

На 1-ом складе остался невостребованным груз в количестве 195 ед.

Оптимальный план является вырожденным, так как базисная переменная x₁₅=0.

На 2-ом складе остался невостребованным груз в количестве 175 ед.

Оптимальный план является вырожденным, так как базисная переменная x₂₅=0.

Задача имеет множество оптимальных планов, поскольку оценка для (1;1) равна 0.

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

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

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

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

	A1	A2	A3	A4	A5	Ai
B1	4	2	5[100]	6	0[100]	200
B2	3	1[120]	4	2[55]	0	175
B3	6	8	7	3[75]	0[150]	225
B4	2[80]	7	5	9	0[120]	200
bj	80	120	100	130	370

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

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 5*100 + 0*100 + 1*120 + 2*55 + 3*75 + 0*150 + 2*80 + 0*120 = 1115