Линейное программирование

Условия задач  и задания к типовому расчету:

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

Задача  №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 (в денежных единицах за единицу времени работы по данной технологии);

l_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 и затраты l_j.

Задание

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

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

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

 

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

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

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

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

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

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

Задание

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

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

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

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

 

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

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

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

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

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

Задание

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

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

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

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

 

 

Задача  №4. Двойственные задачи

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

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

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

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

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

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

5. Пусть ресурсы взаимозаменяемы  и из производства исключается Db₁=2 единицы ресурса R₁. Определить на сколько может уменьшиться максимальный доход (величина D₁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, которые недополучают продукцию, и указать ее количество.