Контрольная работа по предмету "Экономико-математическое моделирование"

Автор работы: Пользователь скрыл имя, 11 Марта 2014 в 22:52, контрольная работа

Описание работы

Задача № 1
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решить задачу на максимум, и почему?
Условие задачи:
Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.
Питательное вещество (витамин) Необходимый минимум питательных веществ Число единиц питательных
Веществ
в 1 кг корма
I II

9 3 1

8 1 2

12 1 6
Стоимость 1 кг корма I и II соответственно равна 4 и 6 ед.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание питательных веществ каждого вида было бы не менее установленного предела.
Задача № 2
Для изготовления двух видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице 24.
Таблица 24 – Исходные данные к задаче
Тип сырья Нормы расхода сырья на одно изделие, ед. Запасы сырья, ед.
А Б
I 1 2 11
II 2 1 5
III 1 3 14
Прибыль изделия, ден. ед. 4 2 Х
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.

Содержание работы

1 Условные обозначения, применяемые при моделировании 3
2 Задача № 1 9
3 Задача № 2 12
4 Задача № 3 17
Список используемой литературы 28

Файлы: 1 файл

Metody_optim_resheny_8_variant.doc

— 400.00 Кб (Скачать файл)

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

,                


;         

 

,

(ден. ед.)

Т.о. оптимальное решение найдено. Минимум расходов 26 ден. ед. достигается при использовании 2 единиц I вида корма и 3 единиц II вида питательных веществ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Задача № 2

 

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

 

Таблица 24 – Исходные данные к задаче

Тип сырья

Нормы расхода сырья на одно изделие, ед.

Запасы сырья, ед.

А

Б

I

1

2

11

II

2

1

5

III

1

3

14

Прибыль изделия, ден. ед.

4

2

Х


 

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

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

x1 + 2x2≤11

2x1 + x2≤5

x1 + 3x2≤14

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 

1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 11

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

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

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

 

 

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

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

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

x3, x4, x5,

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

X1 = (0,0,11,5,14)

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

 

Базис

B

x1

x2

x3

x4

x5

x3

11

1

2

1

0

0

x4

5

2

1

0

1

0

x5

14

1

3

0

0

1

F(X0)

0

-4

-2

0

0

0


 

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

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai1

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

min (11 : 1 , 5 : 2 , 14 : 1 ) = 21/2

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

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

 

Базис

B

x1

x2

x3

x4

x5

min

x3

11

1

2

1

0

0

11

x4

5

2

1

0

1

0

21/2

x5

14

1

3

0

0

1

14

F(X1)

0

-4

-2

0

0

0

0


 

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

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

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

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

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

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

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

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

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

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

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

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

 

B

x 1

x 2

x 3

x 4

x 5

11-(5 • 1):2

1-(2 • 1):2

2-(1 • 1):2

1-(0 • 1):2

0-(1 • 1):2

0-(0 • 1):2

5 : 2

2 : 2

1 : 2

0 : 2

1 : 2

0 : 2

14-(5 • 1):2

1-(2 • 1):2

3-(1 • 1):2

0-(0 • 1):2

0-(1 • 1):2

1-(0 • 1):2

0-(5 • -4):2

-4-(2 • -4):2

-2-(1 • -4):2

0-(0 • -4):2

0-(1 • -4):2

0-(0 • -4):2


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

 

Базис

B

x1

x2

x3

x4

x5

x3

81/2

0

11/2

1

-1/2

0

x1

21/2

1

1/2

0

1/2

0

x5

111/2

0

21/2

0

-1/2

1

F(X1)

10

0

0

0

2

0


 

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

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

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

 

Базис

B

x1

x2

x3

x4

x5

x3

81/2

0

11/2

1

-1/2

0

x1

21/2

1

1/2

0

1/2

0

x5

111/2

0

21/2

0

-1/2

1

F(X2)

10

0

0

0

2

0


 

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

x1 = 21/2

F(X) = 4•21/2 = 10

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 81/2

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 111/2

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

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

Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x3), выполнив соответствующие этапы алгоритма.

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

 

Базис

B

x1

x2

x3

x4

x5

x2

52/3

0

1

2/3

-1/3

0

x1

-1/3

1

0

-1/3

2/3

0

x5

-22/3

0

0

-12/3

1/3

1

F(X )

10

0

0

0

2

0


 

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

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

Информация о работе Контрольная работа по предмету "Экономико-математическое моделирование"