РАБОТА 1. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ СИМПЛЕКСНЫМ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель работы: ознакомиться с симплексным методом линейного программирования.

Задание: используя симплексный метод научиться решать задачи линейного программирования, освоить методику решения одно- и многопродуктовой транспортной задачи в среде Microsoft Office Excel.

Значительное число планово-производственных задач имеет выражение критерия оптимальности в виде линейной функции от входящих в него переменных. При этом на указанные переменные могут быть также наложены некоторые ограничения в форме линейных равенств или неравенств.

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

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

Решение этих задач, математическая формулировка которых сводится к требованию максимизации или минимизации критерия оптимальности, заданного в виде линейной функции независимых переменных с линейными ограничениями на них составляет задачу линейного программирования [1, 2].

В задачах линейного программирования критерий оптимальности представляется в виде

, (1.1)

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

На значения переменных налагаются дополнительные условия, заданные в виде равенств и неравенств

, ; (1.2а)

, ; (1.2б)

, . (1.2в)

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

Будем также считать, что все величины в ограничениях (1.2) отличны от нуля и положительны.

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

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