Решение оптимизационных задач

Опорный план X₃=(0; 14; 0; 72; 66; 0) является оптимальным, т.к. .

Ответ: F_max=28 при Х*=(0; 14; 0).

Осуществим  поиск решения с помощью MS Excel.

В ячейки E2:E4 введём ограничения. В ячейку C5 - формулу целевой функции.

Используем  вкладку Данные/Поиск решения:

 

Рисунок 7– Решение  в MS Excel

Ответ: F_max=28 при Х*=(0;14;0).

Приведём решение  задачи в MathCAD 14 Professional.

Рисунок 8 – Вод исходных данных

Программный код  см. Приложение А.

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

• функция F(A,B.C,Q) находит решение задачи линейного программирования;
• описание переменных в скобках [ ] размерность аргумента;
• А[n,m]  - расширенная матрица условий задачи линейного программирования (записанная с учётом дополнительных и искусственных переменных);
• B[n] - Вектор свободных членов (правых частей неравенств);
• С[m] - Вектор коэффициентов целевой функции (вместо теоретически бесконечно большого числа М подставить большое 100000000000000);
• Q[n] - вектор индексов исходных базисных переменных;

• F(A,B,C,Q)[m,2] - первый столбец результата - значения переменных соответствующих оптимальному (минимальному) значению, первый элемент второго вектора - значение целевой функции, второй элемент второго вектора - если равен 1, то целевая функция в области допустимых решений ограничена, если равен 0, то целевая функция в области допустимых решений неограниченна.

Рисунок 9 – Формирование результата в MathCAD

 

4 Транспортная задача

4.1 Теоретическая часть

Транспортная  задача — задача об оптимальном  плане перевозок  из пунктов отправления в пункты назначения. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Определяем оптимальной  план перевозок некоторого груза из m-пунктов отправления А₁, А₂,…А_m в n-пунктов назначения В₁,В₂,…В_n при этом в качестве критерия оптимальности берем либо минимальную стоимость перевозки всего груза, либо минимальное время доставки.

Обозначим: С_ij - тарифы перевозок, а_i-запасы грузов, b_j- потребности в грузе, x_ij- количество единиц груза.

Математическая  постановка задачи

Целевая функция:

                                             (14)

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

                                                          (15)

                                                         (16)

                                                              (17)

Планом транспортной задачи называется неотрицательное  решение систем линейных уравнений (15) и (14). Получим матрицу Х=(х_ij).

Оптимальным планом называют план Х=(х_ij), при котором целевая функция принимает свое минимальное значение.

Условие разрешаемости:

                                                 (18)

Если Σa_i>Σbj, то вводится фиктивный (n+1)-й пункт назначения.

Если Σa_i<Σb_j, то вводится фиктивный (n+1)-й пункт отправления.

4.2 Практическая часть

Задача 3: Требуется перевезти товары с четырёх складов в пять магазинов. Данные о наличии товаров на складе, спрос на него в магазинах, а так же стоимости перевозки единицы груза между складами и магазинами приведены в таблице. Составить план перевозки, чтобы затраты были минимальными.

Таблица 6 – Исходные данные

Пункт отправления	Пункты назначения					Запасы, aj (тонн)
	B1	B2	В3	B4	B5
а1	11	28	15	12	17	4
а2	32	27	26	10	3	6
аз	12	4	22	3	1	10
а4	4	1	5	4	24	10
Потребности, bi (тонн)	7	7	7	7	2	30

Решение:

Метод северо-западного угла (диагональный)

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

Таблица 7 - Решение методом северо-западного угла

Пункт отправления	Пункты назначения					Запасы, aj (тонн)
	B1	B2	В3	B4	B5
а1	11 4	28 ––	15 ––	12 ––	17 ––	4
а2	32 3	27 3	26 ––	10 ––	3 ––	6
аз	12 ––	4 4	22 6	3 ––	1 ––	10
а4	4 ––	1 ––	5 1	4 7	24 2	10
Потребности, bi (тонн)	7	7	7	7	2	30

S=11 *4+32*3+27*3+4*4+22*6+5*1+4*7+24*2=450 (д.е.).

Ответ S=450 д.е., план перевозок X₁=

Таблица 8 - Решение методом минимального элемента

Пункт отправления	Пункты назначения					Запасы, aj (тонн)
	B1	B2	В3	B4	B5
а1	11 4	28 ––	15 6	12 ––	17 ––	4
а2	32 –	27 ––	26 ––	10 ––	3 ––	6
аз	12 ––	4 ––	22 1	3 7	1 2	10
а4	4 3	1 7	5 –	4 --	24 --	10
Потребности, bi (тонн)	7	7	7	7	2	30

Решение:

S=11*4+4*3+1*7+26*6+22*1+3*7+1*2=264 (д.е.)

Ответ S=264 д.е., план перевозок X₂=

 
ЗАКЛЮЧЕНИЕ

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

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

Метод симплекс-таблиц, методы решения транспортной задачи – все эти математические методы довольно хорошо известны. Я в курсовом проекте воспользовался возможностями прикладных программ при решении задач и выяснил преимущества Mathcad при решении задач линейного программирования графическим методом. При этом решение второй и третьей задач в Mathcad было более трудоёмко, чем Поиск решения в MS Excel.

В настоящее  время достаточно хорошо используется программное обеспечение для решения класса экономических задач.

 
Библиографический список

1 Абрамов Л.М., Капустин  В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

2 Акулич И.Л. Математическое  программирование в примерах  и задачах: Учеб. пособие - 2-е изд., испр. и доп. - М.: Высш. шк. ,1993 - 336 с.

3 Ашманов С.А.Линейное  программирование. - М.: Наука, 1981.

4 Баканов М.И., Шеремет  А.Д. Теория экономического анализа: Учебник. -4-е изд., доп. и перераб. - М.: Финансы и статистика, 2000. - 416 с.

5 Баканов М.И., Шеремет  А.Д.Экономический анализ: ситуации, тесты, примеры, задачи, выбор оптимальных решений, финансовое прогнозирование: Учеб. пособие. - М.: Финансы и статистика, 1999. -656 с.

6 Банди Б. Основы  линейного программирования: Пер.  с англ. - М.: Радио и связь, 1989. -176 с.

7 Габасов Р., Кириллова  Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во  БГУ им. В.И. Ленина, 1977. - 176 с.

8 Габасов Р., Кириллова  Ф.М. Методы линейного программирования. Ч.2. Транспортные задачи, Минск, Изд-во  БГУ им. В.И. Ленина, 1977. - 240 с.

 

ПРИЛОЖЕНИЕ А

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок А.1 – Листинг программы Mathcad