Отыскание минимума линейной функции

Варианты задач для самостоятельного решения

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

Задача 1.

Зоомагазин готовит два набора корма для грызунов: «Зверюшки» и «Грызунчик». В набор корма «Зверюшки» входит 40 г фруктов, 40 г злаков и 20 г орехов, а в «Грызунчик» - 20 г фруктов, 50 г злаков и 30 г орехов. Прибыль от продажи 1 набора корма «Зверюшки» 5 ден. ед., а от продажи 1 набора корма «Грызунчик» – 4 ден. ед. Имеется 6 кг фруктов, 12 кг злаков и 8 кг орехов. Какое количество наборов каждого вида должен расфасовать магазин для получения наибольшей прибыли?

(Ответ: корм «Зверюшки» – 50 наборов, корм «Грызунчик» – 200 наборов, прибыль – 1050 ден.ед.)

Задача 2.

На швейной фабрике планируется выпуск двух видов костюмов: «Лайт» и «Классик». На костюм «Лайт» требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат; на костюм «Классик» – 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней. По плану предусматривается выпуск не менее 110 костюмов. Требуется определить оптимальное число костюмов каждого вида для получения максимальной прибыли, если прибыль от реализации костюма «Лайт» составляет 100 условных единиц, а от костюма «Классик» – 200 усл. единиц.

(Ответ: костюмы «Лайт» – 70, костюмы «Классик» – 80, прибыль – 23000).

Задача 3.

Для изготовления трех видов продукции (П1, П2, П3) используется три вида ресурсов (Р1, Р2, Р3). Все условия представлены в таблице 2. Определить план выпуска продукции, при котором прибыль от реализации будет максимальной.

Таблица 2. Исходные данные

Ресурсы	Запас ресурсов, ед.	Норма расхода ресурса на единицу продукции, ед.
	П1	П2	П3
Р1
Р2
Р3
Прибыль от реализации единицы продукции

(Ответ: 10 единиц продукции П1, 50 единиц продукции П2, продукцию П3 не выпускать, прибыль 130).

Задача 4.

Небольшая фирма производит два вида печатной продукции: плакаты и афиши. Для изготовления одного плаката требуется 3 условных листа бумаги, а для изготовления одной афиши 7 условных листов бумаги. На изготовление одного плаката уходит 2 часа рабочего времени, а на изготовление афиши 8 часов. Каждый плакат приносит 1 доллар прибыли, а каждая афиша - 3 доллара. Сколько плакатов и сколько афиш должна изготовить эта фирма, если она располагает 420 условными листами и 400 часами рабочего времени и хочет получить максимальную прибыль?

(Ответ: 56 плакатов, 36 афиш, прибыль 164 доллара).

Задача 5.

На ткацкой фабрике производится 4 вида ткани: шерстяная, джинсовая, ситцевая, льняная. По условиям производства ткань производится партиями. Величина партии, затраты времени и денежных ресурсов на изготовление одной партии для каждого вида ткани указаны в таблице 3.

Таблица 3. Исходные данные

Вид ткани	время (мин)	затраты (ден.ед.)	количество (м)
шерстяная
джинсовая
ситцевая
льняная

Сколько партий ткани каждого вида должна произвести фабрика в течение суток при условии непрерывного производства, чтобы общее количество ткани (в метрах) было максимальным, если ежедневно на приобретение ресурсов для производства тканей фабрика может потратить не более 12000 денежных единиц?

(Ответ: шерстяная – 120 партий, джинсовая – 8 партий, общее количество ткани – 6800 метров).

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

Критерий оптимальности полученного решения в этом случае можно сформулировать следующим образом:

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

Пример 2. В магазине продается два вида удобрений для комнатных растений: «Турбо» и «Форте», расфасованных в пакеты по 100 г. В 100 г удобрения «Турбо» содержится 8% азота, 15% фосфора и 18% калия, а в 100 г удобрения «Форте» – 6% азота, 3% фосфора и 7% калия удобрений. Известно, что для сбалансированного питания растений потребуется азота 26 г, фосфора 24 г, калия 32 г. Пакет удобрения «Турбо» стоит 18 руб., а пакет удобрения «Форте» 7 рублей. Определить количество пакетов удобрений (х₁ и х₂), которые нужно купить, чтобы обеспечить сбалансированного питание растений и минимизировать стоимость.

Решение. Построим математическую модель задачи. Найти значения переменных х₁, х₂, удовлетворяющие условиям:

(1.6)

при которых целевая функция принимает минимальное значение.

Решение будем проводить симплексным методом. Приведем систему к каноническому виду введением дополнительных переменных: ,

(1.7)

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

(1.8)

Полагая неосновные переменные равными нулю, получаем недопустимое первоначальное базисное решение: . Целевая функция на недопустимом решении не рассматривается!

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

Вычислим для нее оценочные отношения в уравнениях, соответствующих недопустимым решениям: 26/8, 24/15, 32/18. Если увеличить значение переменной х₁ до максимального из указанных значений (26/8), то значения переменных станут допустимыми. Новый базис: x₁, x₄, x₅. Система ограничений примет вид:

(1.9)

Полагая неосновные переменные равными нулю, получаем допустимое базисное решение: . Целевая функция принимает вид .

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

Вычислим оценочные отношения для переменной х₂ в тех уравнениях, где коэффициент при х₂ отрицателен: 13/3, 3, 53/13. Наименьшее из этих отношений (3) определяет разрешающее уравнение. Итак, в новый базис вместо переменной х₄ вводится переменная х₂. Выразим х₂ и подставим полученное выражение в остальные уравнения и в целевую функцию:

(1.10)

(1.11)

Полученное решение допустимое: . При этом целевая функция . Значение целевой функции не может быть уменьшено, так как все неосновные переменные входят в линейную целевую функцию с неотрицательными (положительными) коэффициентами. Следовательно, найденное решение является оптимальным.

Ответ: нужно купить 1 пакет удобрения «Турбо» и 3 пакета удобрения «Форте», стоимость покупки 36 рублей.

Дата добавления: 2015-06-27