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

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

Постановка практической задачи ЛП включает следующие основные этапы: определение показателя эффективности, переменных задачи, задание линейной целевой функцииS(x), подлежащей минимизации или максимизации, функциональных h_k(x), g_j(x) и областных x_li <x_i <x_uiограничений.

Приведем сейчас общую математическую формулировку основной задачи линейного программирования.

Дана система т линейных уравнений с п неизвестными:

a₁₁ x₁ + a₁₁ x₂ + …… + a₁₁ x_n = b₁,

a₂₁ x₁ + a₂₁ x₂ + …… + a₂₁ x_n = b₂,

………………………………………… (1.1)

a_m1 x₁ + a_m1 x₂ + ……+ a_m1 x_n = b_m,

и линейная функция

f = c₁ x₁ + c₂ x_{2 +}………+ c_n x_n (1.2)

Требуется найти такое неотрицательное решение системы

x₁ ≥0, x₂≥0, … …, x_n ≥0 (1.3)

при котором функция f принимает наименьшее значение.

Уравнения (1.1)называют системой ограничений данной задачи; функцию f — целевой функцией (или линейной формой). Следует заметить, что систему ограничений в виде неравенств всегда можно свести к системе в виде равенств (способом введения фиктивных добавочных неизвестных).Так, если имеется

a_i1 x₁+ a_i1 x₂ + …… + a_i1x_n ≥ b_i,

то, вводя неизвестное х_n+1 ≥ 0, получим

a_i1 x₁+ a_i1 x₂ + …… + a_i1x_n - х_n+1 = b_i,

(Значением х_n+1 в окончательном результате можно пренебречь.)Кроме того, так как min f = — max(— f), то любая задача на (максимизацию сводится к задаче минимизации (и наоборот). Так что постановку задачи линейного программирования в форме (1.1) — (1.3) вполне можно считать общей.

Задача

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

Порядок решения задачи в Excel.

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

Рис.1 Исходные данные

- Делаем таблицу «Стоимость перевозок единицы продукции» (Рис.2)

Значения заносим в ячейки (B16:D20) (любые значения)

Рис.2

- Делаем таблицу «Количество перевезённой продукции» (Рис.3). В ячейки (B26:D30) заносим начальные значения для поиска решения.

Рис.3

- Делаем таблицу «Стоимость перевозок продукции». В ячейку B35 заносим формулу =ПРОИЗВЕД (B16;B26) и распространим её на область (B35;D39) (Рис. 4)

Рис.4

-В ячейке E40 вычисляем общую стоимость перевозок =СУММ (Е35;Е39). Она является целевой функцией. Задача состоит в том, чтобы найти такие значения (В26;D30), при которых значение ячейки E40 будет минимальным. (Рис.4)

-В ячейках Е26:Е30 вычисляем общее количество продукции перевезённое со склада (Рис.5).

Рис.5

а в ячейках B31:D31 - привезённое на соответствующий пункт (Рис.6)

Рис.6

При этом должны соблюдаться следующие ограничения:

1. Вся продукция со складов должна быть перевезена, т.е. Е26=B4, E27=B5, E28=B6, E29=B7, E30=B8.

2. Количество перевезённой продукции должно быть целым и неотрицательным.

3. Количество продукции в пунктах назначения должно соответствовать потребности, т.е. B31=E4, С31=E5, D31=E6.

Выполним команду СЕРВИС / ПОИСК РЕШЕНИЯ. В поле ОПТИМИЗИРОВАТЬ целевую функцию установим целевую ячейку, введём ссылку на ячейку $E$40. Установим переключатель Минимальное значение. В поле изменяя ячейки переменных укажем $B$26:$D$30

Рис.7

- Для ввода ограничений нажимаем кнопку добавить. В появившемся окне диалога Добавить ограничения в поле ввода Ссылка на ячейку введём диапазон $E$26:$E$30 В поле ввода Ограничение введём «=», и ссылку $B$4:$B$8. Снова нажимаем кнопку Добавить, аналогично вводим ограничения $B$31:$D$31=$E$4:$E$6. Далее вводим ограничения $B$26:$D$30= целое (в поле ввода Ограничение выбираем цел) и $B$26:$D$30 > = 0

Рис.8

Нажимаем кнопку Выполнить. В полученной таблице установим нужный формат данных.

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

Ниже представлен результат. (Рис.9)

Рис. 9

Список использованной литературы

1. Красс М.С.: Математические методы и модели для магистров экономики. - СПб.: Питер, 2010

2. Просветов Г.И.: Управленческие решения: задачи и решения. - М.: Библиогр.: с., 2009

3. Под ред. С.И. Макарова; Рец.: В.А. Агафонова и др.: Экономико-математические методы и модели. - М.: КноРус, 2009

4. http://io.my1.ru/index/linejnoe_programmirovanie