- •Здійснення постановки задачі лінійного програмування
- •Завдання №4 Побудова подвійної задачі лінійного програмування та її розв’язок
- •Розв’язок транспортної задачі лінійного програмування
- •Завдання №6 Розв’язок задач дискретного програмування методом Гоморі та методом віток та границь
- •Завдання №7 Розв’язок задач дискретного програмування методом Мака та Угорським методом
- •Завдання №8,9 Розв’язок задач нелінійного програмування методом виключень, методом множників Лагранжа та градієнтних методів.
- •Розв’язок задач динамічного програмування
- •Прикдад виконання робіт Задание №1
- •Задание № 2,3
- •Задание №4
- •Задание №5 Задание: решить транспортную задачу линейного программирования методом потенциалов.
- •Задание №6
- •Задание № 7
- •Задание №8,9
- •Задание №10
Завдання №1.
Здійснення постановки задачі лінійного програмування
Завдання: побудувати математичну модель задачі лінійного програмування та визначити можливість розв’язку поданої задачі.
№ |
Задача |
|||||||||||||
1 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 40 т, проволоки 22 т. На один трансформатор первого вида расходуется 4 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуется 4 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 5 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
|||||||||||||
2 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль от реализации одной запчасти первого вида составляет 5 д.е., второго вида – 7 д.е., третьего вида – 8 д.е.
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
|||||||||||||
3 |
При откорме каждое животное должно получить не менее 9 ед.белков, 8 ед. углеводов и 11 ед.протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость. |
|||||||||||||
4 |
Хозяйство располагает следующими ресурсами: площадь 100 ед., труд 120 ед., тяга 80 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. |
|||||||||||||
5 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 3 т, проволоки 18 т. На один трансформатор первого вида расходуется 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуется 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
6 |
Из трех продуктов – І, ІІ, ІІІ составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
Составьте наиболее дешевую смесь. |
|||||||||||||
7 |
Цех віпускает три вида деталей – А, В, С. Каждая деталь обрабатівается тремя станками. Организация производства характеризуется следующей таблицею. Отпускная цена за одну деталь типа А – 30 д.е., типа В – 32 д.е., типа С – 30 д.е.
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли. |
|||||||||||||
8 |
Предприятие должно выпускать два вида продукции А и В, используя при этом последовательно четыре станка. Данные о технологическом процессе указаны в следующей таблице. Прибыль на 1 ед продукции типа А – 2 д.е., типа В – 3 д.е.
Составьте план выпуска продукции, обеспечивающий предприятию наибольшую прибыль. |
|||||||||||||
9 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль на 1 ед продукции первого типа – 5 д.е., второго типа – 8 д.е., третьего типа – 6 д.е.
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
|||||||||||||
10 |
Из двух сортов бензина образуются две смеси А и В. Смесь А содержит бензина 60% первого сорта и 40% второго сорта, смесь В содержит 80% бензина первого сорта и 20% второго сорта. Цена 1 кг смеси А 10 д.е., смеси В 12 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется 50 т бензина первого сорта и 30 т второго сорта. |
|||||||||||||
11 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 12 т, проволоки 17 т. На один трансформатор первого вида расходуется 5 кг железа и 6 кг проволоки, а на один трансформатор второго вида расходуется 3 кг железа и 4 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 6 д.е., второго – 4 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
12 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль от реализации одной запчасти первого типа 7 д.е., второго типа – 6 д.е., третьего типа – 6 д.е.
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
|||||||||||||
13 |
При откорме каждое животное должно получить не менее 9 ед.белков, 7 ед. углеводов и 10 ед.протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость. |
|||||||||||||
14 |
Хозяйство располагает следующими ресурсами: площадь 110 ед., труд 120 ед., тяга 90 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. |
|||||||||||||
15 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 5 т, проволоки 17 т. На один трансформатор первого вида расходуется 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуется 3 кг железа и 4 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 5 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
|||||||||||||
16 |
Из трех продуктов – І, ІІ, ІІІ составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 15 ед. вещества С. Структура химических веществ приведена в следующей таблице:
Составьте наиболее дешевую смесь. |
17 |
Цех віпускает три вида деталей – А, В, С. Каждая деталь обрабатівается тремя станками. Организация производства характеризуется следующей таблицею. Отпускная цена за одну деталь А – 35 д.е., В – 32 д.е., С – 33 д.е.
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли. |
|||||||||||||
18 |
Предприятие должно выпускать три вида продукции А,В,С, используя при этом последовательно четыре станка. Данные о технологическом процессе указаны в следующей таблице. Прибыль на 1 ед продукции А – 2 д.е., В – 3 д.е., С - 3 д.е.
Составьте план выпуска продукции, обеспечивающий предприятию наибольшую прибыль. |
|||||||||||||
19 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль на 1 ед продукции типа 1 – 5 д.е.,типа 2 – 8 д.е.,типа 3 - 6 д.е
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
|||||||||||||
20 |
Из двух сортов бензина образуются две смеси А и В. Смесь А содержит бензина 55% первого сорта и 45% второго сорта, смесь В содержит 70% бензина первого сорта и 30% второго сорта. Цена 1 кг смеси А 12 д.е., смеси В 10 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется 60 т бензина первого сорта и 35 т второго сорта. |
|||||||||||||
21 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 30 т, проволоки 18 т. На один трансформатор первого вида расходуется 7 кг железа и 5 кг проволоки, а на один трансформатор второго вида расходуется 6 кг железа и 4 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 5 д.е., второго – 4 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
|||||||||||||
22 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль на 1 ед продукции типа 1 – 4 д.е.,типа 2 – 8 д.е.,типа 3 - 6 д.е
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
23 |
При откорме каждое животное должно получить не менее 9 ед.белков, 12ед. углеводов и 11 ед.протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е. Составьте дневной рацион питательности, имеющий минимальную стоимость. |
|||||||||||||
24 |
Хозяйство располагает следующими ресурсами: площадь 105 ед., труд 140 ед., тяга 90 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. |
|||||||||||||
25 |
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа составляет 3 т, проволоки 18 т. На один трансформатор первого вида расходуется 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуется 3 кг железа и 1 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 6 д.е. Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль. |
|||||||||||||
26 |
Из трех продуктов – І, ІІ, ІІІ составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 11 ед. вещества С. Структура химических веществ приведена в следующей таблице:
Составьте наиболее дешевую смесь. |
|||||||||||||
27 |
Цех выпускает три вида деталей – А, В, С. Каждая деталь обрабатывается тремя станками. Организация производства характеризуется следующей таблицею. Отпускная цена за одну деталь А – 30 д.е., В – 32 д.е., С – 30 д.е.
Составьте план загрузки станков, обеспечивающий цеху получение максимальной прибыли. |
|||||||||||||
28 |
Предприятие должно выпускать два вида продукции А и В, используя при этом последовательно четыре станка. Данные о технологическом процессе указаны в следующей таблице. Прибыль на 1 ед продукции А – 2 д.е., В – 1 д.е.
Составьте план выпуска продукции, обеспечивающий предприятию наибольшую прибыль. |
|||||||||||||
29 |
На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей. Прибыль на 1 ед продукции типа 1 – 5 д.е.,типа 2 – 7 д.е.,типа 3 - 6 д.е
Составьте план производства запасных частей, обеспечивающий предприятию максимальную прибыль. |
|||||||||||||
30 |
Из двух сортов бензина образуются две смеси А и В. Смесь А содержит бензина 70% первого сорта и 30% второго сорта, смесь В содержит 15% бензина первого сорта и 85% второго сорта. Цена 1 кг смеси А 10 д.е., смеси В 6 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется 45 т бензина первого сорта и 70 т второго сорта. |
Завдання №2,3.
Розв’язок задач лінійного програмування графічним
та симплексним методами
Завдання: розв’язати задачу лінійного програмування наступними методами:
а) графічним методом;
б) симплексним методом.
№ |
Задача |
№ |
Задача |
№ |
Задача |
1 |
L=2x1+5x2→min 3x1+4x2≤6 2x1+3x2≤4 xi≥0 |
2 |
L=x1+4x2→min 3x1+5x2≥8 -3x1+10x2≤16 xi≥0 |
3 |
L=x1+x2→max x1+3x2≤30 2x1+x2≤20 xi≥0 |
4 |
L=2x1+2x2→min x1+x2≥1 -x1+x2≤1 xi≥0 |
5 |
L=2x1+3x2→max x1≥4 x2≥3 x1+x2≤8 xi≥0 |
6 |
L=x1+3x2→min x1+x2≤3 -x1+2x2≤5 xi≥0 |
7 |
L=x1+3x2→min -x1+2x2≤6 x1+2x2≤5 xi≥0 |
8 |
L=2x1+5x2→max x1+x2≤500 x1≤400 x2≤300 xi≥0 |
9 |
L=x1+4x2→max x1+x2≤7 x1≤3 x2≤1 xi≥0 |
10 |
L=2x1+x2→max 2x1+6x2≤15 4x1+3x2≤11 xi≥0 |
11 |
L=2x1+2x2→min x1+x2≥4 -x1+2x2≤8 xi≥0 |
12 |
L=3x1+2x2→max x1≥1 x2≥0.6 0.1x1+0.4x2≤2 xi≥0 |
13 |
L=x1+x2→max 3x1+x2≤20 2x1+3x2≤30 xi≥0 |
14 |
L=5x1+x2→max 3x1+6x2≤11 x1≤3 3x2≤1 xi≥0 |
15 |
L=2x1+7x2→max x1≥3 x2≥4 2x1+2x2≤9 xi≥0 |
16 |
L=x1+2x2→min x1+10x2≤1 -2x1+24x2≤1 xi≥0 |
17 |
L=2x1+4x2→max 4x1+x2≤15 x1+6x2≤7 xi≥0 |
18 |
L=x1+3x2→max 4x1+8x2≤17 x1≤3 x2≤2 xi≥0 |
19 |
L=2x1+3x2→min 5x1+2x2≥3 -4x1+6x2≤9 xi≥0 |
20 |
L=4x1+6x2→max x1+15x2≤32 x1≤31 x2≤2 xi≥0 |
21 |
L=4x1+x2→min 4x1+6x2≤9 -5x1+8x2≤4 xi≥0 |
22 |
L=2x1+x2→min 5x1+3x2≥7 -2x1+9x2≤21 xi≥0 |
23 |
L=x1+5x2→max 2x1+x2≤8 x1+3x2≤7 xi≥0 |
24 |
L=x1+3x2→min 5x1+3x2≥7 -2x1+9x2≤21 xi≥0 |
25 |
L=x1+4x2→max x1≥4 x2≥5 3x1+x2≤16 xi≥0 |
26 |
L=3x1+2x2→min 2x1+5x2≤8 -3x1+8x2≤4 xi≥0 |
27 |
L=x1+3x2→max 16x1+4x2≤9 x1≤1 x2≤2 xi≥0 |
28 |
L=5x1+4x2→max 4x1+x2≤9 x1+3x2≤6 xi≥0 |
29 |
L=3x1+x2→min 4x1+x2≥5 -3x1+10x2≤50 xi≥0 |
30 |
L=3x1+x2→max 2x1+5x2≥12 x2≥1 x1≤2 xi≥0 |