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

Условие задачи №1

Задача о выборе оптимальных технологий

Продукция в цехе может производиться n различными способами T_j (n=3). Для производства продукции могут использоваться ресурсы: рабочая сила, сырье (сталь, древесина, цветные металлы), электроэнергия.

Обозначения:

x_j – время использования технологического способа T_j при производстве продукции (j=1,2,3);

b_i – объем ресурса R_i (i=1,2,3);

a_ij – расход ресурса R_i за единицу времени по технологии T_j;

A – годовое плановое задание по выработке продукции (ден. ед.);

c_j – производительность технологии T_j (в денежных единицах за единицу времени работы по данной технологии);

λ_j – затраты на изготовление продукции в единицу времени по технологии T_j (денежных единицах).

Налагаются ограничения по объемам b_i ресурсов (вида £) и по плановому выпуску A продукции (вида ³).

Возможны три критерия f₁, f₂, f₃ оптимальности плана X=(x₁,…,x_n) применения каждого технологического способа:

а) f₁ – наибольший объем выпускаемой продукции по всем технологиям (ден. ед.);

б) f₂ – наименьшие затраты на выполнение планового задания (ден. ед.);

в) f₃ – наибольшая конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции (ден. ед.).

В таблице представлены объемы b_i ресурсов R_i, их расход a_ij в единицу времени для каждой технологии, плановое задание A, производительности cj технологий T_j и затраты λ_j .

Задание

1. По данным своего варианта составить математические модели задачи по трем критериям оптимальности, сопровождая построение подробными пояснениями.

2. Дать математические постановки задач.

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

Условие задачи №2

Задача о выборе оптимальных технологий

Предприятие выпускает продукцию вида П₁ и П₂, на изготовление которой используется сырье S₁, S₂, S₃. Известны:

b_i – запасы сырья; a_ij – нормы расхода сырья S_i (i=1,2,3) на производство единицы продукции (j=1,2); c_j – себестоимость единицы продукции П_j; p_j – оптовая цена единицы П_j.

Определить оптимальный план X=(x₁,x₂) производства продукции П₁ и П₂, при котором при имеющемся количестве сырья можно получить наибольшую прибыль.

Задание

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

2. Решить задачу графическим методом.

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

4. Определить аналитически и графически, можно ли произвести 3 ед. продукции П₁ и 2 ед. продукции П₂.

Задача №3. Симплексный метод решения задачи линейного
программирования

Условие задачи №3

Задача о выборе оптимальных технологий

На предприятии выпускается n видов П_j (j=1, 2,…, n). При ее изготовлении используются ресурсы R₁, R₂, R₃, размеры допустимых затрат ресурсов ограничены величинами b₁, b₂, b₃. Расход ресурса R_i (i=1,2,3) на производство единицы продукции П_j равен a_ij. Прибыль от реализации единицы продукции П_j равна c_j ден. ед.

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

Задание

1. Записать математическую модель задачи.

2. Привести модель к каноническому виду и заполнить симплексную таблицу.

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

4. Дать экономическое истолкование оптимального решения X_опт и наибольшего значения целевой функции f_наиб(X_опт).

Условие задачи №4

Для задачи о выборе оптимальных технологий (см. задачу №3) требуется:

1. Сформулировать в экономических терминах двойственную задачу.

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

3. Используя оптимальное решение X_опт задачи №3 и соответствие между парами двойственных переменных прямой и двойственной задач, найти компоненты оптимального решения Y_опт двойственной задачи и значение целевой функции T_min в двойственной задаче.

4. Дать экономическое истолкование величине T_min, значениям  основных и дополнительных переменных в оптимальном решении Y_опт двойственной задачи. Указать наиболее дефицитный и недефицитный (избыточный) ресурсы, если они имеются.

5. Пусть ресурсы взаимозаменяемы и из производства исключается ∆b₁=2 единицы ресурса R₁. Определить на сколько может уменьшиться максимальный доход (величина ∆₁f_max). Найти, сколько единиц ресурсов R₂ и R₃ нужно ввести дополнительно в производство, чтобы компенсировать возможный убыток.

Задача №5. Транспортная задача

Условие задачи №5

На заводах A₁, A₂, A₃ производится однородная продукция в количестве a₁, a₂, a₃ единиц. Себестоимость единицы продукции на заводе A_i составляет c_i ден. единиц.

Четырем потребителям B₁, B₂, B₃, B₄ требуется соответственно b₁, b₂, b₃, b₄ единиц готовой продукции. Расходы c_ij ден. ед. по перевозке единицы готовой продукции с завода A_i потребителю B_j заданы.

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

Задание:

1. Внести числовые данные транспортной задачи в распределительную таблицу и составить математическую модель.

2. Если транспортная задача открытого типа, то привести ее к закрытой. Построить исходные планы перевозок по методы «северо-западного угла» (X_с-з) и по методу «минимального элемента» (X_мэ). Вычислить значения общих затрат для построенных планов f(X_с-з) и f(X_мэ) и выявить, какой планов лучше.

3. Методом потенциалов проверить этот план X на оптимальность.

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

5. Определить по оптимальному плану перевозок X_опт:

1) количество продукции, отправляемое из каждого завода A₁, A₂, A₃ каждому потребителю B₁, B₂, B₃, B₄;

2) наименьшие общие затраты на производство продукции и доставку ее потребителям;

3) заводы A_i, в которых остается нераспределенная продукция, и указать ее объем;

4) Пункты потребления B_j, которые недополучают продукцию, и указать ее количество.

Контрольная Линейное программирование, вариант 11 (НГТУ)

Контрольная Мат.логика и алгоритмы (СибГУТИ, вариант 10)

Новую работу можно заказать здесь