Общая постановка задач линейного программирования

 

Линейное программирование – это раздел математики ориентируемый на нахождении экстремума в задачах, которые описываются линейными уравнениями.

 

Задачей линейного программирования называется задачей исследования операций, математическая модель которой имеет вид:

 

F(x) = c_jx_j=c₁x₁+c₂x₂+…+c_nx_n → min (max) (2)

 

Целевая функция (2) - линейная форма.

 

a_ijx_j ≤ b_j (или ≥b), i = = 1,2…m (3)

или

(4)

 

Все переменные должны быть x_j ≥ 0, j =

Система (4) - система ограничений задачи линейного программирования (ЗЛП).

Если математическая модель ЗЛП имеет вид:

 

(5)

 

x_j ≥ 0, b_i ≥ 0, то ЗЛП представлена в канонической форме.

 

 

2.3.2 Построение математических моделей задач линейного программирования

 

Рассмотрим процесс построения математических моделей ЗЛП на примерах.

 

Пример 1 - Задача о диете

 

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

Рассмотрим простую математическую модель этой задачи.

Пусть имеются два вида продуктов, П1 и П2, содержащих питательные вещества А, В, С. Известно, сколько питательных веществ того или иного вида содержится в 1 кг пищи П1 или П2; эти сведения указаны в таблице 2.

 

Таблица 2 – Условие задачи о диете

 

	А	В	С
в 1 кг П1	а1	b1	c1
в 1 кг П2	a2	b2	c2

 

Кроме этих данных, нам известны; a, b, c – ежесуточная потребность организма в А, В, С (соответственно) и s1 и s2 – стоимость 1 кг пищи П1, П2 (соответственно).

Требуется рассчитать количество х1 продукта П1 и количество х2 продукта П2 так, чтобы обеспечить необходимое количество питательных веществ при минимальных затратах на пищу.

Очевидно, общая стоимость пищи будет S = s₁x₁ + s₂x₂.

Общее количество вещества А в обоих видах пищи равно a1x1 + a2x2. Оно должно быть не меньше а: a1x1 + a2x2³ a.

Аналогичные неравенства должны выполняться для Ви С: b1x1 + b₂x₂ ³ b, c1x1+ с₂х₂ ³ с.

 

Таким образом, приходим к следующей задаче.

Дана система трех линейных неравенств с двумя неизвестными х1, х₂и линейная функция S = s₁x₁ + s₂x₂ (6).

 

 

а1х1 + а2х2 ³ а

b1x1 + b2x2 ³ b (6)

c1x1 + c2x2 ³ c

 

Требуется среди неотрицательных решений (х1, х₂)системы (6) выбрать такое, при котором функция S, достигает наименьшего значения (минимизируется).

 

Пример 2 - Задача о распределения ресурсов

 

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

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

 

Пусть предприятие имеет 3 вида ресурсов: R₁, R₂, R₃ в количестве b₁, b₂, b₃ единиц соответственно (таблица 3). Предприятие выпускает товары 2 видов: Т₁ и Т₂. Известно, что а_ij – количество единиц ресурса R_i, используемого для выпуска 1 единицы товара T_j и с₁, с₂ – доход от 1 единицы товара Т₁ и Т₂. При этих условиях требуется выпустить количество товаров Т₁ и Т₂, чтобы доход был максимальным.

 

Таблица 3 – Условие задачи о распределении ресурсов

 

Ресурсы	Товары	Кол-во
	T1	T2	ресурсов
R1	а11	а12	b1
R2	а21	а22	b2
R3	а31	а32	b3

 

Обозначим: x₁ – количество товара T₁; x₂ – количество товара T₂ x₁ ≥ 0, x₂ ≥ 0

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

Из условия задачи составим систему ограничений (7).

 

(7)

 

Составим линейную форму: F(x) = с₁x₁ + с₂x₂ → max

Требуется среди неотрицательных решений (х₁, х₂)системы (7) выбрать такое, при котором функция F, достигает наибольшего значения (максимизируется).

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

 

Пример 3 - Транспортная задача

 

Уголь, до­бываемый в нескольких месторождениях, отправляет­ся ряду потребителей: заводам, электростанциям и т. п. Известно, сколько угля добывается в каждом из месторождений, скажем, за месяц, и сколько его требуется на тот же срок любому из потребителей. Известны расстояния между месторождениями и по­требителями, а также условия сообщения между ними; учитывая эти данные, можно подсчитать, во что обходится перевозка каждой тонны угля из лю­бого месторождения в любой пункт потребления. Тре­буется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были ми­нимальными.

Примем, что имеются лишь два месторождения М₁ М₂ и три потребителя П₁ П₂, П₃. Количества угля в М₁ и М₂равны соответственно a₁ и а₂; потребности пунктов П1 П₂, П₃пусть будут соот­ветственно b1, b₂, b3 - Будем считать, что суммарные запасы равны суммарным потребностям: a1+ а₂ = b1+b₂+ b_3.Наконец, заданы числа С_ij(i = 1, 2; j= 1, 2, 3) - стоимости перевозки тонны угля из М_iв П_jЗадача состоит в на­хождении шести чисел x₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃, где х_ij-количество угля, предназначенное к от­правке из М_i в П_j. Для удобства обозрения составим таблицу 4.

 

Таблица 4 – Транспортная задача

 

	в П1	в П2	в П3	Всего отправлено
Из M1	X11	X12	X13	а1
Из М2	X21	X22	X23	а2
Всего привезено	b1	b2	b3

 

 

Общее количество угля, вывезенное из М1должно равняться а1;отсюда имеем условие x11+ x12+ x13= a1

Аналогичное условие должно выполняться для М₂: x21+ x_{22 +} x₂₃= a2.

Общее количество угля, привезенное в П1должно равняться b1; отсюда x11+ x21= b1. Аналогично получаем условия: x12+ x22= b2, x13+ x23= b3.

Предполагаем, что стоимость перевозки прямо про­порциональна количеству перевозимого угля, т.е. пе­ревозка из M_iв П_jстоит c_ij∙х_ij. Тогда общая стоимость всех перевозок будетS=c₁₁x₁₁+c₁₂x₁₂+c₁₃x₁₃+c₂₁x₂₁+c₂₂x₂₂+c₂₃x₂₃

Таким образом, приходим к следующей задаче.

Дана система (8)

 

x11 + x12 + x13 = a1,

x21 + x22 + x23 = a2, (8)

x11 + x21 = b1,

x12 + x22 = b2,

x13 + x23 = b3.

 

и линейная функция S=c₁₁x₁₁+c₁₂x₁₂+c₁₃x₁₃+c₂₁x₂₁+c₂₂x₂₂+c₂₃x₂₃. Требуется среди неотрицательных решений x11, x12, x13, x21, x22, x23 системы (8) выбрать такое, при котором функция S достигает наименьшего значения (минимизируется).

 

2.3.3 Графическое решение задач линейного программирования

 

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

F = c₁x₁ + c₂x₂ → max (min)

 

(9)

 

x₁ ≥ 0, x₂ ≥ 0

 

Алгоритм графического способа решения задач линейного программирования заключается:

1) Построить прямые уравнения, которые получаются в результате замены в ограничения знаков неравенств на знаки равенств;

2) Найти полуплоскости, определяемые каждым из ограничений задачи;

3) Определить многоугольник решений;

4) Построить вектор = (c₁;c₂) – вектор градиент;

5) Построить прямую F = c₁x₁ + c₂x₂ = 0, проходящую через начало координат и перпендикулярную вектору ;

6) Передвигать прямую F в направлении вектора , в результате чего либо находят точку, в которой целевая функция принимает экстремум (максимум или минимум), либо устанавливают неограниченность функции на множестве планов;

7) Определить координаты точки экстремума функции и вычислить значение целевой функции в этой точки.

Пример: Предприятие изготавливает два вида продукции – П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья – А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице 5.

 

Таблица 5 - Расход сырья продукции

 

Сырье	Расход сырья на 1 ед. продукции	Запас сырья, ед.
П1	П2
А В

 

Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П2 более чем на 1 ед. кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки.

Оптовые цены единицы продукции равны: 3д.е. – для П1 4 д.е. для П2.

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

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

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

2х1 + 3х2 £ 9;

3х1 + 2х2 £ 13;

х1 – х2 £ 1;

х2 £ 2;

х1 £ 0; х2 £ 0.

Доход от реализации х1 единиц продукции П1 и х2 продукции П₂ составит F = 3x1 + 4x2.

Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение Fmax.

Найдем решение данной задачи графическим способом.

Построим многоугольник решений. Для этого в системе координат Х1 0 Х2 на плоскости изобразим граничные прямые:

 

2х1 + 3х2 = 9 (L1);

3х1 + 2х2 = 13 (L2);

х1 – х2 = 1 (L3);

х2 = 2 (L4).

 

Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рисунке показаны стрелками. Областью решений являются многоугольник ОАВСD.

Для построения прямой Z = 3х1 + 4х2 = 0 строим вектор-градиент

С = (3;4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направление вектора С. Из рисунка 9 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L1 и L3. для определения ее координат решим систему уравнений:

2х1 + 3х2 = 9;

х1 – х2 = 1.

 

Оптимальный план задачи х1 = 2,4; х2 = 1,4. подставляя значения х1 и х2 в линейную функцию, получим:

 

Zmax = 3 * 2,4 + 4 * 1,4 = 12,8.

 

Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. доход, получаемый в этом случае, составит: Z = 12,8 д.е.

 

 

 

 

 

Рисунок 5 – Геометрическая интерпретация решения задач линейного программирования

 

Свойства задач линейного программирования

 

При нахождении решения ЗЛП графическим способом могут встретиться следующие случаи (рисунки 6-9):

 

y

 

 

1 F_max

 

0 1 F_min x

F=0

 

Рисунок 6 – Единственное решение ЗЛП

 

 

y

 

A

 

1 B

x

0 1 F_min

 

Рисунок 7 - Бесчисленное множество решений ЗЛП

(любая точка отрезка АВ)

 

y

 

1 F_max→

 

0 1 F_min x

F=0

 

Рисунок 8 – ЗЛП не имеет максимальное решение

 

y

 

 

1

 

0 1 x

 

Рисунок 9 – ЗЛП не имеет многоугольника решений

 

 

Задания для лабораторной работы 2

Задание №1

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

 

Вариант 1

Автотранспортному предприятию (АТП) необходимо освободить из-под груза складские помещения клиента. Вывоз груза следует осуществить в два рейса колоннами автомобилей. Условия перевозки требуют, чтобы в составе каждой колонны, предназна­ченной для вывоза груза в первый район, было 8 автомобилей ЗИЛ-131 и 8 автомобилей ЗИЛ-130; в колоннах второго рейса 8 автомобилей ЗИЛ-130 и 16 — МАЗ-500. Каждая из колонн может сде­лать за сутки одинаковое количество поездок. Парк подвижного состава АТП состоит из 32 автомобилей ЗИЛ-131 грузоподъемнос­тью 3 т, 48 автомобилей ЗИЛ-130 грузоподъем-ностью 4 т, 48 авто­мобилей МАЗ-500 грузоподъемностью 7,5 т.

Определите количество колонн, которое нужно направить в каждый район, чтобы перевезти наибольшее количество груза.

 

Вариант 2

Четыре овощехранилища каждый день обеспечивают кар­тофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. Тарифы (в д.е. за 1 т) указаны в следующей таблице 6.

 

Таблица 6 – Условие задачи варианта 2

 

Овощехранилища	Магазины

 

Составьте план перевозок, минимизирующий суммарные транспортные расходы.

 

Вариант 3

Имеются два склада готовой продукции: А₁ и А₂ с запаса-
ми однородного груза 200 и 300 т. Этот груз необходимо достав
трем потребителям: В₁, В₂ и В₃ в количестве 100, 150, 250 т соот-
ветственно. Стоимость перевозки 1 т груза из склада А₁ потреби-телям В₁, В₂ и В₃ равна 5, 3, 6 д.е., а из склада А₂ тем же потребителям — 3, 4, 2 д.е. соответственно.

Составьте план перевозок, минимизирующий суммарные транспортные расходы.

 

Вариант 4

При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице 7.

 

Таблица 7 – Условие задачи варианта 4

 

Питательные вещества	Количество единиц питательных веществ на 1 кг
	Корма 1	Корма 2
Белки Углеводы Протеин

 

Стоимость 1 кг корма первого вида - 4 д.е., второго - 6 д.е.

Составьте дневной рацион питательности, имеющий минимальную стоимость.

 

Варианта 5

Хозяйство располагает следующими ресурсами: площадь 100 ед., труд - 120 ед., тяга - 80 ед. Хозяйство производит четыре вида продукции П₁, П₂, П₃, П₄. Организация производства харак- теризуется следующей таблицей 8.

 

Таблица 8 – Условие задачи варианта 5

 

Продукция	Затраты на 1 ед. продукции	Доход от единицы продукции
	площадь	труд	тяга
П1 П2 П, П4

 

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

 

Вариант 6

Цех выпускает трансформаторы двух видов. Для изготовле- ния трансформаторов обоих видов используются железо и проволока. Общий запас железа - 3 т, проволоки - 18 т. На один транс­форматор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д. е., второго - 4 д. е.

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

 

Вариант 7

Совхоз отвел три земельных массива размером 5000, 8000, 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице 9.

 

Таблица 9 – Условие задачи варианта 7

 

Посевы	Массивы
	I	II	III
Рожь Пшеница Кукуруза

 

За 1 ц ржи совхоз получает 2 д. е., за 1 ц пшеницы - 2,8 д. е., за I ц кукурузы — 1,4 д. е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить макси­мальную выручку, если по плану он обязан сдать не менее 1900 т ржи, 158 000 т пшеницы и 30 000 т кукурузы?

 

Вариант 8

Из трех продуктов - I, II, III составляется смесь. В ее смеси должно входить не менее 6 ед. химического вещества А, 8 ед. вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице 10.

 

Таблица 10 – Условие задачи варианта 8

 

Продукт	Содержание химического вещества в 1 ед. продукции	Стоимость 1 ед.
	А	В	С	продукции
I II III		1,5		2,5

Составьте наиболее дешевую смесь.

 

 

Вариан 9

В институте проводится конкурс на лучшую стенгазету. Одному студенту дано следующее поручение:

• купить акварельной краски по цене 30 д. е. за коробку, цветные карандаши по цене 20 д. е. за коробку, линейки по цене 12 д.е. блокноты по цене 10

д. е.;

• красок нужно купить не менее трех коробок, блокнотов - столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д. е.

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

 

Вариант 10

Цех выпускает три вида деталей - А, В, С. Каждая деталь обрабатывается тремя станками. Организация производства в цехе характеризуется следующей таблицей 11.

 

Таблица 11 – Условие задачи варианта 10

 

Станок	Длительность обработки детали, мин.	Фонд времени,
	А	В	С	час
I
II
III
Отпускная цена
за одну деталь

 

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

 

Вариант 11

Предприятие должно выпускать два вида продукции — А и В, используя при этом последовательно четыре станка. Данные о технологическом процессе указаны в следующей таблице 12.

 

Таблица 12 – Условие задачи варианта 11

 

Станок	Трудоемкость на 1 ед. продукции	Фонд времени, час.
	А	В
Прибыль на 1 ед. продукции (д. е.)

 

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

 

Вариант 12

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

 

Таблица 13 – Условие задачи варианта 12

 

Ресурсы	Расход материалов на производство одной запасной части, кг	Запас кг
I II III Прибыль от реализации одной запасной части (д. е.)	-	-

 

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

 

Вариант 13

Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л. алкилата, 250 тыс. л. крекинг-бензина, 350 тыс. л. бензина прямой перегонки и 100 тыс. л. изопентона. В результате смешивания этих четырех компонентов в разных пропорциях обра­зуется три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л. указанных сортов бензина характеризуется числами 120 д. е., 100 д. е., 150 д. е.

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

 

Вариант 14

Планируется нанесение удара по некоторому объекту тремя различными видами оружия: оружием А -в течение 3 мин., оружи­ем Б - в течение 5 мин., оружием В - в течение 4 мин. Возможно­сти средств обеспечения стрельбы таковы, что при применении ору­жия А в течение 3 мин., оружия Б в течение 2 мин., оружия В в те­чение 4 мин. общее количество залпов не должно превышать 15. При применении оружия А в течение 2 мин. и оружия В в течение 3 мин. общее количество залпов не должно превышать 8 ед. Кроме то­го, для преодоления противодействия противника необходимо, что­бы количество залпов оружием В за 1 мин. было больше, чем 5 ед.

Рассчитайте темп стрельбы (количество залпов в 1 мин.) всеми
видами оружия, при котором общее количество залпов в ударе будет наибольшим.

 

Вариант 15

Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по бегу, прыжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину — 8 спорт­сменов, а в прыжках в высоту - не более 10. Количество очков, га­рантируемых спортсмену каждого разряда по каждому виду, указа­но в следующей таблице 14.

 

Таблица 14 – Условие задачи варианта 15

 

Разряд	Бег	Прыжки в высоту	Прыжки в длину
I II

 

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

 

Вариант 16

Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть
либо две лисы, либо 1 песец. По плану на ферме должно быть не
менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма - 4 ед., а каждому песцу - 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца — 5 д. е.

Какое количество лисиц и песцов нужно держать на ферме чтобы получить наибольшую прибыль?

Вариант 17

Имеются два элеватора, в которых сосредоточено ответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 т каждому. Расстояние от элеватора до хлебозаводов указано в следующей таблице 15.

 

Таблица 15 – Условие задачи варианта 17

 

Элеваторы	Хлебозаводы

Затраты на перевозку 1 т продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транс­портных расходов.

 

Вариант 18

Из двух сортов бензина образуются две смеси — А и В.
Смесь А содержит бензина 60% 1-го сорта и 40% 2-го сорта; смесь
В — 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А — 10 д.е., а
смеси В — 12 д.е.

Составьте план образования смесей, при котором будет полу­чен максимальный доход, если в наличии имеется бензина 50 т 1-го сорта и 30 т 2-го сорта.

 

Вариант 19

Имеются две почвенно-климатические зоны, площади ко­торых соответственно равны 0,8 и 0,6 млн. га. Данные об урожай­ности зерновых культур приведены в следующей таблице 16.

 

Таблица 16 – Условие задачи варианта 19

 

Зерновые культуры	Урожайность (ц/га)	Стоимость 1 ц, д. е.
	1-я зона	2-я зона
Озимые Яровые

 

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

 

Вариант 20

Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90 и 40 ведер воды. Участки сада требуют для полива соответственно 100, 120 и 90 ведер воды. Расстояния (в метрах) от колодцев до участков сада указаны в следующей таблице 17.

 

Таблица 17 – Условие задачи варианта 20

 

Колодцы	Участки
сливы	яблони	Груши

 

Как лучше организовать полив?

 

Вариант 21

Предприятие производит сборку автомашин двух марок: А₁ и А₂. Для этого требуются следующие материалы: S_1- комплекты заготовок металлоконструкций в коли­честве b₁=17 шт., необходимые для сборки автомашин марок A₁ и А₂ (соответственно 2 и 3 ед.); S₂ - комплекты резиновых изделий в количестве b₂ = 11 шт. (соответст­венно 2 и 1 ед:); S₃ -двигатели с арматурой и электро­оборудованием в количестве b₃ = 6 комплектов, необходимых по одному для каждой автомашины марки А₁; S₄ - двигатели с арматурой и электрооборудованием в количестве b₄ = 5 комплектов, необходимых по одному для каждой автомашины марки А₁ Стоимость автомаши­ны марки A₁ - с₁ = 7 тыс. ден. ед., а автомашины А₂ - с₂ = 5 тыс. ден. ед. Определить план выпуска, обеспечивающий предприятию максимальную выручку.

 

Вариант 22

Для сохранения нормальной жизнедеятельнос­ти человек должен в сутки потреблять белков не менее 120 усл. ед., жиров не менее 70 и витаминов не менее 10 усл. ед. Содержание их в продуктах П₁ и П₂ равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1). Стоимость 1 ед. продукта П₁ - 2 ден. ед., П₂ - 3 ден. ёд. Требуется так организовать питание, чтобы его стоимость была ми­нимальной, а организм получил необходимое количество питательных веществ.

 

Вариант 23

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

таблице 18.

 

 

Таблица 18 – Условие задачи варианта 23

 

Изделия	Нормы расхода сырья на одно изделие	Стоимость ед. изделия, руб.
	Томаты, кг	Специи, кг	Эл. энергия, кВт-ч
Томаты неочищенные	2,1	0,09
Томаты маринованные	2,3	0,07
Томатная паста	3,2	0,7
Запасы сырья

 

Вариант 24

Кондитерская фабрика на одной поточной линии может выпускать четыре вида шоколадных конфет. Определить план выпуска каждого сорта конфет и обеспечить наибольший экономический эффект. Данные приведены в таблице 19.

 

Таблица 19 – Условие задачи варианта 24

 

Сорт конфет	Нормы расхода сырья на производство 1 кг конфет, кг	Цена 1 кг, руб.
	Шоколад	Сахар	Вафли	Фундук	Крахмал
Мишка на севере	0,2	0,4	0,1	-	0,3
Белочка	0,1	0,5	—	0,3	0,1
Трюфели	0,65	0,3	—	—	0,05
Юбилейные	0,15	0,4	—	—	0,45
Запасы сырья, кг

 

Вариант 25

Швейная фабрика выпускает мужские костюмы четырех ар­тикулов. Составить план выпуска костюмов и минимизировать за­траты на их изготовление по данным, приведенным в таблице 20.

 

Таблица 20 – Условие задачи варианта 25

 

Артикул кос­тюма	Трудоемкость, ч	Эл. энергия, кВт-ч	Тепл. энергия, ккал	Себестои­мость од­ного кос­тюма, руб.
	закрой­щика	швеи	Контро ­лера
	3,5		0,5	11,2
	2,5			8,2
	4,2	5,5	1,2
		4,5	0,8	10,2
Нормы затрат

 

 

Задание №2

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

Во всех задачах x₁ ≥ 0, х₂ ≥ 0.

 

Вариант 1 Вариант 2

W = 2х₁ - 5х₂ → min; W = х₁ - 4х₂ → min;

3х₁ + 4х₂ ≤ 6 3х₁+ 5х₂ ≥ 8

2х₁ + 3х₂ ≤ 4 -3х₁+ 10х₂ ≤ 16

 

Вариант 3 Вариант 4

F = х₁ + x₂ → max; W = 2x₁ + 2x₂ → min;

х₁ + 3х₂ ≤ 30 x₁ + x₂ ≥ 1

2х₁ + х₂ ≤ 20 -x₁ + x₂ ≤ 1

 

Вариант 5 Вариант 6

F = 2x₁ + 3х₂ → max W = x₁ – 3x₂ → min;

х₁ ≥ 4 x₁ + x₂ ≤ 3

х₂ ≥ 3 - х₁ + 2х₂ ≤ 5

х₁ + х₂ ≤ 8

 

Вариант 7 Вариант 8

W = x₁ - 3x₂ → min; W = 2x₁ + 5x₁ → max;

-x₁ + 2x₂ ≤ 6 x₁ + x₂ ≤ 500

x₁ + 2x₂ ≤ 5 x₁ ≤ 400

x₂ ≤ 300

 

 

Вариант 9 Вариант 10

W = x₁ + 4x₂ → max; W = 2x₁ + x₂ → max;

x₁ + x₂ ≤ 7 2x₁ + 6x₂ ≤ 15

x₁ ≤ 3 4x₁ + 3x₂ ≤ 11

x₂ ≤ 1

 

Вариант 11 Вариант 12

W = 2x₁ + 2x₂ → min; W = 3x₁ + 2x₂ → max;

x₁ + x₂ ≥ 4 x₁ ≥ 1

-x₁ + 2x₂ ≤ 8 x₂ ≥ 0.6

0.1x₁ + 0.4x₂ ≤ 2

 

Вариант 13 Вариант 14

W = x₁ + x₂ → max; W = 5x₁ + x₂ → max;

3x₁ + x₂ ≤ 20 3x₁ + 6x₂ ≤ 11

2x₁ + 3x₂ ≤ 30 x₁ ≤ 2.75

3x₂ ≤ 1.1

 

Вариант 15 Вариант 16

W = 2x₁ + 7x₂ → max; W = x₁ – 2x₂ → min;

x₁ ≥ 3 x₁ + 10x₂ ≤ 1

x₂ ≥ 4 -2x₁ + 24x₂ ≤ 1

2x₁ + 2x₂ ≤ 9

 

Вариант 17 Вариант 18

W = x₁ + 3x₂ → max; W = 2x₁ + 4x₂ → max;

4x₁ + 8x₂ ≤ 17 4x₁ + x₂ ≤ 15

x₁ ≤ 3 x₁ + 6x₂ ≤7

x₂ ≤ 2

 

Вариант 19 Вариант 20

W = 2x₁ + 3x₂ → min; W = 4x₁ + 6x₂ → max;

5x₁ + 2x₂ ≥ 3 x₁ + 15x₂ ≤ 32

-4x₁ + 6x₂ ≤ 2 x₁ ≤ 31

x₂ ≤ 2

 

Вариант 21 Вариант 22

W = 4x₁ – x₂ → min; W = 2x₁ + x₂ → min;

4x₁ + 6x₂ ≤ 9 5x₁ + 3x₂ ≥ 7

-5x₁ + 8x₂ ≤ 4 -2x₁ + 9x₂ ≤21

 

Вариант 23 Вариант 24

W = x₁ + 5x₂ → max; W = 2x₁ + x₂ → min;

2x₁ + x₂ ≤ 8 5x₁ + 3x₂ ≥ 7

x₁ + 3x₂ ≤ 7 -2x₁ + 9x₂ ≤ 21

 

Вариант 25 Вариант 26

W = x₁ + 4x₂ → max; W = 3x₁ – 2x₂ → min;

x₁ ≥ 4 2x₁ + 5x₂ ≤ 8

x₂ ≥ 5 -3x₁ + 8x₂ ≤ 4

3x₁ + x₂ ≤ 16

 

2.5 Контрольные вопросы к защите лабораторной работы 2

 

1) Какие задачи относятся к задачам линейного программирования?

2) Что называется системой ограничения и целевой функцией задачи линейного программирования?