Исследование математических операций 2 (стр. 11 из 28)

Задача 2.18

На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице:

Ресурсы	Затраты ресурсов на единицу изделия				Запасы ресурсов, ед.
	I	II	III	IV
энергия	2	3	1	2	30
материалы	4	2	1	2	40
труд	1	2	3	1	25

Спланируйте производство так, чтобы прибыль от их реализации была наибольшей.

Задача 2.19

При изготовлении изделий П₁ и П₂ используются сталь и цветные металлы, а также токарные и фрезерные станки. По технологическим нормам на производство единицы изделия П₁ требуется 300 и 200 станко-часов соответственно токарного и фрезерного оборудования, а также 10 и 20 кг соответственно стали и цветных металлов. Для производства единицы изделия П₂ требуется 400, 100, 70 и 50 соответствующих единиц тех же ресурсов.

Цех располагает 12400 и 6800 станко-часами соответственно токарного и фрезерного оборудования и 640 и 840 кг соответственно стали и цветных металлов. Прибыль от реализации единицы изделия П₁ составляет 6 руб. и от единицы изделия П₂ – 16 руб.

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

Задача 2.20

Ежедневно в ресторане фирменный коктейль (порция составляет 0,33 л) заказывают в среднем 600 человек. Предполагается, что в ближайшее время их количество увеличится в среднем на 50 человек. Согласно рецепту в составе коктейля должно быть:

 не менее 20%, но и не более 35% спирта;

 не менее 2% сахара;

 не более 5% примесей;

 не более 76% воды;

 не менее 7% и не более 12% сока.

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

Процентный состав и запасы напитков

Напиток	Спирт	Вода	Сахар	Примеси	Количество, л/сут.
Водка	40%	57%	1%	2%	50
Вино	18%	67%	9%	6%	184
Сок	0%	88%	8%	4%	46

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

Решите задачи линейного программирования (2.21 – 2.36) графическим методом, проведите анализ на чувствительность.

Во всех задачах

,

Задачи линейного программирования (2.37 – 90) решите симплекс-методом и проведите анализ моделей на чувствительность.

Назад | Содержание | Далее

3. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым.

Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Назад | Содержание | Далее

3.1. Постановка задачи

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

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

 прикрепление потребителей ресурса к производителям;

 привязка пунктов отправления к пунктам назначения;

 взаимная привязка грузопотоков прямого и обратного направлений;

 отдельные задачи оптимальной загрузки промышленного оборудования;

 оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a₁, a₂ ,...,a_m . Известна потребность в грузах b₁, b₂ ,...,b_n по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij ,

. Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) x_ij с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл. 3.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта a_i ), а столбцы — пунктам назначения (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значение объема перевозимого груза для данных пунктов.

Таблица 3.1

Исходные данные

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

равен суммарному объему потребности в этих грузах по пунктам назначения

:

(3.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

(3.2)

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

Все грузы из i-х пунктов должны быть отправлены, т.е.:

,

(3.3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

,

(3.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных:

,

,

. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):