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

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

КУРСОВАЯ РАБОТА

по дисциплине

«Математическое программирование в геологоразведочной отрасли»

на тему

«Решение задачи линейного программирования применительно к геологоразведочной отрасли»

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

. СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

.1 Выбор элементов решения

.2 Запись ограничений

.3 Запись целевой функции

.4 Приведение системы ограничений к каноническому виду

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

ЗАКЛЮЧЕНИЕ

ПЕРЕЧЕНЬ РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

ЗАДАНИЕ 1.

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

РЕФЕРАТ

Пояснительная записка содержит: 20 с.,15 табл.,4 источника.

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

Цель работы - вывоз взорванной породы с минимальными транспортными затратами при соблюдении заданных ограничений с учетом максимальной приемной возможностью отвалов.

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

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, РЕШЕНИЕ, ОГРАНИЧЕНИЯ, ЦЕЛЕВАЯ ФУНКЦИЯ, ВЫРАБОТКА, ПОРОДА, ОТВАЛ, МИНИМАЛЬНЫЕ ЗАТРАТЫ.

транспортный затраты канонический математический

ВВЕДЕНИЕ

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

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

При принятии решений использовался метод математического программирования, реализация которого без ЭВМ практически невозможна.

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

При решении задачи использовался один из методов математического программирования - линейное программирование.

1. СОСТАВЛЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

.1 Выбор элементов решения

Основные понятия. Решение - всякий определенный выбор зависящих от нас параметров. Элементы решения - параметры совокупность, которых образуют решение. [3]

Элементами решения применительно к поставленной задачи будут:

х₁, х₂- оптимальные объемы породы, которые вывозятся с первой выработки, соответственно на первый и второй отвал, тыс. м³ км.

х₃, х₄- оптимальные объемы породы, которые вывозятся со второй выработки, соответственно на первый и второй отвал, тыс. м³ км.

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

.2 Запись ограничений

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

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

Ограничения по максимально допустимому годовому объему взорванной породы (1.1):

    (1.1)

Ограничения по максимальной приемной способности отвалов (1.2):

   (1.2)

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

.3 Запись целевой функции

Целевая функция - это показатель эффективности решения. [3]

В данной задаче целевая функция минимизирует транспортную работу при организации вывоза породы с горных выработок (1.3):

(1.3)

.4 Приведение системы ограничений к каноническому виду

Система ограничений, которая представляет математическую модель, имеет вид (1.4):

   (1.4)

Данную математическую модель, а именно систему ограничений неравенств необходимо привести к каноническому виду, позволяющему записать ее в симплекс-таблицу. Для этого систему ограничений неравенств приводят к эквивалентной системе уравнений (1.5) путем введения в каждое неравенство вспомогательной, неотрицательной переменной у со знаком «+» или «-» в зависимости от знака отношения. [1]

      (1.5)

Канонический вид системы уравнений будет выглядеть следующим образом (1.6):

       (1.6)

После приведения системы уравнений к каноническому виду, данные системы ограничений заносим в симплекс-таблицу (табл. 1.1). При занесении системы ограничений в симплекс-таблицу, необходимо изменить знак на противоположный у элементов независимых переменных. Так как в базисном решении все независимые переменные равны нулю (х = 0). [1]

Таким образом, математическая модель, записанная в симплекс-таблице, будет иметь вид:

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

Жордановы исключения. Каждая строка симплекс-таблицы несет в себе всю необходимую числовую информацию из уравнения связи базисной и независимых переменных. Так, переменная y_r получается путем умножения r-й строки таблицы на вектор независимых переменных, дополненных единицей.

.

Переход к новому общему решению предусматривает замену местами одной базисной и независимой переменной. При этом изменяются векторы базисных и независимых переменных и элементы симплекс-таблицы.

Пусть имеется разрешающий элемент а_rs, в котором необходимо заменить y_r на х_s. Строку и столбец с замененными переменными называют разрешающими строкой и столбцами, а элемент, стоящий на их пересечении - разрешающим элементом.

В новой таблице на месте yr будет располагаться переменная x_s, а на месте x_s - переменная y_r.

Элементы новой симплекс-таблицы вычисляются по следующим правилам:

1. На месте разрешающего элемента в новой таблице записывается 1/a_rs.

2. Остальные элементы разрешающей строки делятся на разрешающий элемент, т.е. вместо a_rj в новую таблицу записывается a_rj/a_rs.

3. Остальные элементы разрешающего столбца делятся на разрешающий элемент и записываются в новую таблицу с противоположным знаком, т.е. вместо a_ij заносится (-a_ij/a_rs).

      (2.1)

Из приведенных формул пересчета элементов следует вывод: замену переменных можно выполнить только в случае, когда разрешающий элемент не равен 0, т.е. a_rs¹0.

Описанная процедура носит название жордановых исключений. [2]

Если исходная задача имеет смешанную систему ограничений неравенств, то она приводится к эквивалентной системе уравнений путем введения в каждое неравенство вспомогательной, неотрицательной переменной y со знаком «+» или «-» в зависимости от знака отношения.

Решение задачи выполняется на ЭВМ с использованием компьютерной программы simplex.exe. разработанной на кафедре ТТГР. Решение, приведенное в табл. 1.1 представляет собой опорное решение и оптимальное. Решение является опорным, т.к. в столбце свободных членов отсутствует отрицательный элемент. А также решение является оптимальным, т.к. в строке целевой функции нет отрицательных элементов.

Согласно данной таблице решение следующие: (х₁ = х₂ = х₃ = х₄ = 0), поскольку независимые переменные всегда равны нулю. Но это решение не может быть принятым в качестве оптимального, поскольку оно исключает выполнение работ вообще.

Таким образом, необходимо изменить систему ограничений. А именно ввести жесткое ограничение (уравнение) дающее возможность обеспечить гарантированное выполнение работ на первой выработке, при этом общий объем работ будет равный 18. Введение большого количества жестких ограничений, возможно, может привести к значительному уменьшению столбцов симплекс-таблицы. Что может не позволить решить данную задачу. Новая система ограничений будет иметь вид (2.2):

   (2.2)

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

Таким образом, математическая модель, записанная, в симплекс-таблице будет иметь вид (табл.2.1):

Таблица 2.1 - Исходная симплекс-таблица.

Решение, приведенное в табл. 2.1 не содержит базисного решения, потому что первый элемент столбца базисных переменных содержит нуль-переменную. Чтобы получить базисное решение необходимо нуль-переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.2).

Таблица 2.2-Интерация 1

Решение, приведенное в табл. 2.2 не является опорным. Так как в столбце свободных членов имеется отрицательный элемент. Выполнив следующий шаг жордановых исключений, получим следующее решение (табл. 2.3):

Таблица 2.3-Интерация 2

Решение, приведенное в табл.2.3 является опорным. Так как в столбце сводных членов отсутствует отрицательный элемент. Но не является оптимальным, так как в строке целевой функции имеется отрицательный элемент. Выполнив следующий шаг жордановых исключений, получим следующее решение (табл. 2.4):

Таблица 2.4-Интерация 3

Решение, приведенное в табл. 2.4 является оптимальным, так как в строке целевой функции отсутствует отрицательный элемент. Данное решение допускает отсутствие работ на второй выработке (х₃ = х₄ = 0), а из работающей первой выработки породу вывозят только на второй отвал (х₁=0; х₂=18). Данное решение оптимально с точки зрения линейного программирования, но не может быть принято нами оптимальным, так как предусматривает полное отсутствие работ на второй выработке. При этом транспортная работа z = 140 тыс.м^3.км.

Таким образом, необходимо изменить систему ограничений. А именно ввести жесткое ограничение (уравнение) дающее возможность обеспечить гарантированное выполнение работ на первой выработке и на второй выработке, при этом общий объем работ на первой выработке будет равный 18, а на второй-15. Новая система ограничений будет иметь вид (2.3):

   (2.3)

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

Таким образом, математическая модель, записанная, в симплекс-таблице будет иметь вид (табл.2.5):

Таблица 2.5 - Исходная симплекс-таблица.

Решение, приведенное в табл. 2.5 не содержит базисного решения, потому что первый и второй элементы столбца базисных переменных содержат нуль - переменные. Чтобы получить базисное решение необходимо нуль- переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.6).

Таблица 2.6-Интерация 1

Решение, приведенное в табл. 2.6 не содержит базисного решения, потому что первый элемент столбца базисных переменных содержит нуль-переменную. Чтобы получить базисное решение необходимо нуль-переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.7).

Таблица 2.7-Интерация 2

Решение, приведенное в табл. 2.7 является оптимальным, так как в строке целевой функции отсутствует отрицательный элемент. Данное решение допускает отсутствие работ на второй выработке (х₃ = х₄ = 0), и при этом породу вывозят только из первой выработки (х₁ = 15; х₂ = 3). Данное решение оптимально с точки зрения линейного программирования, но не может быть принято нами оптимальным, так как предусматривает полное отсутствие работ на второй выработке. При этом транспортная работа z = 161 тыс.м^3.км.

Таким образом, необходимо изменить систему ограничений. А именно ввести жесткое ограничение (уравнение) дающее возможность обеспечить гарантированное выполнение работ на первой выработке, при этом общий объем работ будет равный 21. Новая система ограничений будет иметь вид (2.4):

   (2.4)

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

Таким образом, математическая модель, записанная, в симплекс-таблицу будет иметь вид (табл.2.8):

Таблица 2.8 - Исходная симплекс-таблица.

Решение, приведенное в табл. 2.8 не содержит базисного решения, потому что первый элемент столбца базисных переменных содержит нуль-переменную. Чтобы получить базисное решение необходимо нуль-переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.9).

Таблица 2.9-Интерация 1

Решение, приведенное в табл. 2.9 является базисным, так в столбце базисных переменных отсутствует нуль-переменная. Но решение не является опорным. Так как в столбце свободных членов имеется отрицательный элемент. Необходимо выполнить следующий шаг жордановых исключений (табл. 2.10).

Таблица 2.10-Интерация 2

Решение, приведенное в табл. 2.10 является опорным. Так как в столбце сводных членов отсутствует отрицательный элемент. Но решение не является оптимальным, так как в строке целевой функции имеется отрицательный элемент. Выполнив следующий шаг жордановых исключений, получим следующее (табл. 2.11):

Таблица 2.11-Интерация 3

Решение, приведенное в табл. 2.11 является оптимальным, так как в строке целевой функции отсутствует отрицательный элемент. Данное решение допускает отсутствие работ на первой выработке (х₁ = х₂ = 0), а из работающей второй выработки породу вывозят только на второй отвал (х₃ = 0; х₄ = 21). Данное решение оптимально с точки зрения линейного программирования, но не может быть принято нами оптимальным, так как предусматривает полное отсутствие работ на первой выработке. При этом транспортная работа z = 67 тыс.м^3.км.

Таким образом, необходимо изменить систему ограничений. А именно ввести жесткое ограничение (уравнение) дающее возможность обеспечить гарантированное выполнение работ на первой и второй выработке, при этом общий объем работ на первой выработке будет равный 18, а на второй-29. Новая система ограничений будет иметь вид (2.5):

   (2.5)

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

Таким образом, математическая модель, записанная, в симплекс-таблицу будет иметь вид (табл.2.12):

Таблица 2.12 - Исходная симплекс-таблица.

Решение, приведенное в табл. 2.12 не содержит базисного решения, потому что первый и второй элементы столбца базисных переменных содержат нуль-переменную. Чтобы получить базисное решение необходимо нуль- переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.13).

Таблица 2.13-Интерация 1

Решение, приведенное в табл. 2.13 не содержит базисного решения, потому что второй элемент столбца базисных переменных содержит нуль-переменную. Чтобы получить базисное решение необходимо нуль-переменную вывести из базисного решения. Эту операцию нужно совершить последовательным шагом жордановых исключений. А именно ввести независимую переменную в базисную переменную, а столбец под ней сократить (табл. 2.14).

Таблица 2.14-Интерация 2

Решение, приведенное в табл. 2.14 является базисным, так в столбце базисных переменных отсутствует нуль-переменная. Но решение не является опорным. Так как в столбце свободных членов имеется отрицательный элемент. Необходимо выполнить следующий шаг жордановых исключений (табл. 2.15).

Таблица 2.15-Интерация 3

Решение, приведенное в табл. 2.15 является оптимальным, так как в строке целевой функции отсутствует отрицательный элемент.

Данное решение показывает, что работы ведутся на двух выработках. При этом:

Объем горной породы, вывозимой из первой выработки на первый отвал х₁ = 0, т.е. горная порода из первой выработки на первый отвал не вывозится.

Объем горной породы, вывозимой из первой выработки на второй отвал х₂ = 18 тыс. м³ км.

Объем горной породы, вывозимой из второй выработки на второй отвал х₄ = 11 тыс. м³ км.

Произведем проверку, подставив, данное полученное решение в систему ограничений (2.5), и получим (2.6):

   (2.6)

Из системы уравнений (2.6) видно, что данное решение допускает выполнение максимальной приемной способности второго отвала, тыс. м³ (х = 29). А также, что работы ведутся на двух выработках. И при этом первый отвал не задействован.

ЗАКЛЮЧЕНИЕ

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

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

При этом выполняются все ограничения из данного соотношения объемов работ.

ПЕРЕЧЕНЬ РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Резниченко С.С., Подольский М.П., Ашихмин А.А Экономико-математические методы и моделирование в планировании и управлением горным производством. Уч. для вузов - М: Недра, 2010. -429 с.

. Карманов В.Г. Математическое программирование. М., Наука, 2008.

. Венцель Е.С. Исследование операций: задачи, принципы, методология, М., Наука, 2011.

. Методичні вказівки до курсової роботи з дисципліни "Математичне програмування в бурінні" для студентів спеціальності 7.090306 "Буріння"// Склад. Н.Т. Филимоненко, С.Н. Парфенюк - Донецьк: ДонНТУ, 2009 - 22 с.