Цель работы

Целью работы является приобретение навыков решения задач линейного программирования с помощью надстройки поиска решения в среде Excel.

Ход работы

Задание 1

1. По данному функционалу и ограничениям составить текст прямой и двойственной к ней задачи и решить симплекс методом по программе Excel (поиск решения):

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

Экономико-математическая модель задачи:

Пусть X₁, X₂, X₃, X₄, X₅, X₆, X₇, X₈  - число продукции различного типа.

Целевая функция имеет вид:

f(X) = X₁ + 2*X₂ + 2*X₃ + X₄ + 2*X₅ + X₆ – 9*X₇ – 8*X₈ → max

а ограничения по ресурсам:

X₁ + X₂ + X₃ + X₄ + 2*X₅ + 3*X₆ – 5*X₇ + 3*X₈ =15,

X₁ - X₂ + X₃ + X₄ + X₆ – 5*X₇ + 3*X₈ = 9,

X₁ + X₂ - X₃ + X₄ + 2*X₅ + 3*X₆ + 3*X₇ – X₈ = 7,

X₁ + X₂ + X₃ - X₄ + 2*X₅ + 3*X₆ – 3*X₇ + X₈ = 9,

X_i  ≥ 0, где i = 1..8.

На рисунке 1 представлено заполнение аргументов функции СУММПРОИЗВ(), позволяющей подсчитать сумму произведений диапазонов. В данной задаче эта функция используется для подсчета значения целевой функции (сумма произведений переменных и их коэффициентов) и значений по функциям ограничений (сумма произведения переменных и коэффициентов в формулах ограничений).

Результат создания таблиц для поиска решения приведен на рисунке 2.

Рисунок 1. Аргументы функции СУММПРОИЗВ

Рисунок 2. Таблица для поиска решения

На рисунке 3 представлено заполнение параметров поиска решения: целевая функция располагается в ячейке J5, необходимо найти ее максимум, изменяя значения переменных. Также прописаны ограничения и указано, что все переменные должны быть положительными. Для поиска решения используется симплекс-метод.

На рисунке 4 представлен результат поиска решения. Значение целевой функции составило 22. Для получения этого значения необходимо произвести 5ед. X₁, 3 – X₂, 4 – X₃, 3 – X₄.

Рисунок 3. Параметры поиска решения

Рисунок 4. Результат поиска решения

Экономико-математическая модель двойственной задачи:

Так как целевая функция прямой задачи формулируется на максимум, целевая функция двойственной задачи – на минимум.

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

Число переменной в двойственной задаче равно числу функциональных ограничений исходной задачи (4), а число ограничений в системе двойственной задачи – числу переменных в исходной (8).

Коэффициенты при неизвестных в целевой функции двойственной задачи – свободные члены в системе ограничений исходной задачи (15, 9, 7, 9), а свободными членами двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной (1,2,2,1,2,1,-9,-8).

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

Целевая функция двойственной задачи имеет вид:

g(Y) = 15*Y₁ + 9*Y₂ + 7*Y₃ + 9*Y₄ → min

а ограничения:

Y₁ + Y₂ + Y₃ + Y₄ = 1,

Y₁ - Y₂ + Y₃ + Y₄ = 2,

Y₁ + Y₂ - Y₃ + Y₄ = 2,

Y₁ + Y₂ + Y₃ - Y₄ = 1,

2*Y₁ + 2*Y₃ + 2*Y₄ = 2,

3*Y₁ + Y₂ + 3*Y₃ + 3*Y₄ = 1,

-5*Y₁  - 5*Y₂ + 3*Y₃ – 3*Y₄ = -9,

3*Y₁ + 3*Y₂ - Y₃ + Y₄ = -8.

Параметры поиска решения для двойственной задачи приведены на рисунке 5, а результат – на рисунке 6.  Как видно, целевое значение двойственной задачи совпало со значением целевой функции прямой задачи – 22.

Рисунок 5. Параметры поиска решения для двойственной задачи

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

2. По данному функционалу и ограничениям составить текст прямой и двойственной к ней задачи и  решить симплекс методом по программе Excel (поиск решения)

Экономико-математическая модель задачи:

Пусть X₁, X₂, X₃ – число продукции различного типа.

Целевая функция прямой задачи, как правило, задается на максимум. Формула в условиях задана на минимум. Необходимо умножить каждый из коэффициентов на (-1), чтобы перенаправить формулу на максимум:

f(X) = -X₁ + X₂ - X₃ → max.

Чтобы получить 3 ограничение, необходимо поменять знак неравенства и умножить переменную на (-1). Таким образом, ограничения по ресурсам:

X₁ - X₂ = 1,

X₂ ≤ 1,

-X₃ ≤  0.

Параметры поиска решения прямой задачи приведены на рисунке 7, а результат поиска решения  - на рисунке 8.

Значение целевой функции – (-1). Оптимальным предлагается считать решение с одной единицей продукции X₁.

Подставив значения в исходную формулу, можно получить, что целевая функция составит 1*1 = 1 (минимум).

Рисунок 7. Параметры поиска решения прямой задачи

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

Экономико-математическая модель двойственной задачи:

Переменные: Y₁, Y₂

Целевая функция имеет вид:

g(Y) = Y₁ + Y₂ → min

а ограничения:

Y₁ ≥ -1,

- Y₁ + Y₂ ≥ 1.

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

Параметры поиска решения для двойственной задачи приведены на рисунке 9, а результат – на рисунке 10. 

Как видно, целевое значение двойственной задачи совпало со значением целевой функции прямой задачи –   (-1).

Рисунок 9. Параметры поиска решения двойственной задачи

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

Задание 2.

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

Необходимо сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции

Пусть X₁, X₂, X₃, X₄  - переменные, обозначающие 4 вида продукции (их количество, предлагаемое для производства).

Целевая функция задачи имеет вид:

f(X) = 20*X₁ + 15*X₂ + 18*X₃ + 16*X₄ → max

а ограничения на ресурсы имеют вид:

25*X₁ + 20*X₂ + 12*X₃ + 14*X₄ ≤ 360,

22*X₁ + 14*X₂ + 18*X₃ + 30*X₄ ≤ 600,

10*X₁ + 14*X₂ + 18*X₃ + 26*X₄ ≤ 500.

Параметры поиска решения отображены на рисунке 11, а найденное решение – на рисунке 12.

Максимальная прибыль (514,55) достигается при производстве 1,45 единиц 1 продукции и 26,97 единиц – продукции 3 вида.

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

Итак, максимальную прибыль (506) можно получить при производстве 1 ед. продукции первого вида и 27 ед. – третьего типа. При этом затрачивается 349 единиц сырья, 508 единиц рабочего времени и 496 единиц оборудования.

Рисунок 11. Параметры поиска решения

Рисунок 12. Найденное решение

Рисунок 13. Добавление ограничения

Рисунок 14. Параметры поиска целочисленного решения

Рисунок 15. Целочисленное решение

Задание 3.

Оптимизировать стоимость перевозки (А_i – поставщики, B_i – потребители).

Экономико-математическая модель транспортной задачи. Пусть x_ij – количество единиц груза, запланированных к перевозке от поставщика i к потребителю j. Стоимость перевозки составит c_ij*x_ij.

Стоимость всего плана выразится формулой:

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

·     все грузы должны быть перевезены:

·     все потребности должны быть удовлетворены:

Необходимо найти минимальное значение линейной функции Z.

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

Рассматриваемая задача является открытой, потому что суммарное предложение (46+34+40=120) превышает суммарную потребность (4+3+2+5=14).

Необходимо привести модель к закрытому виду. Для этого нужно ввести фиктивного потребителя B₅, потребность которого составит разницу между суммарным предложением и суммарной потребностью (120-14=106). Стоимость перевозки груза до фиктивного потребителя полагается равной нулю, поскольку на самом деле груз не перевозится.

На рисунке 16 отображена форма для решения задачи, созданная в Excel. Так, первая таблица представляет собой исходные данные: значения потребностей и предлагаемые объемы грузов, а также стоимости перевозок от поставщиков к потребителям.

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

Для того, чтобы задать ограничения в инструменте «Поиск решения», необходимо также задать условия реализации мощностей поставщиков и условия удовлетворения запросов потребителей (см. Рисунок 17).

Также требуется задать ячейку с формулой для нахождения целевой функции (см. Рисунок 18). Использована функция СУММПРОИЗВ() – находится сумма произведений значений матрицы перевозок на соответствующие им значения стоимостей перевозок единицы груза. В настоящий момент полученное значение составило 49 – сумма всех стоимостей перевозок грузов, умноженных на единицы.

Рисунок 16.  Форма решения задачи

Рисунок 17. Задание условий

Рисунок 18. Задание формулы для целевой функции

На рисунке 19 отображены параметры поиска решения. Задается ячейка целевой функции, направление оптимизации (до минимума, так как затраты надо минимизировать), изменяемые ячейки (диапазон значений в матрице перевозок, сначала заполненной единицами), ограничения (потребление должно совпадать с потребностями, а фактические отгрузки – с предложениями поставщиков).

На рисунке 20 отображено найденное решение.

Рисунок 19. Параметры поиска решения

Рисунок 20. Найденное решение

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

·     4 единиц груза от 1 поставщика 1 потребителю;

·     3 единиц груза от 1 поставщика 2 потребителю;

·     2 единиц груза от 3 поставщика 3 потребителю;

·     5 единиц груза от 2 поставщика 4 потребителю.

Так достигается удовлетворение потребностей всех потребителей. Поскольку был введен фиктивный потребитель, 39 единиц груза остается у первого поставщика, 29 – у второго, 38 – у третьего.

Вывод

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