Тема 3 Целочисленное программирование 2 страница

Нормальный вектор целевой функции прибыли

Пробная точка

Множество решений данной задачи является выпуклый пятиугольник ОАВСД

Найдем точки пересечения прямых линий- координаты вершин многоугольника ОАВС

Ответ:

Задание 5

Составьте математическую модель задачи:

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

Вид сырья	Норма расхода на 1 изделие	Запас на складе
А	Б
прибыль от 1 изделия

Решение:

Пусть -количество продукции вида А

-количество продукции вида В

Тогда математическая модель имеет вид

Целевая функция прибыли

Графическое решение

Построим граничные прямые

Нормальный вектор целевой функции прибыли

Пробная точка

Множество решений данной задачи является выпуклый четырехугольник ОАВС

Найдем точки пересечения прямых линий- координаты вершин многоугольника ОАВС

Ответ:

Задание

Записать симметричную двойственную пару ЗЛП. Привести к виду для составления общей симплекс-таблицы.

Вариант 3

Тогда математическая модель имеет вид

Задание Составить математическую модель задачи

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

Показатели	Спинка дивана	Подлокотники кресла	Ножки стула	Наличие ресурса
Цена, д.ед/
Древесина м. куб.
Трудозатраты, чел.час.
Спрос, дес. Штук.

Построим математическую модель задачи.

Введем переменные

Пусть х1 ед. количество спинок стульев,

х2 ед.- количество подлокотников,

х3 ед. - количество ножек.

Тогда получаем систему ограничений и целевую функцию:

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

То есть расходы сырья на производство не должны превышать запасов сырья на складе.

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

Задание 4 Составить математическую модель задачи

Бригада приняла заказ на изготовление60 ед. продукции П1, зо ед. продукции П2 и 55 ед. продукции П3.

Продукция производится на станках А и В.

Для изготовления на станке А единицы продукции П1 требуется 3 ед. времени, единицы продукции П2- 40 единиц времени, единицы продукции П3- 10 единиц, на станке В – соответственно 7, 9 и 20 единиц времени. Найти план использования оборудования, чтобы заказ был выполнении в минимальное время.

Решение

Так как нужно найти количество времени работы на каждом станке, чтобы общие затраты времени были минимальными, то

Построим математическую модель задачи.

Введем переменные

Пусть х1 ед. на станке А количество продукции П1,

х2 ед.- количество на станке А продукции П2,

х3 ед. –количество на станке А продукции П3.

Тогда получаем систему ограничений и целевую функцию:

Задание.

Решение

Найдем производную по направлению вектора в точке

Найдем частные производные данной функции

Подставим координаты точки М в данные частные производные.

Определим направляющие косинусы для вектора а

Для этого найдем длину вектора

Найдем производную по направлению

Задание

Составьте математическую модель задачи:

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

Вид питательного вещества	Содержание питательного вещества в единице корма	Необходимое количество питательного вещества
А	Б
Стоимость единицы корма

Решение

Пусть -количество единиц корма вида А

-количество единиц корма В

Тогда математическая модель имеет вид

Целевая функция затрат

Задания для самостоятельного решения по теме №1

Задание 1

Построить линии уровня для следующих функций

a)

b)

c)

d)

e)

Задание 2

Построить область допустимых решений системы неравенств

a)

b)

c)

d)

e)

Задание 3

Построить градиент и антиградиент следующих функций в точке (0;0)

a)

b)

c)

d)

Задание 4

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

a) b)

Задание 5

Таблица 3

Cырье	А	Б	Запас
Прибыль			max

Задание 6

Таблица 4

Состав	А	Б	Норма
Затраты			min

Задание 7,8,9,10 Составить математическую модель задачи(ввести переменные, систему ограничений и целевую функцию)

Задание 7

Трикотажная фабрика использует для производства свитеров и кофточек, жилетов и шапочек чистую шерсть, силон, нитрон, запасы которых составляют соответственно 1000, 500 и 400 кг. Количество пряжи каждого вида, необходимой для изготовления 10 изделий, а также прибыль, получаемая от их реализации, приведены в таблице. Установить план выпуска изделий, максимизирующий прибыль.

Таблица

Вид сырья	Затраты пряжи на 10 шт. изделий, кг
Свитера	Кофточки	Жилеты	Шапочки
Шерсть
Силон			1,5	0,5
Нитрон			0,5	0,5
Прибыль

Задание 8

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

Стройматериалы	Запасы стройматериалов, м^3	Расход стройматериалов для проектов, м^3
I	II	III	IV
Кирпич силикатный
Кирпич красный
Пиломатериалы
Полезная площадь, м^2

Задание 9

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

Таблица

Вид работ	Объем работ	Производительность техники для каждой модели
м1	м2	м3	м4
Р1
Р2
Р3
Стоимость единицы техники

Задание 10

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

Задание 11

Найти оптимальное распределение трех видов механизмов, имеющихся в количестве 45, 20 и 35, между четырьмя участками работ, потребности которых соответственно равны 10, 20, 30 и 40 при следующей матрице производительности:

Таблица

Объем выпуска продукции

Задание 12

При подкормке посева нужно внести на 1 га почвы не менее 10 ед. химического вещества А, 25 ед. вещества Б, 20 ед. вещества В. Сельскохозяйственное предприятие закупает комбинированные удобрения четырех видов (I,II,III,IV). В таблице указаны содержание химических веществ и цена за единицу массы каждого вида удобрений. Минимизировать расходы по закупке необходимого количества удобрений.

Таблица

Химическое вещество	Содержание вещества в единице массы удобрения
I	II	III	IV
А
Б
В
Цена

Задание 17

Имеющийся фонд материалов М₁, М₂, М₃ нужно распределить между изготовителями продукции П₁, П₂, П₃, П₄ так, чтобы получить максимальную прибыль. Нормы расходов материалов, запасы и прибыль, получаемая за единицу продукции, приведены в таблице.

Таблица

Материал	Фонд материалов	Продукция
П1	П2	П3	П4
М1		0,7	0,9	1,5	2,3
М2		1,4	0,3	0,7	2,5
М3		0,5	2,1	1,8	0,7
Прибыль

Задание 18

Предприятие может выпускать продукцию четырех видов – П₁, П₂, П₃, П₄, сбыт любого количества которой обеспечен. При производстве продукции расходуются различные ресурсы, их запасы и удельные затраты приведены в таблице, там же указана и цена продукции. Найти оптимальный план выпуска продукции, максимизирующий выручку предприятия от ее реализации.

Таблица

Ресурсы	Запасы ресурса	Нормы расходов
П1	П2	П3	П4
Трудовые ресурсы
Полуфабрикаты
Станочное оборудование
Цена единицы продукции

Задание 19

В суточном рационе кормления крупного рогатого скота должно быть не менее 20 кормовых единиц, не менее 2000 г белков и не менее 100 г кальция. Для кормления используют сено, силос, корнеплоды и концентраты. Содержание питательных веществ в 1 кг каждого вида корма, а также его себестоимость представлены в таблице. Составить кормовой рацион минимальной стоимости.

Таблица

Содержание питательных веществ в 1 кг корма	Корм
Сено	Силос	Корнеплоды	Концентрат
Кормовая единица	0,5	0,2		0,8
Белки, г
Кальций, г
Себестоимость 1 кг корма, ден. ед.

Тема 2. Симплекс-метод решения задач линейного программирования

Смысл симплекс-метода заключается в целенаправленном переходе от одного опорного решения ЗЛП к другому (т.е. от одной угловой точки ОДР к другой) в направлении экстремума и состоит в последовательности этапов:

а. - найти начальное опорное решение;

б. - осуществить переход от одного опорного решения к другому;

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

Правила преобразования симплекс-таблиц

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

2. Столбец, сответствующий этому элементу, называется разрешающим.

3. Вычисляем отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение).

4. Находят наименьшее из этих симплекс-отношений, оно соответствует разрешающей строке.

5. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

6. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.

7. После нахождения разрешающего элемента строят новую таблицу.

8. Неизвестную переменную, соответствующие раз­решающей строке, заменяют переменной, соответствующей разрешающему столбцу.и столбцу, меняют местами.

9. Все элементы разрешающей строки делим на разрешающий элемент

10. Остальные элементы разрешающего столбца заменяем нулями.

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

Критерий оптимальности. Как только получится таблица, в которой в последней строке в задаче на min все элементы отрицательны (в задаче на max все элементы положительны), считается, что экстремум найден.

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

Задача 3

Решить задачу 1 симплекс-методом

Таблица 6

Сырье			Запасы сырья
Прибыль П			max

Дата добавления: 2017-02-01