Контрольная работа по "Информатике"

Вариант 6.

Задание 1.

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

Решение:

Решим задачу максимизации. Областью решения линейного неравенства с двумя переменными является полуплоскость, лежащая по одну сторону от граничной прямой, а областью решения системы линейных неравенств – часть плоскости, ограниченная данными прямыми. Строим в прямоугольной системе координат прямые 5х₁-2х₂=4, -х₁+2х₂=4, х₁=4/3, х₁+х₂=4.

Находим область решения  данной системы:

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

 откуда А(1,33; 2,67). 

Определяем значение целевой функции:

L(А)=х₁+2х₂ = 1,33 + 2*2,67 = 6,7.

То есть и минимум функции, и максимум, равный 6,7, достигается в точке А(1,33; 2,7).

Ответ: 1) L_max = L_min = L(1,33; 2,67) = 6,7.

 

Задание 2.

Построить математическую модель задачи и решить ее средствами Excel. Записать сопряженную задачу. Провести анализ и сделать выводы по полученным результатам.

Чаеразвесочная фабрика  выпускает чай сорта А и  В, смешивая три ингредиента: индийский, грузинский и краснодарский чай. В таблице приведены нормы расхода ингредиентов и прибыль от реализации 1 т чая сорта А и В.

Ингредиенты	Норма расхода		Объем запасов
	А	В
Индийский чай	0,5	0,2	600
Грузинский чай	0,2	0,6	870
Краснодарский чай	0,3	0,2	430
Прибыль от реализации одной  тонны продукции	3200	2900

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

Решение:

Обозначим через х_1, х₂ – количество тонн чая видов А и В соответственно. Строим математическую модель:

L(x) = 3200x₁ + 2900x₂  - целевая функция

   - ограничения по индийскому чаю,

    - ограничения по грузинскому чаю,

    - ограничения по краснодарскому  чаю.

Имеем задачу линейного  программирования. Для решения задачи средствами Excel заполним следующую таблицу:

Ингредиенты	Норма расхода		Вычисленные значения	Соотношения	Ограничения
	А	В
Количество, Х
Индийский чай	0,5	0,2	0	<=	600
Грузинский чай	0,2	0,6	0	<=	870
Краснодарский чай	0,3	0,2	0	<=	430
Прибыль от реализации одной тонны  продукции	3200	2900	0

Применяем команду Сервис/Поиск решения:

Устанавливаем параметры:

и получаем результат:

Исходная таблица принимает  вид:

Ингредиенты	Норма расхода		Вычисленные значения	Соотношения	Ограничения
	А	В
Количество, Х	600	1250
Индийский чай	0,5	0,2	550	<=	600
Грузинский чай	0,2	0,6	870	<=	870
Краснодарский чай	0,3	0,2	430	<=	430
Прибыль от реализации одной тонны  продукции	3200	2900	5545000

То есть максимальную прибыль в 5545000 тыс. единиц предприятие получит, реализуя 600 т чая вида А и 1250 т чая В.

 

Задание №3.

Решить симплексным  методом одну из пары двойственных задач задания №2. Обосновать выбор  модели для применения симплексного метода. Записать ответы для обеих  задач. Провести анализ и сделать  выводы по полученным результатам.

 

Решение:

Имеем прямую задачу:

L(x) = 3200x₁ + 2900x₂  

 

  

Сопряженная задача имеет  вид:

Здесь у₁, у₂, у₃ – количество затраченного сырья, а целевая функция сводит к минимуму потребление ресурсов (в денежном выражении). То есть предприятию безразлично, производить ли продукцию по оптимальному плану и получить максимальную производительность, или продать ресурсы по оптимальным ценам, и возместить минимальные затраты на ресурсы.

В данном случае проще  решить прямую задачу, добавляем ослабляющие переменные и составляем первую симплексную таблицу:

L(x) = 3200x₁ + 2900x₂  

 

.  

	x1	x2	x3	x4	x5	Правая часть	Оценка
x3	0,5	0,2	1	0	0	600	3000
x4	0,2	0,6	0	1	0	870	1450
x5	0,3	0,2	0	0	1	430	2150
L	3200	2900

Критерий оптимальности  для задачи максимизации – отрицательность переменных нижней строки, опорное решение Х = (0, 0, 600, 870, 430) не оптимально. Разрешающий элемент – второй столбец, вторая строка, составим новую симплексную таблицу:

	x1	x2	x3	x4	x5	Правая часть	Оценка
x3	0,433333	0	1	-0,33333	0	310	715,3846
х2	0,333333	1	0	1,666667	0	1450	4350
x5	0,233333	0	0	-0,33333	1	140	600
L	2233,333	0	0	-4833,33	0	-4205000

Критерий оптимальности  для задачи максимизации – отрицательность  переменных нижней строки, опорное  решение Х = (0, 4350, 715, 0, 600) не оптимально. Разрешающий элемент – первый столбец, третья строка, составим новую симплексную таблицу:

 

	x1	x2	x3	x4	x5	Правая часть	Оценка
x3	0	0	1	0,285714	-1,8571	50
х2	0	1	0	2,142857	-1,428	1250
х1	1	0	0	-1,42857	4,2857	600
L	0	0	0	-1642,86	-9571,428	-5545000

Критерий оптимальности  выполнен, решение Х* = (600, 1250, 50, 0, 0) оптимально.

В данной задаче соответствие между переменными принимает  вид:

x1	x2	x3	x4	x5
↕	↕	↕	↕	↕
y4	y5	у1	у2	у3

На основании первой теоремы двойственности Z_min = L_max = 5545000. На основании второй теоремы двойственности оптимальное решение двойственной задачи У^* = (0, 0, 0, 1642, 9571).