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

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

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

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

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

a11 x1 + a11 x2 + …… + a11 xn = b1 ,

a21 x1 + a21 x2 + …… + a21 xn = b2 ,

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

am1 x1 + am1 x2 + ……+ am1 xn = bm,

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

f = c1 x1 + c2 x2 +………+ cn xn (1.2)

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

x1 ≥0, x2≥0, … … , xn ≥0 (1.3)

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

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

ai1 x1+ ai1 x2 + …… + ai1xn ≥ bi ,

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

ai1 x1+ ai1 x2 + …… + ai1xn - хn+1 = bi,

(Значением х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