Решение задач линейного программирования (стр. 3 из 5)

В1	В2	……	Вn	Всего
C_1,1	C_1,2	……	C_1,n	а1
A₁	C_2,1	C_2,2	……	C_2,n	а2
A₂	….	….	….	….
….	…	…	…	….	….
A_m	C_m,1	C_m,2	……	C_m,n	аm
b1	b2	bn

Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

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

Производственно-транспортная задача

Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).

Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.

3. Решение задач

3.1. Решение задачи линейного программирования

3.1.1.Постановка задачи

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

Составим целевую функцию и зададим ограничения.

Пусть Х1, Х2, Х3, Х4, Х5 – неизвестные переменные

Целевая функция: L(Х) = 14 х

-9 х₂ - х₄+6,4 х₅—> min;

Ограничения: g₁: 0,9 х

+ 10 х₂-28х₄ +5х₅

245,

g₂: 0,8 х

+ 1,7х₂ -0,2х₃ -0,5х₄ =9,

g₃: 6 х

+ 4х₃ - 7х₄ + 6,3х₅

54,

g₄: 8 х

+6,2х₂ -4,8х₄ +2,9х₅

17,

3.1.2.Ввод данных

1. Введем на рабочий лист Excel необходимые данные. В ячейке В5 запишем выражение целевой функции, а в ячейках В8:В11– левые части ограничений.

2.Командой Сервис, Поиск решения откройем диалоговое окно ²Поиск решения² (рис. 2) и заполним его данными. В поле Установить целевую ячейку введем адрес целевой функции $В$5, в поле Изменяя ячейки - адреса $B$3:$E$3. Переведите переключатель Равной в положение минимальному значению.

Чтобы ввести ограничения в окне ²Поиск решения² нажмем кнопку Добавить и на экране появится диалоговое окно ²Добавление ограничения² .

3. Начнем с первого ограничения. Установим курсор в поле Ссылка на ячейку и, выделяя на листе (рис.1) ячейку В8, введем ее адрес $B$8 в это поле.

Кнопкой-стрелкой откроем список и выберем в нем знак <=. В поле Ограничение установите курсор и, выделяя на листе ячейку D8, введем ее адрес $ D $8 в это поле и нажмем кнопку Добавить.

4. Повторим действия п.3 и введем остальные ограничения $В$9=$D$9, $В$10<=$D$10, $В$11>=$D$11, реализующие граничные условия. После ввода последнего ограничения $F$11<=$H$11 вместо кнопки Добавить нажмем кнопку ОК.

Таким образом, в окно ²Поиск решения² (рис. 2) будут введены ограничения.

3.1.3. Решение задачи

1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно ²Параметры поиска решения² (рис.4).

В этом окне оставьте неизменными установленные по умолчанию Максимальное время: 100 сек, выделяемое на поиск решения (возможно до 9 часов), Предельное число итераций: 100, Относительная погрешность: 0,000001, Допустимое отклонение: 5%, переключатели в положении линейная, прямые, Ньютона.

Установим флажок Линейная, чтобы обеспечить применение симплекс-метода, и нажмите кнопку ОК.

2. В окне ²Поиск решения² нажмите кнопку Выполнить. На экране появится диалоговое окно ²Результаты поиска решения² (рис.5) с информацией «Решение найдено. Все ограничения и условия оптимизации выполнены», подтверждающей успешное решение задачи оптимального распределения ресурсов и количественные результаты (значения переменных, ограничений и целевой функции), приведенные на рис.6.

x₁ = А3 = 0, x₂= В3 = 14,43, x₃ =С3 = 39,93, x₄ =D3 =15,10, x₅=Е3=0

При этом значение целевой функции:

L= В5 = -144,99.

3.1.4. Анализ оптимального решения

Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно ²Результаты поиска решения². С его помощью можно подготовить три типа отчетов: по результатам (опция Результаты), по устойчивости (опция Устойчивость), по пределам (опция Пределы).

1. Подготовим отчет по результатам (рис.7).

Отчет состоит из трех таблиц.

В первой таблице (Целевая ячейка) приводятся сведения о целевой функции: исходное значение (в графе «Исходно») и оптимальный результат (в графе «Результат»).

Во второй таблице (Изменяемые ячейки) приводятся исходные (в графе «Исходно») и полученные в результате решения задачи (в графе «Результат») значения переменных x₁, x₂, x₃, x₄, x_5.

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

2. Щелчком на ярлычке Отчет по устойчивости откроем содержимое отчета на рабочем листе (рис. 8).

Отчет по устойчивости содержит две таблицы.

В первой таблице (Изменяемые ячейки) приводятся следующие значения переменных:

· результаты решения задачи (графа «Результ. значение»);

· нормированная стоимость, т.е. дополнительные двойственные переменные v_j,

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

· коэффициенты целевой функции (графа «Целевой коэффициент»);

· предельные значения приращения коэффициентов Dc_j целевой функции (последние две графы), при которых сохраняется набор переменных, входящих в оптимальное решение.

Во второй таблице приводятся значения ограничений:

· значения используемых (графа «Результ. Значение») и заданных (графа «Ограничение, правая часть») ресурсов;

· теневая цена, т. е. двойственные оценки z_i, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

· значения приращения ресурсов Δb_i (последние две графы), при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.

3. Отчёт по переделам (рис.9) показывает, в каких пределах может меняться выпуск продукции, вошедшей в оптимальное решение, при сохранении его структуры:

· приводятся значения х_i в оптимальном решении (графа «Значение»);

· даются нижние и верхние пределы изменения х_i и соответствующие значения целевой функции (в графах «Целевой результат»).

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

3.2.1. Построение модели

В данной задаче искомыми неизвестными являются количество полок каждого вида, которые будут произведены в текущем месяце. Таким образом, Х1 – количество полок А(шт./мес.); Х2 – количество полок В1(шт./мес.); Х3 – количество полок В2(шт./мес.).

Целевая функция: Прибыль определяется разностью между ценой и себестоимостью, тогда:

L(х) = (192-150)х1+(154-120)х2+(147-134)х3 мах

Руб./шт.* шт./мес. =руб./мес.

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

· Ограничения по фонду времени ( с использованием трудоемкости работ)

3,2 х1

27*8*1*22

ч/шт.* шт./мес.

чел.* ч/(чел.см.)*см./дн. * дн./мес.

ч/мес.

3,2 ч/шт. (Тр1) – это время, затрачиваемое на столярные работы при производстве одной полки типа А;

27 чел. (Р1) – это количество столяров;

8ч/(чел.*см) – количество часов работы 1 человека в течении смены;

1см./дн. – количество смен в одном рабочем дне;

22 дн./мес. – количество рабочих дней в месяце

Необходимо произвести проверку единиц измерения!