Лабораторная работа № 3.

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

Программное обеспечение: Microsoft Excel

Основные сведения

1. Целочисленные задачи линейного программирования.

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

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

Задача.

В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено S кв.м площади. На приобретение оборудования предприятие может израсходовать A руб. при этом оно может купить оборудование n видов. Единица оборудования i-го вида стоит a_i руб. Приобретение оборудования i-го вида позволяет увеличить выпуск продукции в смену на b_i ед. Для установки одного оборудования i-го вида требуется c_i кв.м. площади. Определить сколько единиц оборудования каждого вида необходимо закупить, чтобы максимально увеличить выпуск продукции.

Построение математической модели. Предположим, что предприятие закупит оборудование i-го вида в количестве x_i шт.

Целевая функция задачи описывает увеличение объема выпуска продукции, которое должно быть максимальным, т.е.

F = b₁ x₁ + b₂ x₂ + … + b_n x_n → max.

Запишем теперь ограничения задачи.

Первое ограничение относится к стоимости оборудования и выделенной для этой цели денежных средств:

a₁ x₁ + a₂ x₂ + … + a_n x_n ≤ A.

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

c₁ x₁ + c₂ x₂ + … + c_n x_n ≤ S .

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

x_i  ≥ 0  и  x_i – целые

2. Задачи сводящиеся к транспортной модели

Довольно обширный класс экономических задач, не имеющих ничего общего с транспортной задачей, тем не менее сводится к транспортной модели, и для решения таких задач может быть использован алгоритмы и методы решения транспортных задач (Методическое пособие Лабораторная работа №2. Транспортные задачи и их решение средствами Excel).

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

Рассмотрим конкретную задачу.

Задача. Имеется n участков земли, на которых могут быть засеяны m видов культур. Площадь каждого участка соответственно равна s_i. Каждой i-ой культурой следует засеять площадь v_i . Урожайность каждой из культур для каждого из участков различна и задается матрицей C= {c_ij}.

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

Построение математической модели

Обозначим искомые величины – площадь культуры j засеянной на участке i , как x_ij , i = 1, …, n, j =1, …, m.

Целевая функция представляет собой суммарную урожайность всех культур со всех участков. Так как урожайность культуры j с единицы площади участка i равна с_ij , то урожайность этой культуры с площади x_ij составит с_ij x_ij . Суммарная урожайность – целевая функция, которая должна принимать максимальное значение

.

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

, i = 1, …, n

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

, j =1, …, m

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

x_ij ≥ 0,   i = 1, …, n, j =1, …, m

Эта модель по ограничениям полностью совпадает с математической моделью транспортной задачи. Модель является сбалансированной.

В данной задаче необходимо максимизировать целевую функцию. Для перехода к стандартной транспортной модели надо заменить функцию F на противоположную функцию F' = – F, которую необходимо минимизировать, т.е.

Далее задача решается известными методами.