Элементы линейного программирования

Таблица 1.10

Суммарная эффективность вариант назначения составит 142 единицы.

Вычислим элементы матрицы оценок (Табл. 1.10).

Таблица 1.11

Отрицательных оценок нет. Назначение, представленное в таблице 1.10, является оптимальным вариантом назначения. Среди небазисных оценок имеется нулевая оценка , поэтому существуют альтернативные оптимальные варианты назначения.

Итак, оптимальный вариант назначения имеет вид:

, т.е. первый механизм назначен на шестую работу, второй - на первую, третий - на четвертую, четвертый - на пятую, пятый - на вторую, шестой - на третью. Остальные переменные Максимальное значение функции

единиц

3. Найти оптимальный вариант назначений, если матрица эффективностей такова: (венгерский метод)

Решение. Предварительный этап.

Шаг 1. наибольший элемент первого столбца матрицы равен 26.

Поэтому для получения элементов первого столбца матрицы необходимо из 26 вычесть последовательно элементы первого столбца матрицы и поместить полученные результаты в соответствующие позиции первого столбца искомой матрицы. Аналогично для образования столбцов 2, 3, 4, 5 и 6 матрицы вычесть из величин 23, 26, 30, 27 и 27. Получим матрицу:

Шаг 2. Наименьший элемент первой строки матрицы равен 3. Для получения элементов первой строки матрицы необходимо число 3 вычесть последовательно из каждого элемента первой строки матрицы и поместить полученные результаты на прежние места. Во второй строке из каждого элемента вычитаем число 2, в третьей - число 9. Строки 4, 5 и 6 не изменятся, так как минимальные элементы этих строк равны нулю.

После второго шага предварительного этапа получим матрицу:

+ + + +

+

П.1. В первом столбце матрицы помечаем звездочкой нуль, расположенный в шестой строке; во втором столбце помечаем звездочкой нуль, расположенный в пятой строке. В 3, 4 и 5 столбцах помечаем звездочкой нули, расположенные соответственно в первой, второй и четвертой строках. В шестом столбце единственный нуль расположен в пятой строке, в которой уже есть и поэтому не может быть помечен звездочкой.

Число нулей со звездочкой меньше 6, переходим к пункту 2.

П. 2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4 и 5 и считаем эти столбцы занятыми. Незанятый нуль находится в пятой строке шестого столбца. Помечаем его штрихом. В пятой строке есть , переходим к пункту 3.

П. 3. Знак «+» у второго столбца снимаем и вновь считаем его незанятым столбцом, а пятую строку считаем занятой и помечаем знаком «+» справа. Снятие любого значка, в дальнейшем, условимся обводить в рамочку. Возвращаемся к третьему абзацу пункт 2. Незанятых нулей нет. Переходим к пункту 5.

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

+ +

Возвращаемся к четвертому абзацу пункта 2.

П.2. Незанятые нули находятся в первой строке второго и шестого столбцов: Первый из них помечаем штрихом . В третьем столбце первой строки находится нуль со звездочкой. Третий столбец вновь считаем незанятым и знак «+» сверху снимаем , а первую строку объявляем занятой и помечаем знаком «+» справа. Незанятый нуль находится в освободившемся 3 столбце в позиции (6,3). Помечаем штрихом и считаем незанятым первый столбец, а 6 - ю строку объявляем занятой. Незанятых нулей нет. Переходим вновь к пятому пункту.

П.5. Теперь . Вычитаем из незанятых строк: второй, третий и четвертый, а затем прибавляем к занятым столбцам: четвертому и пятому. Получим матрицу , в которой образовалось два незанятых нуля: и .

+

Переходим к пункту 2. Помечаем штрихом . Имеем два незанятых нуля: и . Первый из них помечаем штрихом . В третьей строке нет , следовательно, переходим к пункту 4.

П. 4. Строим цепочку из нулей. Начинаем от , идем по столбцу до , по строке - до , по столбцу - до , по строке - до , по столбцу - до , по строке - до , по столбцу - до , и наконец, по строке - до . Цепочка имеет вид:

.

Вносим изменения в цепочке: звездочки у нулей в цепочке снимаем, а вместо штрихов у нулей в цепочке ставим звездочки:

.

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

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

19+22+21+27+27+26=142 единиц эффективности.

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

Кроме того, из оптимального варианта, полученного методом потенциалов, можно получить оптимальный вариант, полученный методом Эгервари, если в качестве разрешающей коммуникации выбрать коммуникацию (1,2).

ЗАКЛЮЧЕНИЕ

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

2. Аксентьев В.А. Сборник задач по математическим методам в экономике. - Тюмень: Изд - во Тюменского государственного университета, 2003. - 264

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

4. Волков В.А., Элементы линейного программирования. Пособие для учителей средней школы. - М.: Просвещение, 1975. - 73 с.

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

6. Гасс С. Линейное программирование. - М.: Физматгиз, 1961. - 240 с.

7. Ермаков В.И., Общий курс высшей математики для экономистов, М.: Инфра-М, 2000. - 343 с.

8. Идрисов Ф.Ф. Линейное программирование. - Томск: Изд - во ТГПУ, 2004. - 124 с.

9. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании - М.: Изд - во «Дело», 2001. - 360 с.

10. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие. - 2-е изд., перераб. и доп. - М.: Высш. шк., 1980. - 300 с.

11. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск: Высш. шк., 2001. - 270с.

12. Ляшенко И.Н, Карагодова Е.А, Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. - М.: Издательское объединение Высш. шк., 2000. - 372 с.

13. Солодовников А.С. Введение в линейную алгебру и линейное программирование. - М.: Просвещение, 1999. - 184 с.

Размещено на Allbest.ru